Re: Discussion regarding Mr. Diabys algorithm



by lots of people like Bryan
Olson, David Moews, Pat Shanahan, etc.


A rose by any other name....


Here are answers I have basically given you already. The paper is a
linear programming paper. I do not how to express these ideas in any
simplier terms. It is really as plain as possible for the context. If
any of those reading this thread does not understand this, then they
are definitely not qualified to attempt judge my paper (I don't mean
this in patronizing way, but I feel I need to be blunt enough).

My advice is if you don't understand, before you assume it is wrtong,
take it to someone who may be able to translate it to you in
face-to-face context. Talk to whoever has a reasonable amount of
*expertise* in mathematical programming."

Otherwise, you are asking me to explain things to you in say, Hebrew,
when we are in a context where everybody is supposed tyo know, say
English, and English is the only language I can speak.


FIRST SET OF RESPONSES I GAVE YOU ALREADY
Hofman's 2 Questions are:-

QUESTION ONE: - Is your Algorithm capable of pinpointing all (N!) TSP
tours, if every tour has equal length ??? The answer is obviously NO,
because in the overall picture, your Algorithm involves a Polynomial
number of variables. I know that Linear Programming guarantees to find
atleast one optimal tour, within Polynomial time, by walking across the
vertexes of your new Assignment Polytope that has Polynomial size.
However, then that leads to Question 2.
The issue is formally addressed by Proposition 1 of the paper: No TSP
tour is excluded from the feasible set of the IP formulation (see
Proposition 1 and its proof). The feasible set of the LP relaxation
includes that of the IP and must therefore include all the TSP tours.

QUESTION TWO: - Is it possible for your Algorithm to give the correct
solution for the CONVEX COMBINATION OF PATHS, but where EACH SINGLE
PATH IN THIS COMBINATION is a wrong solution ??? According to me, this
is possible because you have not explicitly proved this anywhere in
your paper. Yes, I will believe you only if you write a new proof in
your paper, stating that it is never possible for your Algorithm to
give the correct solution for the CONVEX COMBINATION OF PATHS, but
where EACH SINGLE PATH IN THIS COMBINATION is a wrong solution.
No. If you examine the positive components of any feasible solution you
must find that they have the structure described in Proposition 2 (That
is what the mathematics say -- And, I am quite comfortable with the
correctness). With such a structure each vertex of the polytope
described by the constraints of my model corresponds to a TSP tour
(Note I am saying "corresponds to", not *is*: the solution needs to be
properly "interpreted" because I am not dealing with *the* TSP
polytope). This is what is proven in either Proposition 3 or 4 (I don't
have the paper in front of me, but its the proposition about BFS's and
TSP tours). Each corner of the polytope corresponds to a TSP but has
several alternative algebraic representations in terms of what we call
in LP lingo, Basic Feasible Solutions. So, everything you are asking
for above, is already in the paper.

Finally, I want to make something very clear. I am subjecting myself to
all this for no other reason than out of my desire to be a "good
citizen" of whatever your scientific community is, and into which I was
"dragged" unwillingly. Otherwise, most of th opinions that have
expressed have absolutely no value for me: all these debates would be
trivial matterrs to beginners that have gonme through a few
fundamentals in my area of expertise (OR)...

I really have nothing more to contribute here on these issues apart
from what is below and what is the paper. "Everything" is *really* in
the paper...



SECOND SET OF RESPONSES I GAVE YOU ALREADY

OK, I am still getting emails... Hopefully, this will finally stop
them.

Consider this:

I say (see Proposition 4 on page 18 and the discussion just before it):


"Given a number, say 20, there exists even numbers, say 10 and 30,
such that 20 is the convex combination of those even numbers."
(Clearly, this is true since 20 = .5*10 + .5*30)

Hofman comes back and says:

"I found a counter-example to Diaby statement (above): I found odd
numbers such 20 is the convex combination of those numbers. In fact,
here it is: 20 = .5*21 + .5*19 !!!!"

I hope you get the absurdity?

To convince yourselves further, please, look at Figure 2.2. The graph
there contains 4 paths. Provided lambda(1,1,1) = lambda(1,2,1) = .5,
the solution shown is a convex combination of several pairs of paths
through that network, but only if path is defined in the conventional
graph theoretical sense. By the notion of "path in (y, z)"
introduced in this paper (page 14), is more complex than the
conventional graph theoretical sense.

As to Yannakakis: he (and other people before him) that address the
issue of the TSP polytope, here is some information that may be useful
to some of you:

1) References are given in my paper where you can see a precise
definition of what is meant by "TSP polytope."

2) Just because the problem being modeled is a TSP does not
automatically make the polytope associated with the model *the* "TSP
polytope" (there is only *one* "TSP Polytope")

3) A common practice in the OR (Operations Research) community is that
if the polytope you are working on is is a "hard one" (like *the*
TSP polytope), you try to see if you cannot express the same problem
over what we call a "friendlier" polytope. Just like you may want
to use "transforms" for your differential equations.

4) The polytope over which I am expressing the TSP optimization problem
in my modeling approach is the one we in the OR community call *the*
"Assignment Polytope."

The Assignment polytope has been studied as much, if not more than, the
TSP polytope, in the OR literatute.

The Assignment polytope is * very*, *very* different from *the* TSP
polytope.

My modeling consists of formulating the TSP optimization problem as a
math ptog. Problem over *the* assignment polytope expressed in higher
dimension.

So, the polytope of my model has nothing to do with *the* TSP polytope.

.

Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... atleast one optimal tour, within Polynomial time, by walking across the ... vertexes of your new Assignment Polytope that has Polynomial size. ... The feasible set of the LP relaxation ... solution for the CONVEX COMBINATION OF PATHS, ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... simplier terms. ... I know that Linear Programming guarantees to find ... atleast one optimal tour, within Polynomial time, by walking across the ... vertexes of your new Assignment Polytope that has Polynomial size. ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... tour contains the edge and is 0 if the tour does not contain ... With this definition it is known that the TSP polytope has ... one on the cities in S and one on the cities in T. This ... set of facets which is easily computable (and therefore of polynomial ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... The usual definition of the TSP polytope for n cities is ... tour contains the edge and is 0 if the tour does not contain ... set of facets which is easily computable (and therefore of polynomial ...
    (comp.theory)
  • Re: (non)complete graphs of polytopes and (non)unique decomposition as a convex combination of verti
    ... graph as adjacency graph, ... a polytope with a noncomplete graph as adjacency ... points can be partitioned into two blocks whose convex hulls ... A polytope whose vertex adjacency graph is complete is a simplex. ...
    (sci.math)