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



On Jan 24, 6:45 am, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
Answering to problems written by Diaby in presentation below:

http://www.business.uconn.edu/users/mdiaby/tsplp/hofman/Ans_To_Hofman...Page 11 - funny :)
I have written here SEVERAL times that I prepared example and used ONLY
variables which were not equal to zero. Further on I have prepared
constraints containing at leas one non-zero variable. Because whole flow was
designed "by hand" I can perfectly point which variables are zero.


In fact for 32 cities I have less then 1 million constraints contaning at
least one non-zero variable so it is computable even on my laptop in less
then 3 hours. So argument that I isn't possible to build counter example is
false (or Mr. Diaby claims that adding 32^7 equations 0=0 changes result
:-) ).




The sizes reported in my posted document for my LP formulation are for
variables and constraints that MUST be explicitly considered. (You can
easily check that it is not n^9 and n^7 for the variables and
constraints, respectively). For a 32-city TSP, my LP has more than 100
millions variables and 100 millions constraints. If you are only
considering about one million constraints, then there are more than 99
millions constraints that MUST be satisfied, but that you are not
checking. And, they are definetely not trivial equations... The same
is true of the variables.



For the first thing - page 3:

2. It is possible to completely describe a polytope with an exponential
number of extreme points using a polynomially-bounded number of constraints
For example: The Assignment Polytope
==> Assignment Polytope isn't some "magical oracle" allowing to find answer
for polynomial number of constraints. In fact polytope presented by Diaby is
symmetric polytope which is proved to be unable to solve NP-complete TSP
problem (see Yannakakis). So... What are we talking about?


We are talkiong about the difference between the assignment polytope
and the TSP polytope. As clearly shown in my paper, I do not deal with
the TSP polytope...



3. The LP relaxation of an IP can have have integral verticesunder certain
conditions (such as total-unimodularity).
==> Maybe, but Diaby violates these conditions because his polytope allows
to find incorrect solutions what is showed in my counter-example

Your "counter-example" is invalid for the reasons indicated in my
document.


If I was on INFORMS I would have asked Mr. Diaby to use 4 lines and make
restrictions for set of 4000 points in such way that target function (any
possible one) would always give correct result - it is obvious that it is
impossible. TSP polytope has 2^n facets - claiming that n^7 restrictions
coveres them for large n is... WRONG :)


You have this backward. And your confusion here is more in the realm of
"pure mathematics" than in "mathematical programming."
It should go like this: in k-dimensional space, the number of points
that can be defined by m linear equations is "Combination(m, k)". For
example, in 2-dimensional space, if you have 10 linear equations, then
those can define "Combination (10, 2)" points. The dimension of the
space in which my model is stated is 9. The number of linear equations
is on the order n^7. So the number of points that can be defined by
these equations is on the order of "Combination (n^7, 9)." Try
comparing to n! or 2^n.


//MD

//PS: I do not intend to continue thios discussion and will not respond
to this kind of "stuff" anymore.

.

Relevant Pages

  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... Answering to problems written by Diaby in presentation below: ... In fact for 32 cities I have less then 1 million constraints contaning at ... For example: The Assignment Polytope ... In fact polytope presented by Diaby is ...
    (comp.theory)
  • Re: F.Y.I. - Revised paper "P=NP: LP Formulation of the TSP"
    ... > cities, ... > constraints still dominates the number of possible paths. ... between Problem IP and Problem IP-bar in my paper is that *extreme ... polytope compared to the number of paths. ...
    (comp.theory)
  • Re: Hofman and Diaby talk about P=NP at INFORMS 2007
    ... variables and constraints that MUST be explicitly considered. ... In fact polytope presented by Diaby ... out that model can give incorrect answer - ... Your BLP model is such set of linear equations, ...
    (comp.theory)
  • Re: My LP Formulation of the TSP: Conclusions
    ... constraints from that model) and for my final model I just made ... While trying to prove it I have discovered factors showing that it is ... polytope" and let us discuss factors of YOUR polytope and WHY it is ... Yanakakkis to be incorrect) and remove it's symmetry (if there are two ...
    (comp.theory)
  • Re: P=NP: Linear Programming Formulation of the TSP
    ... > I believe I understand what Dr. Moews is trying to do perfectly. ... then the new polytope is not the same as the original one. ... >>>charaterize the original polytope in terms of these constraints as ... >>>want to identify and discard redundent variables and constraints ...
    (comp.theory)