Discussion regarding Mr. Diabys algorithm

Hi all,

Below is discussion I find very interesing, and I think should be
publicated (author of discussion didn't know how to start thread in
USENET). Answer and discussion will be send as reply.


>>>>>>>>>>>>>>>>>>>>>>>>>>>
From: #DEEPAK PONVEL CHERMAKANI# [mailto:deepakc{}pmail.ntu.edu.sg]
Sent: Friday, November 03, 2006 9:27 AM
To: radekh{}teycom.pl; tchow{}alum.mit.edu; tchow{}umich.edu;
tchow{}lsa.umich.edu; moustapha.diaby{}business.uconn.edu
Subject: Regarding Diaby's work on the TSP
Importance: High

Dear Sir Rodaslaw Hoffman, Sir Tim Chow, and Sir Diaby,

I am Deepak. I am Chairman of the "Brain Modeling / Intelligent
Systems" Special Interest Group of MENSA Singapore -
www.mensa.org.sg/sig

I have so far completed my Bachelors Degree at Nanyang Tech Univ,
Singapore, which I completed in 2003. I am currently working as a
Software Engineer.

I have read Dr. Diaby's work, and have also read the postings at:
http://groups.google.com.nf/group/co...lnk=raot&hl=en

I would like to share with all of you, regarding what I think about
Diaby's work. I have basically written what I think is a shortened
version of Diaby's algorithm.

Please read VERY CAREFULLY ALL SEVEN steps of the Algorithm in the
attachment.

I hope my attachment is able to answer the below comment made by Sir
Hoffman in the google posting.


COMMENT made by Sir Hoffman on 27 Oct 2006:
-------------------------
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?
-------------------------


please feel free to give me your opinions via email on what I have
said. Or pls tell me how may I perform a posting in the google website.
So that we may discuss on the google website.

Best Regards,
-Deepak


>>>>>>>>>>>>>>>>>>ATTACHEMENT>>>>>>>>>>>>>>>>>>> >>

Algorithm of Dr. Diaby -
http://www.business.uconn.edu/users/mdiaby/tsplp/

1.) Formulate the TSP's constraints as a Linear Program (LP), with
polynomial number of variables.

2.) Within polynomial time, the LP generates a single SOLUTION. This
SOLUTION represents all the optimal solutions of the TSP. But this
SOLUTION is by itself not a TSP tour .... it is only a result generated
by the LP.

3.) Within polynomial time, one can systematically generate a single
optimal TSP tour from this LP's SOLUTION (this is true whether the TSP
has polynomial number of optimal tours, or whether the TSP has an
exponential number of optimal tours).

4.) Within polynomial time, one can systematically generate a
polynomial number of optimal TSP tours from this LP's SOLUTION (this
is true whether the TSP has polynomial number of optimal tours, or
whether the TSP has an exponential number of optimal tours).

5.) Within exponential time, one can systematically generate an
exponential number of optimal TSP tours from this LP's SOLUTION (this
is true if the TSP has an exponential number of optimal tours).

6.) But since the definition of the TSP is to find at least one optimal
tour, therefore there is no need to even care about steps 4, and 5,
mentioned above. We only need to care about Step 3.

7.) It follows from the above 6 steps that therefore, Diaby's
Algorithm is able to find at least one optimal tour to any given TSP,
within polynomial time.



The major drawback, according to me, with Diaby's paper, is that
there is no necessity for him to draw parallels with "flows" and
"layers". I know that Dr. Diaby's intention may have been to try
explaining the concept better in terms of "flows" and "layers".
But according to me, this explanation in terms of "flows" &
"layers" is only creating confusion, because it is difficult for
one to visualize the fact that the LP SOLUTION represents all the
optimal TSP tours.
By explaining in terms of "flows" and "layers", it is difficult
to imagine that 1,000,000,000 rivers will join together and still be a
resultant-river with the size of only 100 rivers, but where the
resultant-river still represents all the 1,000,000,000 rivers. There is
no way of explaining this concept in terms of multi-commodity flows. In
fact, I cannot imagine is there is any "real-life parallel" of
explaining this concept. So I feel Dr. Diaby should remove this
explanation of "flows" and "layers".
If I were to be Dr. Diaby, I would simply write my paper within 8
pages, explaining all the 7 points mentioned above. Finally, there is
no need to even show experimental result with the 7-city and 8-city
TSP, because that's not needed. This is a proof, and so no
experiments need support this.


