Re: Discussion regarding Mr. Diabys algorithm

Next part:


U¿ytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisa³ w wiadomo¶ci
news:1163034546.735224.23890@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
SECOND SET OF RESPONSES I GAVE YOU ALREADY

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?

I have responded that problem is that you claim to have model with
restrictions on what is counted to sum. It isn't very hard to prepare absurd
example... it is harder to prove
that every BLP solution consists ONLY of TSP-tours

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.

I completlee agree that every TSP correspond to some BLP, but not in other
direction. Figure 2.2 is example for BLP for two TSP. In mine paper fig 13
shows BLP with no corresponding TSP.

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.

==> nice idea... but it is the same with expressing 3-D or 4-D objects using
2-D - how can you be sure that your "picture" isn't missing something

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.

But it is still only "picture" of real object. Your function does not
react on target function shape, we can then prepare such target function
that for very complex polytopes your "assignment polytope" is
a) loosing important factors of TSP polytope in area where optimal solution
should "cut" polytope (if your "assignment polytope" has only n^9 vertexes)
b) your BLP model cannot express even this polytope because it still has
more then n^7 facets

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

You claim to have proved that BLP can represent TSP - I can agree with that
(TSP => BLP). But what you didn't prove is <=> relation. Or we may say other
direction BLP => TSP.

Cheers,

Radek Hofman


.

Relevant Pages

  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... for BLP even z's are not enough. ... Propositions you mention DOES NOT INCLUDE WHAT I AM ASKING OF! ... Intuitive sense - TSP polytope has n! ... It is obvious that your model is only approximation of polytope. ...
    (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)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... Polytope, since I am actually reformulating an Assignment Polytope! ... you stand comes from certain river and reached destination river using ... You can only check if % of water in certain channel comes from ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... "LP formulation has the structure of the Assignment Polytope". ... If we consider assignment polytope as such that has every row and column ... produces incorrect solutions... ... is equivalent to another NP-complete problem, so reformulation of TSP to 0-1 ...
    (comp.theory)
  • 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)