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

1.- When N is small your formulation has a number of constraints that
are greater of 2^N so you can have an exact LP relaxation then. That
is, you formulation is only exact when its complexity is greater than
brute force search.

2.- The total flow is, of course, positive. It is forced to be one. I
state that your formulation allows for a solutions formed by adding
c.a.s.s. paths with negative and positive "flows", because the sum can
still have positive values in all the variables, and a total flow of 1.
I repeat here the constructive proof of my first reply in a more visual
way:

You can have a solution formed by considering the following terms:

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

_________________________________________
0 <= xi <= 1

It is obvious that, if each of the lines (terms) corresponds to a
c.a.s.s. path, the resulting sum is a feasible solution under your (any
TSP) LP formulation. It also easy to see that such solutions exist
because you can allways find a c.a.a.s. path that compensate the
negative values of the first term in one or more of the remaing
variables.
¿Can you prove no solution like that is a feasible solution to your
formulation?

The LP formulation constraints the total flow and the total sum for
each real valued variable of the solution to be positive, but it DOES
NOT constraint the contribution of each c.a.s.s. in a solution as the
shown above.

.

Relevant Pages

  • Re: A Two-Level SOLVER ??
    ... I'm running Excel Solver from a macro. ... ....Subject to constraints: B18=1 ... The correct formulation of the problem should be, I think, something like: ... cells or a vector of cells. ...
    (microsoft.public.excel.programming)
  • P=NP: Linear Programming Formulation of the TSP
    ... in the process of extending my LP formulation of the ... TSP to other combinatorial problems, I found that the model needed some ... additional constraints. ...
    (comp.theory)
  • Re: optimization: nonlinear equations with constraints
    ... the constraints dictate that imaginary part of the eigenvalue must be same value and there is at least one real e-value. ... 1.Is it possible to use fmincon to solve this problem, if not possible, what method do i use? ... The formulation sounds a little funny working with imaginary numbers. ... You have to make sure that the values of your objective function and constraint violations are real. ...
    (comp.soft-sys.matlab)
  • Re: optimization: nonlinear equations with constraints
    ... the constraints dictate that imaginary part of the eigenvalue must be same value and there is at least one real e-value. ... 1.Is it possible to use fmincon to solve this problem, if not possible, what method do i use? ... The formulation sounds a little funny working with imaginary numbers. ... fmincon's active-set algorithm employs sequential quadratic programming. ...
    (comp.soft-sys.matlab)
  • Re: ip6600D (CLI-8) Ink Information
    ... If you are asking of the pigment black, I am sure it is the exact same ... formulation across all late model (since BCI3e) Canons. ...
    (comp.periphs.printers)