Otherwise, in my opinion, Diaby's algorithm is able to Polynomially
solve the TSP, and the TSP is Polynomially solvable.

- Deepak Ponvel Chermakani, IEEE Member, 4 Oct 2006
( Chairman of MENSA Singapore's Brain Modeling Group -
www.mensa.org.sg/sig )

From: #DEEPAK PONVEL CHERMAKANI# [mailto:deepakc{}pmail.ntu.edu.sg]
Sent: Friday, November 03, 2006 1:11 PM
To: Radoslaw Hofman; tchow{}alum.mit.edu; tchow{}umich.edu;
tchow{}lsa.umich.edu; moustapha.diaby{}business.uconn.edu
Cc: sgubin{}genesyslab.com
Subject: RE: Regarding Diaby's work on the TSP


Dear Sir Hofman,

Thank you for your expert comments on Diaby's and Gubin's paper.

Your explanation is very good in:
http://www.teycom.pl/docs/Why_LP_can...omial_time.pdf

I now understood that LP cannot be used to prove that P=NP.

Regards,
-Deepak


-----Original Message-----
From: Radoslaw Hofman [mailto:radekh{}teycom.pl]
Sent: Fri 11/3/2006 4:25 PM
To: #DEEPAK PONVEL CHERMAKANI#; tchow{}alum.mit.edu; tchow{}umich.edu;
tchow{}lsa.umich.edu; moustapha.diaby{}business.uconn.edu
Cc: sgubin{}genesyslab.com; 'Radoslaw Hofman'
Subject: RE: Regarding Diaby's work on the TSP

Hi,



Please refer to his paper - I haven't prepared extra counter example
for his
paper yet, but as you look into it - method is nearly the same, except
that
author uses Gauss-Jordan exclusion for his solution, and there are only
n^2
variables (not n^9 like in Diaby's work).



This method is much weaker - for large instances.



Number of linearly independent equations is (in authors worlds) O(n^3)
for
n*m variables what is not true. If we look at formula at page 4 there
is
n^2+2*n+2*n+n+nm=O(n^3)... well as far as I know definition of BigO it
should be O(n^2), but if we look closer at equations it is less then
that.
For example:

(5) - there are n columns in matrix, and equation is repeated for every
column, this means only n equations (not n^2)

(6) - 2, not 2*n equations (and it makes 2 equations from (5) be
linearly
dependant)



Now we can see that construction of Hamilton cycle requires to pick up
n
arcs, then we have n^2 variables (not n x m) and only O(n) equations.
It may
work only for very small n.



Author seems to have unclear idea - is he preparing instance for set of
equations or LP instance. Is it integer or decimal problem? No matter
what
answers are it simply cannot work... , and if it was tried on large
instances then it would be very clear (I will be able to perform check
when
author provides formulas for his equations).



Important thing in order to preserve linear independency is that if we
know:
sum of column, sum of row it can build up not 2*n linearly independent
equations but no more then 2*n-1.



Cheers,



Radek Hofman



_____

From: #DEEPAK PONVEL CHERMAKANI# [mailto:deepakc{}pmail.ntu.edu.sg]
Sent: Friday, November 03, 2006 11:19 AM
To: Radoslaw Hofman; tchow{}alum.mit.edu; tchow{}umich.edu;
tchow{}lsa.umich.edu; moustapha.diaby{}business.uconn.edu
Subject: RE: Regarding Diaby's work on the TSP



Dear Sir Radek Hofman,

Thank you for your expert comments on Diaby's work.

Sir Hofman, Could you also please give me some website links, in which
you
have made comments on the following additional paper:

In October 2006, Sergey Gubin tried to prove P=NP by constructing a
polynomial time algorithm for the directed Hamiltonian cycle problem.
His
paper is available at http://arxiv.org/abs/cs.DM/0610042. The title of
the
paper is "A Polynomial Time Algorithm for The Traveling Salesman
Problem".

I got the above from http://www.win.tue.nl/~gwoegi/P-versus-NP.htm

Unfortunately, the link to your "Comments" on Sergey Gubin's paper, is
not
working.
I eagerly await your early reply.

Thank you,
-Deepak


-----Original Message-----
From: Radoslaw Hofman [mailto:radekh{}teycom.pl]
Sent: Fri 11/3/2006 2:54 PM
To: #DEEPAK PONVEL CHERMAKANI#; tchow{}alum.mit.edu; tchow{}umich.edu;
tchow{}lsa.umich.edu; moustapha.diaby{}business.uconn.edu
Cc: 'Radoslaw Hofman'
Subject: RE: Regarding Diaby's work on the TSP

Hi,

To use USENET you may register as GoogleGroups user - I use this way
when
I'm travelling because no USENET server allows to post messages from
cell-phone net in Poland.

Getting to your paper:
1) It is formulated first as INTEGER LINEAR PROGRAMMING
1.a) Then it is claimed to be equal to LP
2) OK
3) No... It is only possible when SOLUTION is correct. In fact TSP is
decision problem - you do not have to know exact solution, you have to
give
correct answer "If solution is equal to X", and what I can show is
example
that answer can be better then optimal for TSP
4) Same comment
5) Same comment
6) We don't have to care about 3 either because P and NP classes
consist
only from decision problems (with YES/NO answers)
7) No , it can find solution better then optimal for TSP. If optimal
solution is X, and found by LP is lower then X then you cannot find any
TSP
tour for LP solution

