Hofman and Diaby talk about P=NP at INFORMS 2007

According to the conference website, Moustapha Diaby and Radoslaw
Hofman were scheduled to talk at a session on Friday, January 5th, at
the tenth INFORMS computing society conference. Would it be possible
for Hofman, Diaby, or another conference attendee to say how the
session went?

On 9 Jan 2007 23:37:49 -0800, dmoews{}fastmail.fm wrote:

>According to the conference website, Moustapha Diaby and Radoslaw
>Hofman were scheduled to talk at a session on Friday, January 5th, at
>the tenth INFORMS computing society conference. Would it be possible
>for Hofman, Diaby, or another conference attendee to say how the
>session went?

Next good argument for me not to renew INFORMS membership.

A.L.

dmo...{}fastmail.fm wrote:
> According to the conference website, Moustapha Diaby and Radoslaw
> Hofman were scheduled to talk at a session on Friday, January 5th, at
> the tenth INFORMS computing society conference. Would it be possible
> for Hofman, Diaby, or another conference attendee to say how the
> session went.

Dr. Moews:

Please, see

http://www.business.uconn.edu/users/...To_Hofman2.pdf


for a summary of the "rebuttal" I had planned to present, eventhough I
had been informed beforehand that Hofman had withdrawn his paper.

I ended up not presenting this rebuttal because the session chair felt
it would have served no purpose at the conclusion of my actual
presentation. Instead, we (myself and a number of the people in
attendance) spent the time in informal discussions...

I think my presentation went quite well!

//MD

Hi

I havent visitied Usenet for while and I wasn't either on INFORMS... :-(. I
hadn't withdrawn my paper - and I don't know if it was printed in conference
predceedings - I just couldn't be there .

Answering to problems written by Diaby in presentation below:

> http://www.business.uconn.edu/users/...To_Hofman2.pdf

Page 11 - funny
I have written here SEVERAL times that I prepared example and used ONLY
variables which were not equal to zero. Further on I have prepared
constraints containing at leas one non-zero variable. Because whole flow was
designed "by hand" I can perfectly point which variables are zero.

In fact for 32 cities I have less then 1 million constraints contaning at
least one non-zero variable so it is computable even on my laptop in less
then 3 hours. So argument that I isn't possible to build counter example is
false (or Mr. Diaby claims that adding 32^7 equations 0=0 changes result
:-) ).

For the first thing - page 3:

2. It is possible to completely describe a polytope with an exponential
number of extreme points using a polynomially-bounded number of constraints
For example: The Assignment Polytope
==> Assignment Polytope isn't some "magical oracle" allowing to find answer
for polynomial number of constraints. In fact polytope presented by Diaby is
symmetric polytope which is proved to be unable to solve NP-complete TSP
problem (see Yannakakis). So... What are we talking about?

3. The LP relaxation of an IP can have have integral verticesunder certain
conditions (such as total-unimodularity).
==> Maybe, but Diaby violates these conditions because his polytope allows
to find incorrect solutions what is showed in my counter-example

If I was on INFORMS I would have asked Mr. Diaby to use 4 lines and make
restrictions for set of 4000 points in such way that target function (any
possible one) would always give correct result - it is obvious that it is
impossible. TSP polytope has 2^n facets - claiming that n^7 restrictions
coveres them for large n is... WRONG

Best regards,

Radek Hofman

On Wed, 24 Jan 2007 12:45:39 +0100, "Radoslaw Hofman"
<radekh{}teycom.pl> wrote:

>Hi
>
>I havent visitied Usenet for while and I wasn't either on INFORMS... :-(. I
>hadn't withdrawn my paper - and I don't know if it was printed in conference
>predceedings - I just couldn't be there .
[...]
>If I was on INFORMS I would have asked Mr. Diaby to use 4 lines and make
>restrictions for set of 4000 points in such way that target function (any
>possible one) would always give correct result - it is obvious that it is
>impossible. TSP polytope has 2^n facets - claiming that n^7 restrictions
>coveres them for large n is... WRONG
>

Who cares... really?...

A.L.

Uzytkownik "A.L." <alewando{}fala2005.com> napisal w wiadomosci
> Who cares... really?...

I don't know



I didn't want to leave this unanswered with suggestions that I have
withdrawn :-)



Cheers,



Radek Hofman

On Jan 24, 6:45 am, "Radoslaw Hofman" <rad...{}teycom.pl> wrote:
> Answering to problems written by Diaby in presentation below:
>
> >http://www.business.uconn.edu/users/..._Hofman...Page 11 - funny
> I have written here SEVERAL times that I prepared example and used ONLY
> variables which were not equal to zero. Further on I have prepared
> constraints containing at leas one non-zero variable. Because whole flow was
> designed "by hand" I can perfectly point which variables are zero.

>
> In fact for 32 cities I have less then 1 million constraints contaning at
> least one non-zero variable so it is computable even on my laptop in less
> then 3 hours. So argument that I isn't possible to build counter example is
> false (or Mr. Diaby claims that adding 32^7 equations 0=0 changes result
> :-) ).
>



