My LP Formulation of the TSP: Conclusions


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* (i.e., Constraint 2.8) were not
sufficient for one of the steps of Proposition 2
(Specifically,Expression 2.28 in the proof) 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 I had assumed would 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 produced using
Hofman's "construction" approach).

All the theoretical developments remain the same. The final model
contains a lot of redundancies, but I have decided it is better to
leave the "finessing" of the model for a later time.

Best.

//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)