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


Jennifer Anderson wrote:
> Dear Dr. Diaby,
>
> Are you sure the algorithm isn't just getting lucky, landing on 0,1
> solutions, and that there's no guarantee that the optima achieved is
> always 0,1? This can happen with lots of integer programs formulated
as
> linear programs.
>
> For instance, in your proof of Proposition 2, you assume that the
path
> that is not c.a.s.s. has positive flow. Why can't it have a negative
> flow, as Jarfo pointed out before and other paths which are not
> c.a.s.s. have positive flows to cancel it out?
>
> - 1/M x ( 1 1 1 0 0 0 1 1 1 0 0 0 1 1 1 .......)
> + 1/M x ( 1 1 1 .....................................)
> + 1/M x ( ...............1 1 1...................... )
> + 1/M x ( ..............................1 1 1....... )
>
> In his chart, we have an example, the first vector that could have a
> negative flow and not be c.a.s.s. but not violate your "constraint
> (2.22)".
>
> Jenny

Dear Jenny - All variables in my model are non-negative. So, I am not
sure I understand what you mean by "negative flow." I think it would be
helpful if you could indicate to me exactly which variables in my model
would be negative to correspond to the "first vector" in your chart
above, and how and at what stage of the simplex procedure such
negative variables would arise. //Moustapha.

.

Relevant Pages

  • Re: Hydraulic Diameter for Moody, Fanning, Darcy
    ... in simple pipe flow friction factor charts? ... That depends on the chart. ... Does the chart have flow rate or velocity as an input? ...
    (sci.engr.mech)
  • Re: Best Layout?
    ... I am working on a project where I want to create somewhat of a flow ... representing each box in the "flow chart" with a JPanel. ... What I am looking for is a layout where I can say ...
    (comp.lang.java.gui)
  • Re: Chart Property (e.g.: .HasTitle) reset fails with run-time err
    ... There are many things about the Excel chart object and how it is exposed to ... worksheet objects have distinct names (one is Fuel and one is Flow). ...
    (microsoft.public.excel.programming)
  • Re: Importing modules
    ... Fredrik Lundh ha scritto: ... >> To understand a program, however, you need also a flow chart... ... > so understand a carefully designed modular component structure, ...
    (comp.lang.python)
  • Re: Importing modules
    ... >> To understand a program, however, you need also a flow chart... ... > so understand a carefully designed modular component structure, ...
    (comp.lang.python)