Re: Hofman and Diaby talk about P=NP at INFORMS 2007


Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1170347936.814270.83870@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
On Feb 1, 10:56 am, t...@xxxxxxxxxxxxx wrote:
For the benefit of those who might be really interested in the truth,
here is another example:

Consider the constraints:

a + b + c = 3 (1)
b + c = 2 (2)
a, b, c nonnegative. (3)

If you leave out constraint (2) because you are only concerned about
"a", and "a" does not appear in it, you will mistakenly believe that a
= 3 is a feasible solution to this constraints set...

Feasibility in a math program is not such a naively simple affair as
Hofman believes: You must to consider all the constraints and
variables together (unless you can show hat those you "throw away are
redundant in the model).

I will give picture of my point using your example (despite of Tim Chow
comment about foolishness of this argument), so those who haven't verified
it yet will have clear view.

Diaby's model is something like this (I have changed right sides to zero as
in your model):
Minimize 2*a+3*b+5*c
a + b + c = 0 (1)
b + c = 0 (2)
a, b, c nonnegative. (3)

I claim that if we set (by assumption) b and c to zero then we can
completely remove them - not only from (2) but from every equation. Using
math from primary school dictionary: we substitute b and c with 0. We obtain
then:
Minimize 2*a+3*0+5*0
a + 0 + 0 = 0 (1)
0 + 0 = 0 (2)
a, 0, 0 nonnegative. (3)

Now, of course, we can get rid of zeros:
Minimize 2*a
a = 0 (1)
a nonnegative. (3)

And we have feasible soultion: a=0, b=0, c=0.... Maybe it isn't optimal (in
general this approach may not result in obtaining optimal solution - afer
setting some variables to zero we may not reach global optimum, but it is
not the point), but for sure it is feasible.

The same with counterexample I have prepared - I have assumed that most of
variables are zero, and omited them. I have also omited equations with no
non-zero variables left. That is why 32 cities example became solvable on
standard PC. Maybe my counter example does not produce optimal solution for
32 cities... but certenly it is feasible and better then optimal TSP tour -
what else do we need?

Best regards,

Radek Hofman




.

Relevant Pages

  • Re: P=NP: Linear Programming Formulation of the TSP
    ... >> completely explained why the y_'s can be taken to be zero. ... >> the optimal solution must be in the subspace where each y_is ... Since these constraints are ... >> David Moews ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... David Moews wrote: ... > completely explained why the y_'s can be taken to be zero. ... > the optimal solution must be in the subspace where each y_is ... Since these constraints are ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Therefore, the optimal solution must also have finite objective function, ... the optimal solution must be in the subspace where each y_is zero. ... Since these constraints are ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Therefore, the optimal solution must also have finite objective function, ... the optimal solution must be in the subspace where each y_is zero. ... Since these constraints are ...
    (comp.theory)
  • Re: a question regarding optimization theory
    ... all unknowns .....my problems is more like an undetermined linear ... equations but i have some constraints to the solutions of the ... 1)all the x1 ....x6 must be positive and non zero ... phrase accordingly. ...
    (sci.math.num-analysis)