Re: My LP Formulation of the TSP: Conclusions

On Mar 30, 3:59 pm, t...@xxxxxxxxxxxxx wrote:
In article <1175269178.977762.70...@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,

<moustapha.di...@xxxxxxxxxxxxxxxxxx> wrote:
So, may be *you* can explain to everybody what the "basic textbook
facts about the assignment polytope" are that Hofman understands?

For example, that it has integer vertices, and so an optimal integer
solution may be found by linear programming.

What Hofman is pointing out is that your claims about the TSP do not
follow from the properties of the assignment polytope, and that your
attempt to prove otherwise is broken.
--

OK, one more time:

This is what I said:

<< 5. Sometimes, Convex hull of LP relaxation = Convex Hull of IP.
This
is the case of the Assignment Problem, which my model is a
reformulation of. >>


This is what Hofman said in response:

<< In math language:
Set Of LP Feasible Solutions = Set of IP Feasible Solution UNION Set
of IP
not-feasible solutions
Set of IP not-feasible solutions = Set of solutions with value
between
lowest and highest cost of tour UNION Set of solutions with cost lower
then
lowest tour or higher then highest cost of tsp tour
You have to agree that if this last set is NOT EMPTY then solution is
incorrect (any of such solutions cannot be considered as combination
of
other solutions). You cannot prove that it is empty... I have showed
that it
is not empty. Conclusions?

.... but... where is proof that for Assignement Polutope yhis third
set
of those I have named is empty? >>


May be you can explain to everyone how these are not in contradiction
with what you have stated instead of putting words in Hofman's mouth?

Anyway, I think it would probably make all our lives easier if we all
just adopt a "put up" or "shut up" approach.

I am waiting to see Hofman's counter-examples (or yours for that
matter) for my model in the IMECS proceedings (since he says his
"construction" scheme did not depend on the removal of the "visit"
constraints from that model) and for my final model I just made
public.

//MD

.

Relevant Pages

  • Re: My LP Formulation of the TSP: Conclusions
    ... For example, that it has integer vertices, and so an optimal integer ... What Hofman is pointing out is that your claims about the TSP do not ... follow from the properties of the assignment polytope, ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... Assignment Polytope, where this solution comprises of all incorrect ... an invalid TSP tour). ... Radek Hofman ... Diaby must prove the above to deserve Clay Prize. ...
    (comp.theory)
  • Re: My LP Formulation of the TSP: Conclusions
    ... may be *you* can explain to everybody what the "basic textbook ... facts about the assignment polytope" are that Hofman understands? ...
    (comp.theory)