About rivers example - remember that rivers are joining and splitting,
then
again joining and splitting... you cannot check if water far away from
where
you stand comes from certain river and reached destination river using
certain path. You can only check if % of water in certain channel comes
from
certain river. Imagine that you have river - then it splits to n
rivers,
then joins into one, then splits... ect. How can you be sure that there
exists at least one water drop which choosen certain path?

Please consider - if polytope defined in LP model hes expotential
number of
facials (no doubt that representing TSP polytope has this number), and
you
create polynomial number of restrictions (each referring to one facet)
then
you have to admit that some facet were omitted. If our target function
is
corresponding to this ommited facial then it will produce incorrect
answer.

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

And
http://www.teycom.pl/docs/Why_LP_can...omial_time.pdf

Best regards,

Radek Hofman

From: Moustapha Diaby [mailto:Moustapha.Diaby{}business.uconn.edu]
Sent: Friday, November 03, 2006 4:12 PM
To: Radoslaw Hofman; #DEEPAK PONVEL CHERMAKANI#; tchow{}alum.mit.edu;
tchow{}umich.edu; tchow{}lsa.umich.edu
Cc: sgubin{}genesyslab.com
Subject: RE: Regarding Diaby's work on the TSP


As I have been pointing out, Mr. Radoslaw is "missing the boat"
completely on my work! ...Why the model works has nothing to do with
probem size! The model works because there is a certain structure to
the the flows. It is only sufficient for such structure to *exist* in
any feasible solution.

I believe the difficulties for Mr. Radoslow's are due to his apparently
limited familiarity with Linear Programming.

(By the way, I am going to present the qap version of the work on
Wednesday at the INFORMS Conference in Pittsburgh... The paper has also
been accepted for the INFORMS Computing Society Meeting coming up in
January in Florioda --These may be opportunities for face-to-face
interactions...)

From: #DEEPAK PONVEL CHERMAKANI# [mailto:deepakc{}pmail.ntu.edu.sg]
Sent: Saturday, November 04, 2006 6:27 AM
To: #DEEPAK PONVEL CHERMAKANI#; Moustapha Diaby; Radoslaw Hofman;
tchow{}alum.mit.edu; tchow{}umich.edu; tchow{}lsa.umich.edu
Cc: sgubin{}genesyslab.com
Subject: RE: Regarding Diaby's work on the TSP
Importance: High


Dear All,

I just read the latest posting of Sir Radoslaw on
"http://groups-beta.google.com/group/comp.theory/browse_thread/thread/84ee8d0d661df004/b3621b540d9ab329?hl=en&"

