Re: P=NP: Linear Programming Formulation of the TSP

Dear Mr. Diaby

There is nothing special in you IP formulation of TSP and the
corresponding LP relaxation. For large N, the LP relaxation will surely
have extreme points that are no TSP tours and the associated cost may
be lower than the cost of the optimal TSP tour. Therefore, with LP
relaxation you will not be able to solve the associated NP-complete
decision problem.

Your PROPOSITION 2 is not very clear, but I understand that by "a
collection of c.a.s.s paths" you mean a linear combination with
positive weights (flow) of (solutions corresponding to) c.a.s.s. paths.

That is false. You can have a linear combination of positive and
negative "flows" if that results in a solution with non-negative values
for each LP variable.

You can easyly construct such a solution as follows.

- Choose any c.a.s.s. path and assign a negative flow of -1 to it.
- Add the necesary different c.a.s.s paths with flow 1 to cancel all
the negative values correspondig to the first c.a.s.s path. It is easy
to show that for large N you can allways find the appropiate c.a.s.s.
path that cancel one o more of the remaining negative variables.
- Renormalize the weight of each vector to obtain a total flow of 1.

Your proof fails because in general you can have a solution that has
nothing to do with a path, so you can not suppose that after all the
c.a.s.s paths has been identified and removed you will have a path. In
the example just mentioned you will not be able to extract a single
path from it, if you want to keep the remainig vector with positive
variables. That is, you can not identify a single c.a.s.s. path using
only positive variables.

On the other hand is quite obvious that all the variables in (2.22) has
to be zero in any feasible solution. And if you remove feasible
solutions from a solution, those variables will remain to be zero. But
that has nothing to do with a proof os PROPOSITION 2.

PROPOSITION 3 and 4 are false since PROPOSITION 2 is false. The flows
sum 1, but you can have positive and negative flows.


moustapha.diaby@xxxxxxxxxxxxxxxxxx wrote:
> Dear Fellows of the Community:
> Some weeks ago, in the process of extending my LP formulation of the
> TSP to other combinatorial problems, I found that the model needed
some
> additional constraints. I have revised the model and paper
accordingly.
> I would like to invite you, if I may, to take a look at the revised
> model and paper at: http://www.business.uconn.edu/users/mdiaby/TSPLP.
> Any comments would be highly appreciated. Regards.//MD.

.