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

Radoslaw Hofman wrote:
Hi,

There is nothing "escaping" mine attention :). We have two
possibilities:
1) You do not understand my objection
2) Mine and yours definition of "proof" differs dramatically (because
you call "proven" thing which I can show is wrong).

You prove for integer linear programming that feasible solution is ONE
TSP tour, and it is obvious. But after changing to non-integer version
you omit this problem. You write in "proof" for proposition 3:
"Hence, there is a one-to-one correspondence between paths in (y, z)
from (1, .) to (n-2, .) and c.a.s.s. paths of Graph G (and therefore,
TSP tours)." And where is proof that this correspondence is one to
one? Where is proof that NON-TSP paths cannot be combined together
forming groups feasible in model?

This thing is not true if you are expressing not single solution but
set of solutions! This is crucial difference between integer and
non-integer version of problem: integer version expresses ONE solution
at time. If there are many possible solutions than still it holds only
ONE. Non-integer version expresses SET OF SOLUTIONS. And therefore it
needs different expression precision. And assumption that "integer
version refers to TSP tour then non-integer version refer to set of TSP
tours" is more then naïve.

BTW: what background do you have on complexity theory? If you had it,
then you would realize consequences of my last arguments (those with
figures and cardinality of power-set over n!). Imagine problem instance
for n=100. Let us assume that 25% of solutions are optimal. Can your
model "list" them all? No!

There would be 100!/4=X/4*10^24=[BIG NUMBER]*10^24 optimal solution,
while your model is capable to store no more then 10^18 different
solutions. If then in your model you cannot recognize EVERY possible
solution why are you so sure, that there are no NON-TSP paths combined
together?

One more thing - on computing machines it is impossible to store
infinite number of different values. Even using decimals - they are
stored on X bites, what means that they can have NO MORE then 2^X
different values. This means that if one wants your model to work
number of bites should correspond to n! making it exponential (not
polynomial).

I came up with solution to our argument. Please - let us all source
code of your equation generating program (as I did with mine counter
example, and all equations generating program) - capable to generate
equations for n=32 with some instructions how to use it. I hope that
(because you claim you have used this program) it is not effort
exceeding your possibilities.

Because I know all y's and z's values in counter example I will make
only one modification to your program: I will not generate in output
file variables which are equal to 0. Of course I will also omit
equations which are to be equal to zero and which left side contains
only equations equal to 0. You have to agree that such modification
does not change interpretation of output.

How I will do it? I will put all variables with values to database, and
in your program I will add checks before printing each variable (if it
is in database then it will be printed, if not that means that it is
equal to 0 and won't be printed). I shall also make stronger cut
offs:

If your program is generating (for example equation 3.8) after choosing
u and v we may check if there is any possible flow for u to v. If not
then we know that all y_u*v***, y_***u*v, z_u*v******, z_***u*v***,
z_******u*v are zeros and we can skip whole branch. So after picking up
some arc used in EVERY variable in equation I will check if any of them
is non-zero, if not whole equation shall be skipped.

This should be generated in less then 24 h taking no more then 300 MB.

You have to admit that if solution is to be correct for any n=32, then
after such modification it should be infeasible. It does not change any
part of logic in your model (I can assign my own values to variables -
LP solver would do it if all equations were generated).

Of course I will send you back modified program with unload of mine
variables table. Every modification will be marked very clearly with
comment (you will be able to check with text comparator, that in other
places code remains as it was).

Of course I might not be able to do it if your source code is written
not according to rules of proper programming... but let's have a try!

I think this proposition is very fair, and it will allow us with
corollary - counter example is wrong, or your method is incorrect for
large instances. Effort required by you is minimal.

What do you say? :)

Cheers,

Radek Hofman



Mr. Hofman,

To make things easier I am reproducing some of your comments before
responding to them.

There is nothing "escaping" mine attention :). We have two
possibilities:
1) You do not understand my objection

The "path" notion in Proposition 2 (and introduced just before it) is
escaping you. Otherwise, combine it with constraints 2.14 and it would
be obvious to you why your objection is not valid.

You write in "proof" for proposition 3:
"Hence, there is a one-to-one correspondence between paths in (y, z)
from (1, .) to (n-2, .) and c.a.s.s. paths of Graph G (and therefore,
TSP tours)." And where is proof that this correspondence is one to
one? Where is proof that NON-TSP paths cannot be combined together
forming groups feasible in model?

No, this is not written as part of the proof of Proposition 3. It is a
remark after the proposition, to make the transition smooth. No more.
The statement may need to be made more precise, but that is a extremely
trivial matter. The fact is, it does not have any impact on the
correcteness of Propositions 2 or 3.

With respect to your other comments having to do with number of
possible solutions, etc., I would suggest to you that you familiarize
yourself with the subject of Linear Programming. (I don't mean this in
an insulting way, but I base it on the emails you have sent me in
private -- and to which, BTW, I have always responded with the utmost
courtesy!).

.