In fact, Radoslaw's posting automatically answers my below-mentioned
Question. The answer to my below-mentioned Question is NO, because both
Diaby's model and Gubin's model are incapable of having the exact
picture of the polytope.

Their model DOES LEAVE out many vertexes in the polytope, when the TSP
has a large number of nodes. So it is possible to generate TSP
problems, where Diaby's model and Gubin's model give an inaccurate (and
absolutely wrong) answer.

And this is true, irrespective of whether the TSP has EXACTLY one
optimal tour, or whether is has a polynomial number of optimal tours,
or whether it has an exponential number of optimal tours.

I am now absolutely convinced that LP cannot be used to solve
NP-Complete Problems.
Thank you very much.

Regards,
-Deepak


-----Original Message-----
From: #DEEPAK PONVEL CHERMAKANI#
Sent: Sat 11/4/2006 10:03 AM
To: Moustapha Diaby; Radoslaw Hofman; tchow{}alum.mit.edu;
tchow{}umich.edu; tchow{}lsa.umich.edu
Cc: sgubin{}genesyslab.com
Subject: RE: Regarding Diaby's work on the TSP

Dear Sir Radoslaw:
Please kindly answer this important Question that I have:-
Will the Algorithm of Diaby/Gubin be able to always give a correct
YES/NO answer to the Hamiltonian Cycle Problem (HCP), within Polynomial
Time, if the HCP has EXACTLY one optimum tour ??? If the answer to my
Question is YES, please explain the reason. And if the answer is NO,
then also please explain the reason. I eagerly await your reply.

Dear Sir Diaby:
Thank you for your email. Yes I am sure the INFORMS conference is a
competent conference, but I think there is a difference between the
reviewing Quality of a conference, and the reviewing Quality of a
Journal. I myself earlier believed that you had identified the "correct
geometric pattern" of the TSP. But now after reading Radoslaw's paper
on
"http://www.teycom.pl/docs/Why_LP_cannot_solve_large_instances_for_NP-complete_problems_in_polynomial_time.pdf",
I find that what Sir Radoslaw is saying is very realistic. Within 4
pages, Sir Radoslaw has put it down very neatly and concisely,
regarding the transition from ILP to LP. Maybe your Algorithm may be
able to correctly identify within Polynomial time, if the Problem has
EXACTLY one optimum solution.

But I am not still sure about that yet....we will wait for Sir Radoslaw
to give his explanation on my above Question.
I hope I will get the opportunity to travel to this INFORMS Conference
in Jan 2007.

Thanks,
-Deepak

Hi,

Longer you claim that solution has nothing to do with instance size
then longer you keep yourself away from reality. Please read my papers
carefully (not as you did) and then we may discuss.

Maybe you will post me source code of your program - remember that I
have already implemented your method and source code is public
available - maybe you can point out errors in it? It works perfectly
for small instances but for large ones it produces false results - so
problem is not with structure - it is a problem with size.

You did not respond to argument that when polytope has O(2^n) facets
then your O(n^7) restrictions miss some of them. It is enough to
prepare target function which would have touched this facet "not seen"
by your model - it will produce false result:
see: http://www.teycom.pl/diaby/eq2.png and
http://arxiv.org/abs/cs.CC/0611008

It's a pity places you mention are to far for me... but I shall send my
comments to reviewers boards.

Cheers,

Radek Hofman

PS. I will move this discussion to comp.theory - hope you don't mind

On 4 Nov 2006 01:08:45 -0800, "Radoslaw Hofman" <radekh{}teycom.pl>
wrote:

>Hi all,
>
>Below is discussion I find very interesing, and I think should be
>publicated (author of discussion didn't know how to start thread in
>USENET). Answer and discussion will be send as reply.
>

Mr. Hofman, all this is very exciting, but from historical
perspective...

First attempt to solve TSP using Linear programming is as old as
Linear Programming itself and dates to early 50. This is described
in original Dantzig book that provides further references.

The difficulty is that a) TSP is integer problem: for each stop we
have to provide index to next stop, b) There are difficult to
implement constraints, especially "no sub tour" constraint that
eliminates solutions that consist of several isolated cycles.

