Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time

Hi,

I was wondering yesterday why you have advised me to "get familiarized" with
subject of Linear Programming. Of course I did not think about personal and
insulting reasons - I wondered what factor of LP do you think you know, what
makes your solution which I do not :).

I think I know the answer - it is in your article in section 2.2 where you
refer to polytope built on TSP solutions. Well. no doubt it is true :). Even
if we changed from integer programming (meaning polytope lattice) to
non-integer programming solution which is "on the edge" of polytope is in
the same place. No doubt of this. See picture:
http://www.teycom.pl/diaby/eq1.png

But. When we are discussing polytope and if you look closer on what your
model is dealing with - it is only "picture" of this polytope "done with
poor quality leans" (I do not use word "poor" in context of your work - I
want to stress out that "picture" is fuzzy).

Why do I say it? I think that is also thing "escaping" your attention:
number of vertexes of polytope is equal to number of possible TSP solutions
(n!), while your model is capable of being precise up to n^9 variables and
n^7.

I shall give you example with pictures - imagine that we want to get picture
of stars in the night and we use very good digital camera capable of
recognizing 100 MPixels. We make photo. and we look on this photo. What
conclusions you have is "largest star in the Universe is this one because it
is largest on my photo". But you cannot be sure that there exists star so
far away that this 100 MPixels camera cannot even notice it is there. and
this one is the largest.

So, thinking of polytope with n! vertexes. You create model ("photo" of
polytope) using n^7 equations. It is obvious then, that not every vertex is
used in your picture. Even if one "line" touches n vertexes, only O(n^8)
vertexes are recognizable. Or even worse - if your modes chooses really most
important parts of picture - it can recognize no more then n^20 vertexes.

What happens to other? These are still feasible solutions! You assume that
"all not recognized vertexes are "inside" of polytope, or has worse target
function". Is this part so obvious? In my opinion not. But more important
thing is, that your model allows solutions which are feasible for LP while
they are infeasible for integer LP. Finding example where such infeasible
solution has better target value is. simple - it only need to "build up"
example having more "curves", "edges" and vertexes then your model can
handle. See picture 2 as an example:
http://www.teycom.pl/diaby/eq2.png

This is what I'm writing about in last posts - your model is simple
incapable of having precise picture of polytope. So considerations about
polytope and consequences of this are true (that optimal solution is on the
edge), but having only sketch (only few % for large instances of real shape)
in algorithms memory makes this method fragile for large instances with some
traps in them. That is what I have shown in my text - how to build "trap"
for your method.

It is exactly the same when you want to recognize some functions shape (for
example if they are monotone) - number of checks (lets denote them as S) is
to small then functions of size y=x^(S*3) are capable of fitting perfectly
in every check-point while recognized picture is simply incorrect.

On very large instances (n=100) we have 9.3*10^157 vertexes while your model
can recognize no more then 10^40. This means that this model for such
instance cannot recognize even 1% of vertexes. It is then like picture from
web-cam of this sky. you cannot tell anything studying such picture. That's
why I say that proposition 4 is simply FALSE.

This could have worked. If number of equations had been so large, that every
possible solution had at least one equation "touching" it. This means that
number of equations and expressions in them would be O(n!).

Cheers,

Radek Hofman

PS. Where are you going to make yopur publication - maybe they should
consider mine examples as well :)


.