The sizes reported in my posted document for my LP formulation are for
variables and constraints that MUST be explicitly considered. (You can
easily check that it is not n^9 and n^7 for the variables and
constraints, respectively). For a 32-city TSP, my LP has more than 100
millions variables and 100 millions constraints. If you are only
considering about one million constraints, then there are more than 99
millions constraints that MUST be satisfied, but that you are not
checking. And, they are definetely not trivial equations... The same
is true of the variables.



> For the first thing - page 3:
>
> 2. It is possible to completely describe a polytope with an exponential
> number of extreme points using a polynomially-bounded number of constraints
> For example: The Assignment Polytope
> ==> Assignment Polytope isn't some "magical oracle" allowing to find answer
> for polynomial number of constraints. In fact polytope presented by Diaby is
> symmetric polytope which is proved to be unable to solve NP-complete TSP
> problem (see Yannakakis). So... What are we talking about?


We are talkiong about the difference between the assignment polytope
and the TSP polytope. As clearly shown in my paper, I do not deal with
the TSP polytope...


>
> 3. The LP relaxation of an IP can have have integral verticesunder certain
> conditions (such as total-unimodularity).
> ==> Maybe, but Diaby violates these conditions because his polytope allows
> to find incorrect solutions what is showed in my counter-example

Your "counter-example" is invalid for the reasons indicated in my
document.

>
> If I was on INFORMS I would have asked Mr. Diaby to use 4 lines and make
> restrictions for set of 4000 points in such way that target function (any
> possible one) would always give correct result - it is obvious that it is
> impossible. TSP polytope has 2^n facets - claiming that n^7 restrictions
> coveres them for large n is... WRONG


You have this backward. And your confusion here is more in the realm of
"pure mathematics" than in "mathematical programming."
It should go like this: in k-dimensional space, the number of points
that can be defined by m linear equations is "Combination(m, k)". For
example, in 2-dimensional space, if you have 10 linear equations, then
those can define "Combination (10, 2)" points. The dimension of the
space in which my model is stated is 9. The number of linear equations
is on the order n^7. So the number of points that can be defined by
these equations is on the order of "Combination (n^7, 9)." Try
comparing to n! or 2^n.


//MD

//PS: I do not intend to continue thios discussion and will not respond
to this kind of "stuff" anymore.

On Jan 25, 9:56 am, moustapha.di...{}business.uconn.edu wrote:
>The dimension of the
> space in which my model is stated is 9.

The dimension is actually 15 (I forgot the y-variables). Everything
else is the same in the post.

//MD

Uzytkownik <moustapha.diaby{}business.uconn.edu> napisal w wiadomosci
news:1169737009.817606.66330{}j27g2000cwj.googlegr oups.com...

> The sizes reported in my posted document for my LP formulation are for
> variables and constraints that MUST be explicitly considered. (You can
> easily check that it is not n^9 and n^7 for the variables and
> constraints, respectively). For a 32-city TSP, my LP has more than 100
> millions variables and 100 millions constraints. If you are only
> considering about one million constraints, then there are more than 99
> millions constraints that MUST be satisfied, but that you are not
> checking. And, they are definetely not trivial equations... The same
> is true of the variables.

No. Remember that I know exact list of non-zero variables so I can exactly
say which equations must be generated. I omitt only those where EVERY
variable is equal to zero. You must admit that such operation does not
change sense of solution. It does not matter how "non-trivial" idea was - if
feasible solution may have all variables from certain equation equal to zero
then whole equation can be omited.



Have you seen source code? You can see skipping rules there - every
condition from your BLP is there. Only skipping is done by checking:

- if I should generate equations for y_i_s_j_*_*_* and z_*_*_*_i_s_j_*_*_* I
first check if there is x_i_s_j - if not, then all y's and z's contain i_s_j
in index have to be zero - all such equations can be omited (true?)

- even more - entering loop I check if there is at leas one x starting from
i - if not whole loop can be omitted because we will not have any x_i_*_*
not equal to zero and consequently y's and z's



Those are all reductions I make - they really do not change meaning (do you
agree?).



And as some of usenet members pointed out you haven't proved that every
feasible BLP solution is also feasible TSP solution. (in paper there is
proof in opposite direction). My counter example only shows that you will
never be able to prove it because there exists at least one feasible
solution which overall value is less then optimal TSP tour.



>> ==> Assignment Polytope isn't some "magical oracle" allowing to find
>> answer
>> for polynomial number of constraints. In fact polytope presented by Diaby
>> is
>> symmetric polytope which is proved to be unable to solve NP-complete TSP
>> problem (see Yannakakis). So... What are we talking about?
>
> We are talkiong about the difference between the assignment polytope
> and the TSP polytope. As clearly shown in my paper, I do not deal with
> the TSP polytope...

