New thred of discussion about Mr. Diaby's algorithm

Hi,



My usenet client is fed up with depth of discussion about Mr. Diaby TSP
conjecture so I have decided to summarize it here and ask all of you to
continue discussion here.



We are discussing paper http://arxiv.org/abs/cs.CC/0609005 with its twin
about QAP
http://arxiv.org/abs/cs.CC/0609004. Second one was even presented on
IMECS 2006 conference where author obtained merit award for it.



I have prepared counter example http://arxiv.org/abs/cs.CC/0610125 for n=32
(there is source code of program generating variables, their values,
boundaries and whole LPT instance - compatible with SoPlex - for BLP model
presented in article - resources are available to download (links are in my
paper)).



Discussion fell into conclusion (from set of people involved in discussion
only author of conjecture rejects this conclusion) that article proves that
every TSP tour can be represented in some BLP feasible solution, but there
is no proof in opposite direction.



After some discussion I have written another article "Why LP cannot solve
NP-complete problems" - it is available here:
http://arxiv.org/abs/cs.CC/0611008. Key point is that for plytope
representing NP-complete problem there are O(2^n) vertexes, polytope has
O(2^n) facets and that's why polynomial number of restrictions cannot "see"
them all. And if it omits some of them, then situation analogical to
presented in picture http://www.teycom.pl/diaby/eq2.png may occur.



Counter example is very simple and it bases on fact that variables and
equations in BLP model can "see" only three arcs in one variable. So taking
couple of "threes" we cannot distinct if there are the same or different
paths in it. If we consider that every variable refers to some correct
variables then we cannot be sure that their connection is still correct -
they are only connected by different sums of flow from, to node and set of
arcs.



Author didn't point any flaw in counter-example, continues to claim that it
is incorrect because "it is impossible"
(http://www.business.uconn.edu/users/mdiaby/tsplp/hofman/Ans_To_Hofman.pdf)
but no proof given. Author cannot run counter example using his source code,
because it is to large for him. I have proposed that I shall modify his
source code to produce only non-zero variables and only equations containing
at leas one non-zero variable (this makes number of equations less then 1
million) but code is still authors secret.



Below is example for better understanding of counter-example.



If anyone is interested in continuing this discussion - please do it here.



Best regards,



Radek Hofman



U¿ytkownik "Radoslaw Hofman" <radekh@xxxxxxxxx> napisa³ w wiadomo¶ci
news:<ek4h99$9v5$1@xxxxxxxxxxxxxxxxxxxx>...



It is easy to prove that it can be deceived



imagine flow on arc A->B - then it splits to four in next level C,D,E,F
then

it splits to reach next 4 cities we have G,H,I,J:

A->B->C->G

A->B->C->H

A->B->C->I

A->B->C->J

...

A->B->F->J



Then again to four cities K,L,M,N

A->B->C->G->K

A->B->C->G->L

A->B->C->G->M

A->B->C->G->N

...

A->B->F->J->N



Then again to next three cities O,P,Q,R



So in node O we have flow from C,D,E,F form level 2, and from G,H,I,J from

level 3, and from K,L,M,N in level 4.



Now we have flow to C,D,E,F - is it legal? Of course it is - to node C it

should send flow from D, E, F from level 2 and so on.



Then it happens again - we reach level 8 and once more want to go to

C,D,E,F - it is still OK - flow which visited C in level 2 and D in level
5

can be directed to E or F in level 9.



And what will happen if we try to repeat it for level 12->13? Then your

algorithm fails. Because using z_ARC1_ARC2_ARC3 you cannot prevent
reaching

same city. If then your model is asked about flow from z_C->G_D->H_***
then

it will allow flow on stages 9 and 13 reach same cities. Now you can
prevent

it having z for levels 4->5 and 8->9 but in this case you cannot prevent

flow from stage 2 reach same cities because it is beyond scope of

recognition...



Try to write down this example and assume that on every level split is

proportional. If you add some lead-in (4 cities before A with single path)

and lead-out then it will be feasible for your model. In this case it will

not be optimal - but will be feasible what proves that NOT EVERY BLP

SOLUTION CONSISTS OF VALID TSP TOURS. Mine counter example shows such

situation but it presents version where feasible solution is better then

optimal TSP, but if you want only feasible solution having nothing in
common

with TSP tours then here it is :).



How large instances can your algorithm solve? Maybe I shall prepare
smaller

example showing feasible (not better then optimal) solution having

properties I mention - It could have only 20 nodes.



Best regards,



Radek Hofman








.