Re: My LP Formulation of the TSP: Conclusions

On Mar 30, 10:12 am, t...@xxxxxxxxxxxxx wrote:
In article <euiakm$co...@xxxxxxxxxxxxxxxxxxxxxxx>,

Radoslaw Hofman <rad...@xxxxxxxxx> wrote:
Well, you have repeated continously that "every thing was in your paper" and
it occured even to you that it was wrong. Still same arguments?

In this particular instance, Diaby seems to be under the (mis)impression
that you don't understand the basic textbook facts about the assignment
polytope.


Well, this is what Hofman wrote:

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?
<<

I responded by telling him to consider the Assignment Polytope:
You should look at Point 5 of my last post. <

to which he responded:

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


So, may be *you* can explain to everybody what the "basic textbook
facts about the assignment polytope" are that Hofman understands?

//MD

.

Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... polynomial time the question "does this TSP instance have a tour of ... TSP instance have a tour of cost <= C?"? ... The transformation of an arbitrary TSP into a TSP with a unique optimal ... in which Hofman says that we can convert this single ...
    (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
    ... of those I have named is empty? ... textbook. ... Ask Hofman to find it for you, since he needs to do the homework ...
    (comp.theory)