Because of what? Because you say so? No, in fact you build very complex
polytope but it still is TSP polytope!



I do not understand why do you believe that 3 dimensions of variables are
enough? What is special in number 3? Why not 5 dimensions (you would have
had variables d_(i,a,j)_(k,b,l)_(m,c,n)_(o,d,p)_(q,e,r)). Is this model also
correct one (of course after defining bunch of restrictions)? Or in opposite
direction - why 2 dimensions are not enough? And why 1 is not enough?



If you knew answer for above you could probably (assuming that you have a
bit of research and doubting approach) see that your model has nothing
special making it correct...



Believe me - I was once looking for my own model for NP-complete problem.
Problem was different (SAT) but in one of attempts I have build model with
flows and 3 dimensional checking consistency of flow (it was almost
identical to yours). I was very satisfied because I seemed I had had more
equations then variables. I started some experiments and very shortly found
out that model (with best possible restrictions) can give incorrect answer -
feasible solutions were wrong. I started to wonder why... and tried to find
proof missing in your paper - how is it possible to prove that feasible
solution is also correct. Now I know that it is impossible...



>> 3. The LP relaxation of an IP can have have integral verticesunder
>> certain
>> conditions (such as total-unimodularity).
>> ==> Maybe, but Diaby violates these conditions because his polytope
>> allows
>> to find incorrect solutions what is showed in my counter-example
>
> Your "counter-example" is invalid for the reasons indicated in my
> document.



Please, stop writing, saying and thinking that it is incorrect unless you
can show AT LEAST ONE:

- not legal variable

- violated restriction

You could not find such thing in my counter example, you cannot solve my
example using your method, you didn't give me source codes to implement
counter example in them. Why then you repeat that it is incorrect? Because
it contradicts with your paper? Or maybe figures are in wrong colors? Unless
you have one solid thing that is wrong in my counter example you only
*claim* that it is incorrect, and your model is correct... It is *claim* not
*fact*.



> You have this backward. And your confusion here is more in the realm of
> "pure mathematics" than in "mathematical programming."
> It should go like this: in k-dimensional space, the number of points
> that can be defined by m linear equations is "Combination(m, k)". For
> example, in 2-dimensional space, if you have 10 linear equations, then
> those can define "Combination (10, 2)" points.

==> But it only applies to line-crossings... I have meant something else

http://www.teycom.pl/diaby/eq2.png



Imagine that we have 4000 such red points (as on the picture - making some
random shape). You can use 4 lines (as on the picture) and target is to
build such restriction that your claim is correct: "any point found on edge
of restriction corresponds to some set of solutions" or in other words "has
value of optimal solution or greater".



Green line on the picture is example of target function - and it cuts model
with value much lower then optimal solution.



Your BLP model is such set of linear equations, and TSP solutions are such
red points - you cannot prove that every solution will be feasible in TSP.
To do it you should have O(2^n) restrictions because in worst case O(2^n)
points make different solutions, and your BLP model has to adapt to it.



> //PS: I do not intend to continue thios discussion and will not respond
> to this kind of "stuff" anymore.

As you wish

I'm disappointed - first time I have mailed you I really expected that
talking with person with Ph.D. will allow me to present my point and count
for consideration. And... I say something, show counter-example, you
couldn't find flaw in it but repeat (as mantra) that it is incorrect... I
would have expected such attitude from my 3 years old son, not science
worker...

And BTW:
> The dimension of the
> space in which my model is stated is 15. The number of linear equations
> is on the order n^7. So the number of points that can be defined by
> these equations is on the order of "Combination (n^7, 15)." Try
> comparing to n! or 2^n.

I did... and amazing you don't realize what happens for large n.

Let us take n=1000.

We have 4,02*10^2567=402*1000^855 feasible TSP solutions.

Combination(1000^7,15)=
=(1000^7)! / (1000^7-15)!*15!=
=(1000^7-14)*(1000^7-13)...(1000^7) / 15!
<1000^(7*15)/10^12 //15! > 10^12
=1000^105/1000^4=1000^101

What a surprise.... For n=1000 you have only 1000^101 points while there are
more then 1000^855 possible solutions. So your model contains... less then
1% or even less then any bit of percent.

Why then you claim that for n=1000 your model can solve TSP problem? Can't
you see that no matter how large constants you take n^7, n^14, n^21...
limens of this comparision always will show that number of points grows
faster!

Proof:
lim csub{n toward inf} (n!-{(n^c)!} over {d!*(n^c-d)!} ) =
lim csub{n toward inf} (n!-{(n^c-d+1)*(n^c-d+2)...*(n^c-d+d)} over {d!} ) =
lim csub{n toward inf} (n!-{(n^c-d+1)*(n^c-d+2)...*(n^c-d+d)} over {d!} ) <
lim csub{n toward inf} (n!-{n^{c*d}} over {d!} ) =
lim csub{n toward inf} (n!-{n^e} over {f} ) = +inf

Best regards,

Radek Hofman