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

Mr. JARFO - oVERALL, I THINK THAT, MAY BE, YOU SHOULD READ THE PAPER
MORE CAREFULLY. PLEASE, SEE MY COMMENTS FOLLOWING YOUR STATEMENTS
BELOW. BEST. //MD


jarfo wrote:
> 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.

HOW LARGE WOULD "N" HAVE TO BE BEFORE THIS HAPPENS? ALSO, WHY WOULD
THIS NOT HAPPEN WHEN "N" IS "SMALL" (WHATEVER THAT MAY MEAN)?

>
> 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.
>
MY FORMULATION DOES NOT ALLOWS FOR NEGATIVE FLOWS. SO THIS SEEMS QUITE
NON-SENSICAL.


> Your proof fails because in general you can have a solution that has
> nothing to do with a path,

MY FORMULATION ONLY ALLOWS FOR PATHS AS SHOWN IN THE PROOFS GIVEN IN
THE PAPER.


> so you can not suppose that after all the
> c.a.s.s paths has been identified and removed you will have a path.

I AM NOT "SUPPOSING" ANY SUCH THING. WHAT IS PROVEN IN THE PAPER IS
THAT AFTER ALL THE CASS PATHS HAVE BEEN IDENTIFIED AND PROPERLY
ACCOUNTED FOR, EITHER WHAT REMAINS (IF ANYTHING) IS ALSO A CASS PATH OR
THE SOLUTION AT HAND IS INFEASIBLE, THE COMMON-SENSE IMPLICATION OF
THAT BEING THAT ANY FEASIBLE SOLUTION HAS TO BE A COLLECTION OF CASS
PATHS.


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.

THIS STATEMENT OF YOURS IMPLIES THAT THERE WOULD BE A FEASIBLE SOLUTION
TO THE MODEL THAT CONTAINS NO CASS PATH, SINCE ONLY NON-NEGATIVE
VARIABLES ARE ALLOWED IN THE MODEL. HOWEVER, THAT IS NOT POSSIBLE FOR
THE MODEL BECAUSE THERE ARE CONSTRAINTS IN THE MODEL THAT REQUIRE THAT
EVERY FLOW "VISIT" EVERY CITY.


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

THE MODEL DOES NOT ALLOW FOR NEGATIVE FLOWS. (OR MAY BE, I DON'T
UNDERSTAND WHAT YOU MEAN BY "NEGATIVE FLOWS"? PERHAPS, YOU COULD
CLARIFY THIS AND ALSO SHOW HOW IT APPLIES TO MY MODEL?)
>
>
> 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.

.