My LP Formulation of the TSP: Conclusions

(I had posted this information earlier today. But, for some reason,
the thread disappeared! So, I am posting again...)


For those who may be interested, a revised version of my paper is
available at: http://www.business.uconn.edu/users/mdiaby/tsplp.

With respect to the last discussions in this forum regarding my paper,
After further checking, I found that in the absence of constraints
2.12 - 2.13 (of the previous version), the flow connectivity
constraints on the y-variables *only* (Constraints 2.8) were not
sufficient for one of the steps of Proposition 2 (Specifically,
Expression 2.28) to always hold. Hence, constraints 2.12 - 2.13 were
indeed *not* redundant in the previous version of the paper.

In the revised version, the flow balance equations on the z-variables
(that were assumed to implicitly hold in the previous version) have
been explicitly added. (It is easy to verify that these constraints
would also be violated for any solution "constructed" using Hofman's
approach).

All the theoretical developments remain the same.

The revised model contains a lot of redundancies. But it is
*absolutely* safe in the sense that each step of each proof in the
paper follows directly (i.e., without the need any unstated constraint
to hold implicitly).

(I decided that it would be better to leave the "finessing" of the
model for a another time).

//MD

.

Relevant Pages

  • Re: Declarative constraints in practical terms
    ... eliminate single points of failure based on a risk assessment. ... constraints are, ... redundant systems for quality sake are one thing. ...
    (comp.databases.theory)
  • Re: Declarative constraints in practical terms
    ... It sounds like you want not only multiple places where constraints are ... redundant systems for quality sake are one thing. ... software development, but I'm not sure exactly what that something is. ...
    (comp.databases.theory)
  • Re: My LP Formulation of the TSP: Conclusions
    ... constraints on the y-variables *only* ... Could you tell us for what N 2.13 is not redundant? ... so you do not include them (refer to my original counter-example ...
    (comp.theory)
  • Re: My LP Formulation of the TSP: Conclusions
    ... I found that in the absence of Constraints ... Could you tell us for what N 2.13 is not redundant? ... so you do not include them (refer to my original counter-example ... We should rely on the mathematics of the situation for the "why?'s". ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... that constraints 2.12-2.13 are not redundant in my model after all, ... you are missing another constraints which would be redundant for smaller n, ... possibly invent - but unless you understand WHY you will not be able to ... "mathematical idiot" appeared to be smarter then smartest model you have ...
    (comp.theory)