Linear Programming is not INTEGER programming, i.e. if we relax TSP
removing the requirement for integrality, there is no guarantee that
solution will be integer (some problems, such as transportation
problem, posses the "integrality" property: if all data is integer,
then the solution is integer, even if solved using conventional LP).
Dantzig and company noticed this, and implemented sequential
procedure by adding additional constraints, named "cuts" after
non-integer solution was obtained. Unfortunately, they have noticed
that the number of these cuts will increase exponentially with the
size of the problem. Similar difficulty they encountered with "no
sub tour" constraint.

In other words, if someone wants to show that LP can solve TSP,
he/she must to show that a) solution obtained by standard LP is
integer, b) there will be no sub tours, c) to enforce a) and b)
increase of the complexity of the problem is reasonable.

Proving that TSP is equivalent to Integer Linear Programming doesn't
show anything: Integer Programming is NP-complete anyway..

A.L.

Radoslaw Hofman wrote:
> Your explanation is very good in:
> http://www.teycom.pl/docs/Why_LP_can...omial_time.pdf
>
> I now understood that LP cannot be used to prove that P=NP.

Hi I haven't been following these arguments about P ?= NP problems -b/c
I don't think it's sth to progress (!) in a newsgroup, but although I
appreciate your hardwork on your tech-report/paper kind of thing, this
result has been proven (in a generalized form) by Mihalis Yannakakis
almost 20 years ago, just to point out:
http://dx.doi.org/10.1016/0022-0000(91)90024-Y

I still think trying to prove old results on your own is good, no
offense.

Uzytkownik "tuncay tekle" <tuncaay{}> napisal w wiadomosci
news:1162667869.588797.60880{}f16g2000cwb.googlegr oups.com...

> I still think trying to prove old results on your own is good, no
> offense.
>

Of course :-). I've read other Yannakakis paper (Expressing combinatorial
optimization problems by Linear Programs Journal of Computer and System
Sciences, Volume 43, Issue 3, December 1991, Pages 441-466 Mihalis
Yannakakis) and its corollary isn't so strict that LP cannot be used to find
solution. Remember that Mr Diaby used Yannakakis paper to justify his
algorithm...

I referr mainly to Mr Diaby's work showing why his algorithm cannot be
correct - why if Yannakakis was so strict somebody is using exactly same
method and claiming that he proved that P=NP? Why such paper passes reviews
for conferences?

Cheers,

Radek Hofman

Hi,

I agree compleetly, BUT... there are some people which don't agree

> Dantzig and company noticed this, and implemented sequential
> procedure by adding additional constraints, named "cuts" after
> non-integer solution was obtained. Unfortunately, they have noticed
> that the number of these cuts will increase exponentially with the
> size of the problem. Similar difficulty they encountered with "no
> sub tour" constraint.

Well, Diaby overcomes this...

> In other words, if someone wants to show that LP can solve TSP,
> he/she must to show that a) solution obtained by standard LP is
> integer,

Yes, but if he claims it is optimal then in fact it is integer (no proof
needed)

> b) there will be no sub tours,

He claims that his restrictions forbid this

> c) to enforce a) and b) increase of the complexity of the problem is
> reasonable.

And this

Problem is... He is wrong (for sure) but we have to point out certain
equation/proof in his paper that is not correct. That is result of my work -
exact counter example

And don't forget that his paper received Merit Award on IMECS2006... Well...
But still he is wrong, and there is no better way to show it but counter
example .

Additionaly I show that no matter how exact cuts and restrictions you have
you will obtain result BETTER then optimal for TSP using LP - that's the
point because TSP in NP is decision problem - you do not have to know tour -
you have to answer question about its overall cost.

Cheers,

Radek Hofman

"Radoslaw Hofman" <radekh{}teycom.pl> writes:

>I referr mainly to Mr Diaby's work showing why his algorithm cannot be
>correct - why if Yannakakis was so strict somebody is using exactly same
>method and claiming that he proved that P=NP? Why such paper passes reviews
>for conferences?

Such paper passes reviews because of poor reviewing, which is a
big problem today, even with more specialised conferences.