A reply to Moews on Diaby contradicting Yannakakis

From: Moustapha (moustapha.diaby_at_business.uconn.edu)
Date: 11/11/04

  • Next message: Deokhwan Kim: "Re: Decision Problem and Optimization Problem" 
    Date: 10 Nov 2004 22:16:38 -0800

    A Response to Moews on: "Diaby's claim contradicts Yannakakis's 1988
    result"
                                   (by M. Diaby)

    I thank Dr. Moews for his exposition entiled: "Diaby's claim
    contradicts Yannakakis's 1988 result," regarding my paper entitled:
    "P=NP: Linear Programming Formulation of the Traveling Salesman
    Problem." I believe the following observations are in order.

    First, the x(ij) variables in Dr. Moews' presentation are ill-defined
    with respect to the overall optimization problem in my paper, in the
    sense that they cannot be used for the equivalent expressions of
    polytopes described in Yannakakis (p. 442).

    Also, it is ALWAYS possible to add any number of redundent variables
    and constraints to any Mathematical Programming Problem (MPP) without
    changing the optimization problem at hand.

    Either the constraints developed by Moews using his x(ij) variables
    define new facets of the original LP polytope or they don't. If they
    do, then the new polytope is not the same as the original one. If they
    don't, then they are redundent with respect to the original polytope.
    In either case, it seems clear that it would be inappropriate to
    charaterize the original polytope in terms of these constraints as
    Moews does.

    Overall, Dr. Moews' approach flies in the face of the basic,
    common-sense idea of "pre-processing." In general, it seems one would
    want to identify and discard redundent variables and constraints of
    any Mathematical Programming Problem (MPP) as a first step, before
    attempting to solve it or study its properties. It is nonsensical to
    add irrelevant, redundent variables and constraints to a problem and
    then infer properties of that problem based solely on these. In fact,
    Yannakakis' developments are based –appropriately- on "minimal LP
    descriptions" of polytopes (see page 448).

    Clearly, unless it can be shown that the proofs presented in my paper
    are erroneous, the initial polytope in the paper is SUFFICIENT in the
    sense that nothing needs to be added to it -although not necessarily
    minimal- in order for it to describe the TSP polytope, and it is NOT
    symmetric in the sense of Yannakakis, as recognized by Moews himself.

  • Next message: Deokhwan Kim: "Re: Decision Problem and Optimization Problem"

    Relevant Pages

    • 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)
    • Re: P=NP: Linear Programming Formulation of the TSP
      ... I believe I understand what Dr. Moews is trying to do perfectly. ... >>Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ... then they are redundent with respect to the original ...
      (comp.theory)
    • Re: P=NP: Linear Programming Formulation of the TSP
      ... David Moews wrote: ... constraints you are adding to the original math prog problem are ... then the new polytope is not the same as the original one. ...
      (comp.theory)
    • Re: P=NP: Linear Programming Formulation of the TSP
      ... Dr. Moews: I am busy with exams, grading, etc. at this time. ... That is clearly not what Yannakakis says. ... Either the constraints developed by Moews using his xvariables ... then the new polytope is not the same as the original one. ...
      (comp.theory)