Re: Another LP model for TSP (by S. Gubin)


Uzytkownik "Zhu Guohun" <ccghzhu@xxxxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1163689528.557202.300350@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Is the idea of this paper orignal ?
==> I don't want to judge but... if one tries to find LP definition for TSP
then in natural way will get to such model... it means that autor may have
discovered it with no influence from other papers :)

There has been a paper pubilished in Chinese about formulation the
Hamiltonian cycle problem with Integer constaints programming (The
title of the paper is 'Necessary and Sufficient Conditions for
Hamiltonian Based on
Linear Diophantine Equations') whose idea is very similar.
please ref:
http://www.informatics.org.cn/doc/ucit200606/ucit20060610.pdf.
As I know, the author of this paper had also completed a draft on
Hamiltonian cycle problem in polynomial time on directed/undirected
graph with the linear system equations last December, which claims
that the complexity is no more than O(n^3) to determine if a Hamilton
cycles exist or not and that to obtain a solution if one or more such
cycles exist no more than O(n^4).
The paper had been review by two professors (one is Japanese, the other
is Canadian) . they said it is not clear enough by mathematics proof
so that the author was asked to think more about it.
Mr. Gubin,are you sure your idea is orignal? and if it were,how did you
get your inspiration?
==> as I mentioned above... this definition is quite obvious... and for me
is quite obvious that it leads to nowhere :)

Working with TSP looking for LP definition makes one think about nodes
(that's Gubin model) or arcs (taht's Diabys mode). Then authors find out
that their one-dimensional models are not capable of expressing correct
solutions... so they are multiplying model - for every object they
"memorize" sub-model. Again - it isn't enough so they get to next dimensions
generating next sub-model. Such approach is only "escape" from real problem,
which is uncapability of first level model to be correct. Reformulation to
sub models where each of them is nothing more but nested first level model
cannot help it... It is always possible to build counter-example...

See: http://arxiv.org/abs/cs.CC/0611008

I have looked inside article you provided link for... and I saw nothing - is
it in English? or it uses some chinese fonts?

Best regards,

Radek Hofman


.