Re: P=NP: Linear Programming Formulation of the TSP
moustap...@business.uconn.edu
> In article <1115321325.2...@z14g2000cwz.googlegroups.com>,
> <moustap...@business.uconn.edu> wrote:
> >Your overall approach for demonstrating the contradiction you want
> >(unless that approach is different from what you have posted before)
is
> >invalid. Yannakakis's results apply to symmetric TSP's. The approach
> >you are using can be applied to any LP formulation of the TSP, which
> >means that basically, your claim is really that the TSP cannot be
> >formulated as an LP (any LP)! That is clearly not what Yannakakis
says.
> >(By the way, why do you think Yannakakis takes such great care to
limit
> >his results to symmetric problems? Do you think you know the scope
of
> >his work better than him?)
>
> Actually, it is you that misunderstands the situation. Of course,
> David Moews understands that Yannakakis's result applies only to
> symmetric LP's. The structure of his argument is, at a high level,
> that if your *non-symmetric* LP formulation is correct, then one
> can construct a *symmetric* LP formulation in contradiction with
> Yannakakis's theorem.
I believe I understand what Dr. Moews is trying to do perfectly. All I
am saying is that his argumentation is invalid. For one thing, if we
turn the tables and apply the "structure of his argument" to himself,
we can only conclude that either his approach is invalid or that he has
broadened the scope of Yannakakis' work to the claim that there exists
no LP formulation of the TSP, which Yannakakis was careful enough not
to even suggest.
>
> >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).
>
> These paragraphs also betray a fundamental misunderstanding.
> Yannakakis's theorem does not apply only to LP's without redundant
> constraints. Of course, in practice one might apply pre-processing
and
> remove obviously redundant constraints, but this does not change the
> statement of Yannakakis's theorem.
>
> I don't have access to the journal version of Yannakakis's paper at
the
> moment, only the STOC extended abstract, but in the latter, the
remark
> about minimal LP's is irrelevant to the discussion at hand. The
point
> is that the statement of Yannakakis's theorem stands on its own, and
> even if minimal LP's are considered at some point during the proof,
> this does not mean that the theorem applies only to minimal LP's.
Among other things overlooked by Dr. Moews, Yannakakis makes the
assumption that if the polytope under consideration is symmetric, then
its minimal description is also symmetric. Clearly, that is not case
with the "extended model" Moews constructs from my model.
> --
> Tim Chow tchow-at-alum-dot-mit-dot-edu
> The range of our projectiles---even ... the artillery---however
great, will
> never exceed four of those miles of which as many thousand separate
us from
> the center of the earth. ---Galileo, Dialogues Concerning Two New
Sciences
David Moews
completely explained why the y_{isiisi}'s can be taken to be zero.
The reason is as follows: by Proposition 1, we know that feasible
solutions to problem \overline{IP} exist with finite objective function.
Therefore, the optimal solution must also have finite objective function,
and since, if any y_{isiisi} is positive, the objective function is infinite,
the optimal solution must be in the subspace where each y_{isiisi} is zero.
The behavior of the Diaby algorithm is therefore not changed if
we add the constraints
y_{isiisi} = 0, i in {2, ..., n}, s in {1, ..., n-2}
to problem \overline{IP}, so, in our analysis of the algorithm, we can assume
that this has already been done. Since these constraints are
symmetric with respect to permutations of i, the construction in
<cmote5$al6$1...@lydian.ccrwest.org> still works.
--
David Moews dmo...@xraysgi.ims.uconn.edu
moustap...@business.uconn.edu
moustap...@business.uconn.edu
David Moews wrote:
> In article <1115321325.2...@z14g2000cwz.googlegroups.com>,
> <moustap...@business.uconn.edu> wrote:
> |Your overall approach for demonstrating the contradiction you want
> |(unless that approach is different from what you have posted before)
is
> |invalid. Yannakakis's results apply to symmetric TSP's. The approach
> |you are using can be applied to any LP formulation of the TSP, which
> |means that basically, your claim is really that the TSP cannot be
> |formulated as an LP (any LP)!
>
> I don't think my approach can be applied to an arbitrary LP
formulation
> of the TSP. If you see a way to do this, I'd like to ask you to
indicate
> it, as the result that the TSP can't be formulated as a (small) LP
problem
> would be very interesting.
>
I think this is obviously trivial, because the variables and
constraints you are adding to the original math prog problem are
completely irrelevant to the optimization problem expressed by that
math prog problem.
For example,
(P1)
Min cx
st: Ax = b
x >= 0
and
(P2)
Min cx
st: Ax = b
y = Bx
x >= 0
y >=0
are trivially the same optimization problem if B only has non-negative
components. But, clearly, it is utter nonsense to try to infer
properties of (P1) based on characterizations of the y variables in
some other space that has nothing to do with either of the 2
optimization problems!
I submit to you that this is exactly what you are doing, and that
"minimality" is actually quite crucial.
> |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.
>
> Introducing the x_{i, j}'s clearly does not change the shape of
> the feasible polytope, although it raises the dimensionality of its
> ambient space. The reason for introducing them is that we wish to
> simplify the feasible polytope by projecting it onto the x_{i, j}'s.
>
> |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).
>
> Minimality is not relevant here. The logical flow of the proof is as
follows:
>
> 1. We start with a formulation (minimal or not) of a linear
programming
> problem which claims to express the matching polytope and is
symmetric
> under vertex permutation.
>
> 2. Since the LP problem is symmetric, its feasible polytope is also
symmetric.
>
> 3. Yannakakis now proves (JCSS 43, 441--466, at 448) that this
polytope can
> be described by a minimal symmetric LP problem.
>
> The formulation we start with need not be minimal.
>
> |[...]
> |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.
>
> As I have said, although it is not symmetric, Yannakakis's proof can
be
> adapted to handle it. Yannakakis's proof is as follows:
>
> 1. He proves (Theorem 1) that the matching polytope cannot be
expressed
> by a small symmetric LP.
>
> 2. He proves that if there is a small symmetric LP expression of the
> TSP polytope, it can be used to construct a small symmetric LP
expression
> of the matching polytope.
>
> 3. Therefore, no small symmetric LP expression of the TSP polytope
exists
> (Theorem 2).
>
> My construction is almost identical to Yannakakis's.
>
> 2'. I prove that if there is a small symmetric LP problem which
expresses
> the Hamiltonian path polytope, it can be used to construct a
small
> symmetric LP problem which expresses the matching polytope.
>
> 3'. Therefore, no small symmetric LP problem which expresses the
Hamiltonian
> path polytope exists.
>
> 4'. Your LP formulation of the TSP immediately gives a small
symmetric LP
> problem which expresses the Hamiltonian path polytope.
> --
> David Moews
dmo...@xraysgi.ims.uconn.edu
Bryan Olson
> DR. MOEWS - WHATEVER THIS MAY BE TO YOU (SINCE I DON'T KNOW YOU), I
> WOULD SUGGEST THAT YOU READ MY PAPER MORE CAREFULLY STILL.
I just looked at the paper myself. The first major outright
error I see is that the constraints in "Problem TSP" do not
require each city to be visited. That's not the NP-hard problem
we know as TSP.
Also, the problem doesn't say that the c's are given, so we can
minimize the expression by minimizing the c's, except that
they're unconstrained. Incidentally, "back-travel" is a non-
issue; TSP is still NP-hard without the requirement that no city
is revisited.
--
--Bryan
moustap...@business.uconn.edu
> moustap...@business.uconn.edu wrote:
> > DR. MOEWS - WHATEVER THIS MAY BE TO YOU (SINCE I DON'T KNOW YOU),
I
> > WOULD SUGGEST THAT YOU READ MY PAPER MORE CAREFULLY STILL.
>
> I just looked at the paper myself. The first major outright
> error I see is that the constraints in "Problem TSP" do not
> require each city to be visited. That's not the NP-hard problem
> we know as TSP.
Problem TSP is actually just a version of the "time-dependent"
formulation that is one of the "classical" formulations in the
literature (Please, see the references cited in the paper). There is no
explicit constraint that requires that each city be visited in Problem
TSP. But to understand how all the constraints together force this,
consider the following: You have say, 4 cities (a, b, c, d), to be
visited in 4 stops (1, 2, 3, 4); You have to make all the stops
(required by the expplicitly stated constraints); And you have to visit
a different city at each stop (required by the "no back-travel"
constraint). The only way to achieve this is if you visit each city
exactly once.
>
> Also, the problem doesn't say that the c's are given, so we can
> minimize the expression by minimizing the c's, except that
> they're unconstrained.
The travel costs are given, and the c's are directly obtained from
these. They are not variables in the model.
Incidentally, "back-travel" is a non-
> issue; TSP is still NP-hard without the requirement that no city
> is revisited.
In fact, it is precisely this requirement that "no city is revisited"
that makes the TSP NP-Hard. Without it, TSP changes into other problems
that are easy to solve. The contribution of my model (provided it is
correct -which I believe it is) is that it overcomes this difficulty
(i.e., "no city is revisited") within a linear programming (LP)
modeling framework. As a result, we are able to solve an LP to get the
optimal solution to the TSP. And so, since LP's can be solved in
polynomial time, that means we are able to obtain optimal solutions to
TSP's in polynomial-time!
>
>
> --
> --Bryan
Bryan Olson
> Bryan Olson wrote:
>> The constraints in "Problem TSP" do not
>>require each city to be visited. That's not the NP-hard problem
>>we know as TSP.
>
> (required by the expplicitly stated constraints); And you have to visit
> a different city at each stop (required by the "no back-travel"
> constraint). The only way to achieve this is if you visit each city
> exactly once.
Yes. I got lost in a bit of notation.
[...]
>> Incidentally, "back-travel" is a non-issue; TSP is still NP-hard
>> without the requirement that no city is revisited.
>
> In fact, it is precisely this requirement that "no city is revisited"
> that makes the TSP NP-Hard. Without it, TSP changes into other problems
> that are easy to solve.
Not true. See, for example:
http://en.wikipedia.org/wiki/Traveling_salesman_problem
under "NP-hardness".
> The contribution of my model (provided it is
> correct -which I believe it is) is that it overcomes this difficulty
> (i.e., "no city is revisited") within a linear programming (LP)
> modeling framework. As a result, we are able to solve an LP to get the
> optimal solution to the TSP. And so, since LP's can be solved in
> polynomial time, that means we are able to obtain optimal solutions to
> TSP's in polynomial-time!
I only know a little about linear programming. In particular,
the standard form I've seen has much simpler constraints. Is it
obvious, or well-known, that you can set up inter-dependent
constraints and still put the problem into the required form in
polynomial time?
--
--Bryan
moustap...@business.uconn.edu
You are right. I think I oversimplified a little too much. What I had
in mind was that, whithout the "no city revisited" requirement, the TSP
changes into what is known as an "assignment problem" which is easy to
solve. Also, different versions of the resulting "modified TSP" can be
modeled as "shortest path problems", which are also easy to solve.
>
> > The contribution of my model (provided it is
> > correct -which I believe it is) is that it overcomes this
difficulty
> > (i.e., "no city is revisited") within a linear programming (LP)
> > modeling framework. As a result, we are able to solve an LP to get
the
> > optimal solution to the TSP. And so, since LP's can be solved in
> > polynomial time, that means we are able to obtain optimal
solutions to
> > TSP's in polynomial-time!
>
> ...Is it ... well-known that you can set up inter-dependent
> constraints and still put the problem into the required form in
> polynomial time?
Not always. But the answer is "yes" in general, and in particular for
my model.
moustap...@business.uconn.edu
changes into ..." what I had in mind is the fact that the solution to
the assignment problem does not actually result in a connected travel
in general. So that solution is not really a "travel" in the normal
sense.
David Moews
<moustap...@business.uconn.edu> wrote:
|[...]
|I think this is obviously trivial, because the variables and
|constraints you are adding to the original math prog problem are
|completely irrelevant to the optimization problem expressed by that
|math prog problem.
|
|For example,
|
|(P1)
|Min cx
|st: Ax = b
| x >= 0
|
|and
|
|(P2)
|Min cx
|st: Ax = b
| y = Bx
| x >= 0
| y >=0
|
|are trivially the same optimization problem if B only has non-negative
|components. But, clearly, it is utter nonsense to try to infer
|properties of (P1) based on characterizations of the y variables in
|some other space that has nothing to do with either of the 2
|optimization problems!
Prof. Diaby,
Introducing new variables in this way is always possible, and it is a
reasonable thing to do if looking at the problem in terms of the new variables
makes things clearer (which it does in the case I am considering.) I will
present a trivial, but analogous, example.
--------
Suppose that an air cargo shipper is concerned about the
amount of cargo he can ship from various cities to various other cities
on June 22, 2005. Let
A be the number of tons of cargo shipped from Toronto to Ottawa,
B " " " " " " " " from Toronto to Saskatoon,
C " " " " " " " " from Toronto to Regina,
D " " " " " " " " from Minneapolis to Saskatoon,
and
E " " " " " " " " from Minneapolis to Regina.
Now, examination of the flight schedule yields the following constraints:
A >= 0, B >= 0, C >= 0, D >= 0, E >= 0,
A <= 40,
B + C <= 20, (*)
D + E <= 20,
B + C + D + E <= 30.
Suppose that we are interested in how many tons of cargo depart from Toronto
in all, and how many depart from Minneapolis in all. To study this, we can
introduce new variables
F := A + B + C,
G := D + E (**)
and project the feasible polytope defined by (*) and (**) onto the F-G plane.
This yields the projected feasible polytope
F >= 0, G >= 0,
F <= 60,
G <= 20,
F + G <= 70.
By examining this projected polytope, we can infer, for example, that it
is possible for 56 tons of cargo to leave Toronto on the date in question,
or for 16 to leave Minneapolis, but not for both of these events to occur
simultaneously.
--------
My introduction of the x_{i,j}'s is wholly analogous to the introduction
of F and G in this example. I hope that this clarifies the introduction
of the x_{i,j}'s, which, as I think you can see, is essentially
straightforward.
--
David Moews dmo...@xraysgi.ims.uconn.edu
Bryan Olson
I have to agree (after a little homework). Now I'm stuck where
others are, on Proposition 2. By an extension to construction in
the proof of proposition 1, I think we can show:
Any set of c.a.s.s. paths, each with an associated flow,
such that the sum of the flows is 1, corresponds to a
feasible solution to IPBAR.
And I understand Proposition 2 to be asserting the converse:
Any feasible solution to IPBAR can be generated as a sum
of flows along c.a.s.s. paths.
I'm not too confident of my understanding of Prop 2, because the
argument seems to take the "collection of c.a.s.s. paths" to be
"all possible c.a.s.s. paths obtainable from (y,z)." That is not
generally the same as a set of c.a.s.s. paths with flows that
sum to the feasible solution. Proof:
There are M! c.a.s.s. paths, so we have M!-1 degrees of freedom
in creating a set of c.a.s.s. path flows that sums to 1. A
feasible solution to IPBAR gives us only order M**14 equations.
For problems with many cities, multiple sums of c.a.s.s. path
flows must correspond to the same feasible solution for IPBAR.
Is Proposition 2 (as I understand it) true? I don't think so.
The M! c.a.s.s. paths must, by definition, each be connected,
their flows conserved. The constraints link certain sums of
path-flows, but that's not, at least not obviously, enough.
The first sentence of the proof of Prop 2 states:
Note that constraints (2.15) and (2.17) require that every
path span the set of stages.
I don't think so. The variables in constraints 2.15 and (the
corrected version of) 2.17 are pairs of vertices at stages.
Many different paths may go through one such pair.
Can we strengthen the constraints to say connect and conserve
each individual path? In the multi commodity-flow model, I don't
see how to partition the flow into c.a.s.s. paths without
defining one commodity per c.a.s.s. path. Given that there are
M! of them, that would be super-polynomial.
As far as I can see, if I'm wrong and Prop 2 is true, the rest
of the important results follow. There may be more than one
optimal c.a.s.s. path, which could give us fractional flows, but
we'd get the optimal cost, and that's enough to solve the
NP-complete decision-problem version of TSP.
--
--Bryan
moustap...@business.uconn.edu
> moustap...@business.uconn.edu wrote:
> > Bryan Olson wrote:
> >>...Is it ... well-known that you can set up inter-dependent
> >>constraints and still put the problem into the required form in
> >>polynomial time?
> >
> > Not always. But the answer is "yes" in general, and in particular
for
> > my model.
>
> I have to agree (after a little homework). Now I'm stuck where
> others are, on Proposition 2. By an extension to construction in
> the proof of proposition 1, I think we can show:
>
> Any set of c.a.s.s. paths, each with an associated flow,
> such that the sum of the flows is 1, corresponds to a
> feasible solution to IPBAR.
This is true.
>
> And I understand Proposition 2 to be asserting the converse:
>
> Any feasible solution to IPBAR can be generated as a sum
> of flows along c.a.s.s. paths.
Yes indeed, that is what the proposition asserts.
>
> I'm not too confident of my understanding of Prop 2, because the
> argument seems to take the "collection of c.a.s.s. paths" to be
> "all possible c.a.s.s. paths obtainable from (y,z)."
No, that is not what the proposition means to say. (y,z) is any *given*
*feasible* solution. The idea is that basically, the positive
components of any given feasible solution will correspond to a set of
cass paths thru the network. To understand the common sense behind
this, consider the figure on page 8. Think of each *row* of vertices as
a "level," and of y(isjkrt) as the contribution of (the flow on) arc
(i,s,j) to (the flow on) arc (k,r,t). Now, basically, constraints 2.22
stipulate that an arc (i,s,j) cannot contribute to any "downstream" arc
(k,r,t) with k = i or t = j. Another way to think of this, is that flow
enters and/or leaves a level only once. Yet, each flow starting at
stage 1 must span the set of stages because of constraints 2.15. Hence,
flow originating from stage 1 has to span the set of levels also. At a
given stage, say r, a same given flow is labeled multiple times, in
terms of arcs at preceeding stages, thru the y(isjkrt) variables. This
allows us the ability to keep enforcing constraint 2.22 as the flow
"moves" across the network from stage to stage. The z variables ensure
that all flows are consistent with the flows at stage 1.
Alternatively, within the framework of the IP, one can think of
y(isjkrt) as the product x(isj) * x(krt), and of z(ijupvkrt) as the
product x(i,1,j) * x(upv) * x(krt) (where the x(isj)'s are 0/1
indicators of flow on arcs of the network), and apply a reasoning
similar to the one above.
That is not
> generally the same as a set of c.a.s.s. paths with flows that
> sum to the feasible solution. Proof:
>
> There are M! c.a.s.s. paths, so we have M!-1 degrees of freedom
> in creating a set of c.a.s.s. path flows that sums to 1. A
> feasible solution to IPBAR gives us only order M**14 equations.
> For problems with many cities, multiple sums of c.a.s.s. path
> flows must correspond to the same feasible solution for IPBAR.
Given any feasible solution, its positive components
>
> Is Proposition 2 (as I understand it) true? I don't think so.
> The M! c.a.s.s. paths must, by definition, each be connected,
> their flows conserved. The constraints link certain sums of
> path-flows, but that's not, at least not obviously, enough.
> The first sentence of the proof of Prop 2 states:
>
> Note that constraints (2.15) and (2.17) require that every
> path span the set of stages.
>
> I don't think so. The variables in constraints 2.15 and (the
> corrected version of) 2.17 are pairs of vertices at stages.
> Many different paths may go through one such pair.
Yes, it is true that many different paths may go thru each vertex. But
because of flow conservation, starting from stage 2, what comes into a
vertex must flow out of that vertex, except if the node is at the last
stage of the network. Hence each flow must span the set of stages
(although it is additionally re-labeled multiple times from stage to
stage).
>
>
> Can we strengthen the constraints to say connect and conserve
> each individual path? In the multi commodity-flow model, I don't
> see how to partition the flow into c.a.s.s. paths without
> defining one commodity per c.a.s.s. path. Given that there are
> M! of them, that would be super-polynomial.
Here the total flow on a given arc is like a "commodity." If the total
flow on arc (i,s,j) is say, lambda, then this flow of lambda will
create a "layer" of flow by its "contributions" to arcs starting from
stage s+1, through the y(isjkrt) variables. The sum_over k and
t_(y(isjkrt)) will equal lambda for any given r >= s+1. And because of
the constraints 2.22, y(isjkrt) will equal zero for any r >= s+1 if k =
i or t = j (roughly). Hence, thinking of the cities as "levels" in the
graph of Fig. 2.1, the basic idea is (roughly) that any flow "enters"
and/or "leaves" a given level only once, as I indicated earlier.
>
>
> As far as I can see, if I'm wrong and Prop 2 is true, the rest
> of the important results follow. There may be more than one
> optimal c.a.s.s. path, which could give us fractional flows, but
> we'd get the optimal cost, and that's enough to solve the
> NP-complete decision-problem version of TSP.
That is true.
>
>
> --
> --Bryan
Bryan Olson
[...]
> No, that is not what the proposition means to say. (y,z) is any *given*
> *feasible* solution. The idea is that basically, the positive
> components of any given feasible solution will correspond to a set of
> cass paths thru the network.
That's open, but the following is definitely false:
Any given feasible solution to IPBAR will correspond to
*exactly one* set of c.a.s.s. paths through the network.
That's not a counter-example, but it does show that the proof
of Prop 2 doesn't really make sense. What are "all possible
c.a.s.s. paths obtainable from [the positive components of]
(y,z)"?
>>The first sentence of the proof of Prop 2 states:
>>
>> Note that constraints (2.15) and (2.17) require that every
>> path span the set of stages.
>>
>>I don't think so. The variables in constraints 2.15 and (the
>>corrected version of) 2.17 are pairs of vertices at stages.
>>Many different paths may go through one such pair.
>
> Yes, it is true that many different paths may go thru each vertex. But
> because of flow conservation, starting from stage 2, what comes into a
> vertex must flow out of that vertex, except if the node is at the last
> stage of the network. Hence each flow must span the set of stages
> (although it is additionally re-labeled multiple times from stage to
> stage).
The issue is whether every *path* spans the stages. The claim
doesn't really even makes sense under the usual definition of
path (one arc is a path).
--
--Bryan
moustap...@business.uconn.edu
> That's open, but the following is definitely false:
>
> Any given feasible solution to IPBAR will correspond to
> *exactly one* set of c.a.s.s. paths through the network.
I did not mean to suggest this. I hope you appreciate my efforts to
give you an intuitive sense of what the mathematics prove... As they
say, "One image is worth a thousand words." ...Or should that be "One
formula"?
Anyway, here is another attempt:
Consider an arc at stage 1, say (i,1,j), with a positive flow of L ( 0
< L <= 1) (i.e., y(i,1,ji,1,j) = L). At stage 2, the flow L, may be
"split" as it leaves node (j,2) into, say L_1, L_2, ..., L_k. Now, each
of these L_i's may be similarly "split", leaving stage 3, and so on.
The labeling of the flows is such that each flow resulting from L, say
the fractional amount of it that flows on arc (k,r,t), is labeled as
y(i,1,j,krt). Hence this amount does not "return" to either cities i or
j because of constraints 2.22.
Now assume the total flow on an arbitrary arc (k,r,t), y(krtkrt), is
positive. This flow may be successively "split" as described above,
starting at stage r+1. But, in the sense described above, none of it
will "return" to either cities k or t.
Combining the above, if arc (k,r,t) "received" any contribution from
arc (i,1,j) (i.e., if y(i,1,jkrt) is positive) that contribution will
not "return" to either i, j, k, or t, after stage r (given some
consistency requirements).
I think Proposition 2 follows from this.
>
> That's not a counter-example, but it does show that the proof
> of Prop 2 doesn't really make sense. What are "all possible
> c.a.s.s. paths obtainable from [the positive components of]
> (y,z)"?
All the cass paths that comprise a given feasible solution can be
identified by recursively "tracing", in a backward manner, the
positive flows going into stage n-1 of the network, all the way back to
the stage 1, through the y variables.
.
> The issue is whether every *path* spans the stages. The claim
> doesn't really even makes sense under the usual definition of
> path (one arc is a path).
I am not sure I said that " *every path* spans the set of stages."
Anyway, what I meant to say is that the positive components of every
feasible solution correspond to a set of paths that each span the set
of stages. And, in fact, I believe this follows trivially from flow
conservation and connectivity!
moustap...@business.uconn.edu
moustapha.di...@business.uconn.edu wrote:
> Bryan Olson wrote:
>
> > That's open, but the following is definitely false:
> >
> > Any given feasible solution to IPBAR will correspond to
> > *exactly one* set of c.a.s.s. paths through the network.
>
> I did not mean to suggest this. I hope you appreciate my efforts to
> give you an intuitive sense of what the mathematics prove... As they
> say, "One image is worth a thousand words." ...Or should that be "One
> formula"?
>
On viewing my posted message, I realized that I had misread your
statement that
"Any given feasible solution to IPBAR will correspond to
> > *exactly one* set of c.a.s.s. paths through the network."
That is actually what I am stating. As I indicated in the previous
message, that set of cass paths can be "retrieved" by recursively
tracing the positive components of the solution, starting from the last
stage of the network and working backward.
All my other responses in the previous post remain the same.
>
Bryan Olson
> On viewing my posted message, I realized that I had misread your
> statement that
>
> "Any given feasible solution to IPBAR will correspond to
> *exactly one* set of c.a.s.s. paths through the network."
>
> That is actually what I am stating. As I indicated in the previous
> message, that set of cass paths can be "retrieved" by recursively
> tracing the positive components of the solution, starting from the last
> stage of the network and working backward.
That much I can prove false. There are M! c.a.s.s. paths. Any
set of (non-negative) flows on those paths, such that the total
flow is one, forms exactly one feasible solution. We have M! - 1
degrees of freedom in creating a legal set of c.a.s.s. path
flows. A feasible solution gives us only polynomial many (order
M**14) equations, so we cannot in general solve for M! unknowns.
There just isn't enough information in a feasible solution.
The number-of-unknowns argument proves that the recursive
retrieval cannot, in general, reconstruct the set of c.a.s.s.
path flows (even assuming the feasible solution is a set of
c.a.s.s. path flows). Intuitively, where it fails is that the
feasible solution doesn't distinguish each c.a.s.s. path as its
own commodity.
The 'y' variables identify two arcs, and how much of the same
commodities flows on both; the 'z' variables identify the same
commodities flowing on three arcs. The constraints, on the
other hand, require only numeric equality of amount of flow;
they do not generally imply that the same commodities are
flowing on both sides of each equation.
--
--Bryan
moustap...@business.uconn.edu
> moustap...@business.uconn.edu wrote:
> > On viewing my posted message, I realized that I had misread your
> > statement that
> >
> > "Any given feasible solution to IPBAR will correspond to
> > *exactly one* set of c.a.s.s. paths through the network."
> >
> > That is actually what I am stating. As I indicated in the previous
> > message, that set of cass paths can be "retrieved" by recursively
> > tracing the positive components of the solution, starting from the
last
> > stage of the network and working backward.
>
> That much I can prove false. There are M! c.a.s.s. paths. Any
> set of (non-negative) flows on those paths, such that the total
> flow is one, forms exactly one feasible solution. We have M! - 1
> degrees of freedom in creating a legal set of c.a.s.s. path
> flows. A feasible solution gives us only polynomial many (order
> M**14) equations, so we cannot in general solve for M! unknowns.
> There just isn't enough information in a feasible solution.
The problem with your argument is that it overlooks the fact that paths
overlap. In particular, the total flow on an arc belonging to multiple
paths is accounted as well as the details of the "contributions" of
arcs from stages that precede the stage of the arc in question.
I agree that there is a large number of possible cass paths. But, no
set of cass paths with flows summing to one is excluded from the
feasible set of the model.
>From the graph underlying the model (Fig. 2.1) it is evident all the M!
cass path possibilities are part of the feasible set. To see this,
observe that if you pick an arc with positive flow at stage 1, then
because the constraints of the model, you will have (M-1) choices for
feasible flow from that arc into stage 2; for each of those feasible
flow into stage 2, you will have (M-2) possibilities of feasible flow
into stage 3, and so on. None of the "possibilities for feasible flow"
into the next stage from a given stage is prohibited in the model. In
other words, for each choice of positive flow at stage 1, you have
(M-1)! possibilities of feasible (i.e. cass) flows through the network.
>
> The number-of-unknowns argument proves that the recursive
> retrieval cannot, in general, reconstruct the set of c.a.s.s.
> path flows (even assuming the feasible solution is a set of
> c.a.s.s. path flows). Intuitively, where it fails is that the
> feasible solution doesn't distinguish each c.a.s.s. path as its
> own commodity.
>
> The 'y' variables identify two arcs, and how much of the same
> commodities flows on both; the 'z' variables identify the same
> commodities flowing on three arcs. The constraints, on the
> other hand, require only numeric equality of amount of flow;
> they do not generally imply that the same commodities are
> flowing on both sides of each equation.
>
The feasible solution does not actually need to distinguish each cass
path as a separate commodity (that would require enumeration of those
paths!). But as I stated before, the cass paths in a particular given
solution can be easily reconstructed by "tracing" the y variables,
because the set of those variables that "form" a given path (similar to
a "characteristic vector" of the path) will be defined through
relations that are similar to 2.25 with the "1" replaced with the
"weight" of the path.
I think you could possibly get a better understanding of these by
taking a look at the OSL outputs posted on my "P = NP" page, if you
have not done so already.
Bryan Olson
[...]
> I did not mean to suggest this. I hope you appreciate my efforts to
> give you an intuitive sense of what the mathematics prove... As they
> say, "One image is worth a thousand words." ...Or should that be "One
> formula"?
And I hope you appreciate my efforts to gain such a sense.
> Anyway, here is another attempt:
>
> Consider an arc at stage 1, say (i,1,j), with a positive flow of L ( 0
> < L <= 1) (i.e., y(i,1,ji,1,j) = L). At stage 2, the flow L, may be
> "split" as it leaves node (j,2) into, say L_1, L_2, ..., L_k. Now, each
> of these L_i's may be similarly "split", leaving stage 3, and so on.
>
> The labeling of the flows is such that each flow resulting from L, say
> the fractional amount of it that flows on arc (k,r,t), is labeled as
> y(i,1,j,krt). Hence this amount does not "return" to either cities i or
> j because of constraints 2.22.
>
> Now assume the total flow on an arbitrary arc (k,r,t), y(krtkrt), is
> positive. This flow may be successively "split" as described above,
> starting at stage r+1. But, in the sense described above, none of it
> will "return" to either cities k or t.
>
> Combining the above, if arc (k,r,t) "received" any contribution from
> arc (i,1,j) (i.e., if y(i,1,jkrt) is positive) that contribution will
> not "return" to either i, j, k, or t, after stage r (given some
> consistency requirements).
>
> I think Proposition 2 follows from this.
And I disagree. I see how any set of c.a.s.s. path flows
conforms to the constraints, but I see no convincing evidence
that the constraints are strong enough to force all flow into
c.a.s.s. paths.
>> The issue is whether every *path* spans the stages. The claim
>> doesn't really even makes sense under the usual definition of
>> path (one arc is a path).
> I am not sure I said that " *every path* spans the set of stages."
> Anyway, what I meant to say is that the positive components of every
> feasible solution correspond to a set of paths that each span the set
> of stages. And, in fact, I believe this follows trivially from flow
> conservation and connectivity!
I got "every path spans the stages" from the first sentence of
the proof of proposition 2. I added the *emphasis* myself.
I fear at this point, we are wasting our time trying to explain
our intuition. I've joined those who consider proposition 2 to
be unproven, and expect that it is false.
--
--Bryan
moustap...@business.uconn.edu
Some weeks ago, in the process of extending my LP formulation of the
TSP to other combinatorial problems, I found that the model needed some
additional constraints. I have revised the model and paper accordingly.
I would like to invite you, if I may, to take a look at the revised
model and paper at: http://www.business.uconn.edu/users/mdiaby/TSPLP.
Any comments would be highly appreciated. Regards.//MD.
David Moews
<http://www.business.uconn.edu/users/mdiaby/TSPLP/Paper/TSP_LP_small.pdf>,
dated 2005-II-12, of Moustapha Diaby's paper
``P=NP: Linear Programming Formulation of the Traveling Salesman Problem''.
I have the following comments.
1. The statement of Proposition 2 is unclear, because it has not been
defined what it means for (y, z) to consist of a collection of
c.a.s.s. paths.
2. The proof of Proposition 2 is likewise unclear. At the bottom
of page 13, for example, it is claimed that ``there must remain at
least one path, say Path L, with positive flow, say \lambda (\lambda>0),
that is not a c.a.s.s. path''. Presumably, what is happening here
is that vectors which project onto multiples of the v_g's (see below)
are being subtracted from the y_{isjkrt}'s and z_{ijupvkrt}'s so as to
leave these variables nonnegative, and after this can no longer be
done, the situation is examined. However, a priori, the y_{isjkrt}'s and
z_{ijupvkrt}'s are only a collection of variables, and it is not clear
what it means to locate in them a path of positive flow, nor why this
should be possible.
3. If we attempt nonetheless to clarify the content of Proposition 2,
given the claims made in Propositions 1, 3, 4 and the rest of the paper,
it appears that it must imply that the projection of the feasible polytope
onto the variables y_{isjisj} yields the convex hull of
{ v_g | g a c.a.s.s. path}, where c.a.s.s. paths and v_g are as defined in
my previous post <cmote5$al6$1...@lydian.ccrwest.org>. Given this, it can
be shown, using similar reasoning to my previous post, that Proposition 2
is in conflict with Yannakakis's 1988 result. I give the argument in an
appendix at the end of this post.
4. Re the remarks on Yannakakis's result near the bottom of p. 12, I will
point out that in order for a LP formulation of the TSP to be symmetric,
Yannakakis does not require that the stages of the tour be treated
symmetrically, or even that they be expressed at all. Symmetry under
permutation of cities (in a sense defined in Yannakakis's paper) is all
that is required. Of course, Diaby's formulation is not symmetric in this
sense, because city 1 is treated differently from the other cities.
However, Yannakakis's proof can be adapted to handle this, as I outline
below and in my previous post.
5. There appears to be a typo in equations (2.7) (p. 9), (2.17) (p. 10),
and (3.6) (p. 17): to preserve Proposition 1 and the sense of the paper,
y_{isjk,r+1,t} should be changed to y_{isjt,r+1,k} in these equations.
--
David Moews dmo...@xraysgi.ims.uconn.edu
---------------------------------------------------------------------------
APPENDIX.
In this revision, Diaby's initial LP formulation, \overline{IP} (p. 12)
of an n-city TSP problem contains variables y_{isjkrt} and z_{ijupvkrt},
where i, j, k, t, u, and v range over the set {2, ..., n} (the set of
cities, excluding city 1), and p, r, and s range over the set {1, 2, ..., n-2}
(the set of times at which these cities are visited, excluding time n-1.)
Now
(1') If the y's and z's are permuted by sending
y_{isjkrt} to y_{f(i)sf(j)f(k)rf(t)}
and z_{ijupvkrt} to z_{f(i)f(j)f(u)pf(v)f(k)rf(t)}
for some permutation f of {2, ..., n}, the set of constraints used
to define the feasible polytope is left unchanged, and therefore the
feasible polytope is left unchanged,
and
(2') According to Proposition 2, projecting the feasible polytope
onto the variables y_{isjisj} yields the convex hull of
{ v_g | g a c.a.s.s. path }. Here, a c.a.s.s. path is a bijection g
from {1, ..., n-1} (the set of times) to {2, ..., n} (the set of
cities, excluding city 1), and the value of y_{isjisj} at v_g is 1 if
(g(s),g(s+1))=(i,j), 0 otherwise.
We can now proceed with the argument given in <cmote5$al6$1...@lydian.ccrwest.org>,
replacing (1) and (2) with (1') and (2'), and construct a counterexample to
Theorem 1 in Yannakakis (J. Computer and System Sciences 43 (1991), pp.
441--466).
--
David Moews dmo...@xraysgi.ims.uconn.edu
tc...@lsa.umich.edu
How much work would it take to build an explicit counterexample? Due to the
unclarity of Proposition 2, maybe this isn't possible?
tc...@lsa.umich.edu
>How much work would it take to build an explicit counterexample?
By this I meant not a counterexample to Yannakakis's theorem, but an
instance of the TSP that is incorrectly solved.
moustap...@business.uconn.edu
CORRECTLY POINTED OUT A TYPO IN THE PAPER, BUT IT IS CLEAR TO ME -AND
IN FACT, YOU YOURSELF ACKNOWLEDGE THIS- THAT YOU STILL DO NOT
UNDERSTAND THE PAPER.
I AM PRETTY CONVINCED THAT IF THERE IS A FLAW IN MY MODEL --WHICH I
DON'T BELIEVE THERE IS-- IT WOULD HAVE NOTHING TO DO WITH ANY OF YOUR
EXPOSITIONS SO FAR, BECAUE THOSE EXPOSITIONS HAVE BEEN MOSTLY
NON-SENSICAL SO FAR. IT IS SUGGESTED TO YOU IN THE CURRENT THREAD THAT
YOU TO COME UP WITH AN INSTANCE OF THE TSP THAT WOULD BE INCORRECTLY
SOLVED BY MY MODEL. I THINK YOU SHOULD DO THIS AND PERHAPS, MAKE THE
LENGTHY ARGUMENTATION UNNECESSARY. I ALSO HAVE SOME BRIEF COMMENTS ON
SOME OF YOUR STATEMENTS. PLEASE, SEE BELOW. //MD
2. The proof of Proposition 2 is likewise unclear. At the bottom
of page 13, for example, it is claimed that ``there must remain at
least one path, say Path L, with positive flow, say \lambda
(\lambda>0),
that is not a c.a.s.s. path''. Presumably, what is happening here
is that vectors which project onto multiples of the v_g's (see
below)
are being subtracted from the y_{isjkrt}'s and z_{ijupvkrt}'s so as
to
leave these variables nonnegative, and after this can no longer be
done, the situation is examined...
YOU SAY YOU DON'T UNDERSTAND, YET YOU MAKE "PRESUMPTIONS" AND JUST "RUN
AWAY" (SO TO SPEAK) WITH THOSE. AS A RESULT YOU ARE ENDING UP WRITING A
LOT OF GIBBERISH. FOR EXAMPLE, YOU WRITE "Presumably, what is happening
here ..." WHAT DO YOU MEAN BY "WHAT"? ALSO, WHATEVER IS "happening" IS
"HAPPENING" TO WHAT?
However, a priori, the y_{isjkrt}'s and
z_{ijupvkrt}'s are only a collection of variables, and it is not
clear
what it means to locate in them a path of positive flow, nor why
this
should be possible.
ARE YOU NOT STATING, AGAIN, THAT YOU DON'T UNDERSTAND? THE Y AND Z'S
ARE CONSTRAINED VARIABLES WITHIN A CLEARLY-STATED MODEL AND ARE PARTS
OF A DETAILED EXPOSITION. I THINK YOU SHOULD MAKE THE EFFORT TO
UNDERSTAND WHATEVER IS BEING SAID ABOUT THEM WITH RESPECT TO THESE OR
YOU SHOULD BE ABLE TO SHOW THAT WHAT IS BEING SAID CANNOT BE UNDERSTOOD
BECAUSE IT IS NONSENSE IN THE CONTEXT AT HAND.
3. If we attempt nonetheless to clarify the content of Proposition 2,
given the claims made in Propositions 1, 3, 4 and the rest of the
paper,
it appears that it must imply that the projection of the feasible
polytope
onto the variables y_{isjisj} yields the convex hull of
{ v_g | g a c.a.s.s. path}, where c.a.s.s. paths and v_g are as
defined in
my previous post <cmote5$al...@lydian.ccrwest.org>. Given this,
it can
be shown, using similar reasoning to my previous post, that
Proposition 2
is in conflict with Yannakakis's 1988 result. I give the argument
in an
appendix at the end of this post.
4. Re the remarks on Yannakakis's result near the bottom of p. 12, I
will
point out that in order for a LP formulation of the TSP to be
symmetric,
Yannakakis does not require that the stages of the tour be treated
symmetrically, or even that they be expressed at all. Symmetry
under
permutation of cities (in a sense defined in Yannakakis's paper) is
all
that is required. Of course, Diaby's formulation is not symmetric
in this
sense, because city 1 is treated differently from the other cities.
However, Yannakakis's proof can be adapted to handle this, as I
outline
below and in my previous post.
I SUGGEST YOU READ YANNAKAKIS' WORK MORE CAREFULLY ALSO, AS I SUGGESTED
TO YOU IN MY RESPONSE TO YOUR PREVIOUS POSTING ON THIS TOPIC, AND WOULD
REFER YOU TO THAT RESPONSE.
--
tc...@lsa.umich.edu
<moustap...@business.uconn.edu> wrote:
[comments deleted]
Without getting into any of the technical details here, let me just give you
a few background facts that may be of use to you if you do indeed have your
eye on the Clay prize.
As I quoted before, the CMI requires that a purported solution gain
general acceptance in the mathematical community before they will
bother considering it for a prize. USENET, of course, is not a
terribly good sample of the "mathematical community." However, David
Moews is an outstanding mathematician. Just to mention one of his many
achievements, he was a three-time Putnam fellow, achieving a perfect
120/120 score once. You should consider it an honor to have him take
the time to study your paper. If he says that something is unclear,
and you think it is clear, then I would bet dollars to doughnuts that
the statement in question is in fact unclear and that you would do well
to understand what the objection is and address it directly. More to
the point, if someone purports to have solved a major open problem that
has had innumerable false proofs, then the burden of proof lies on the
solver to convince others; the burden of proof does *not* lie on the
mathematical community to find the mistake in an unclearly written
paper. If someone like David Moews finds a problem with your paper,
then you can bet that most people are going to take his word for it
over yours.
Again, this is not to take sides on the particular technical issue
under debate, because I haven't studied your paper. It's just some
practical advice about how to go about gaining credibility for your
work.
moustap...@business.uconn.edu
t...@lsa.umich.edu wrote:
> In article <1114994341....@f14g2000cwb.googlegroups.com>,
> <moustap...@business.uconn.edu> wrote:
> [comments deleted]
>
> Without getting into any of the technical details here, let me just
give you
> a few background facts that may be of use to you if you do indeed
have your
> eye on the Clay prize.
>
> As I quoted before, the CMI requires that a purported solution gain
> general acceptance in the mathematical community before they will
> bother considering it for a prize. USENET, of course, is not a
> terribly good sample of the "mathematical community."
I CAN ASSURE YOU THAT THE MOTIVATION FOR MY WORK WAS PURELY FOR THE
INTELLECT CHALLENGE. I ONLY FOUND OUT ABOUT THE CLAY PRIZE SOME TIME
LAST OCTOBER (2004), AFTER I HAD COMPLETED THE CURRENT WORK. I HAD
SCHEDULED A PRESENTATION AT MY DEPT HERE. A COLLEAGUE OF MINE SAW THE
ANNOUNCEMENT AND SENT ME AN EMAIL IN WHICH HE ASKED IF I WAS AWARE THAT
THERE WAS A "SUBSTANTIAL PRIZE" ON THIS PROBLEM. I RESPONDED THAT I DID
NOT, AND EVEN JOKINGLY INQUIRED AS TO HOW SUBSTANTIAL? HE THEN INFORMED
ME OF THE CLAY INSTITUTE PRIZE.
MY INTEREST IN THE TSP DATES BACK TO MY FIRST COURSES IN MATHEMATICAL
PROGRAMMING, MORE THAN 20 YEAR AGO.
However, David
> Moews is an outstanding mathematician. Just to mention one of his
many
> achievements, he was a three-time Putnam fellow, achieving a perfect
> 120/120 score once. You should consider it an honor to have him take
> the time to study your paper.
PLEASE, FORGIVE ME FOR NOT KNOWING ABOUT DAVID MOEWS.
If he says that something is unclear,
> and you think it is clear, then I would bet dollars to doughnuts that
> the statement in question is in fact unclear and that you would do
well
> to understand what the objection is and address it directly. More to
> the point, if someone purports to have solved a major open problem
that
> has had innumerable false proofs, then the burden of proof lies on
the
> solver to convince others; the burden of proof does *not* lie on the
> mathematical community to find the mistake in an unclearly written
> paper. If someone like David Moews finds a problem with your paper,
> then you can bet that most people are going to take his word for it
> over yours.
>
> Again, this is not to take sides on the particular technical issue
> under debate, because I haven't studied your paper. It's just some
> practical advice about how to go about gaining credibility for your
> work.
I APPRECIATE YOUR ADVICE AND THANK YOU FOR IT. AS I STATED ABOVE, I DO
NOT KNOW DAVID MOEWS. THE FIRST TIME I HEARD OF HIM IS THRU THIS USENET
WHEN HE POSTED ABOUT MY PAPER. I BELIEVE I SPECIFICALLY RESPONDED TO
HIS STATEMENTS ABOUT MY WORK. I STAND BY WHAT I HAVE SAID IN THAT
RESPECT AND HOPE NONE OF IT IS TAKEN PERSONALLY. AFTER ALL, AREN'T WE
ALL SUPPOSED TO BE "TRUTH SEEKERS?"
tc...@lsa.umich.edu
> z_{ijupvkrt}'s are only a collection of variables, and it is not
>clear what it means to locate in them a path of positive flow, nor why
>this should be possible.
>
>ARE YOU NOT STATING, AGAIN, THAT YOU DON'T UNDERSTAND? THE Y AND Z'S
>ARE CONSTRAINED VARIABLES WITHIN A CLEARLY-STATED MODEL AND ARE PARTS
>OF A DETAILED EXPOSITION. I THINK YOU SHOULD MAKE THE EFFORT TO
>UNDERSTAND WHATEVER IS BEING SAID ABOUT THEM WITH RESPECT TO THESE OR
>YOU SHOULD BE ABLE TO SHOW THAT WHAT IS BEING SAID CANNOT BE UNDERSTOOD
>BECAUSE IT IS NONSENSE IN THE CONTEXT AT HAND.
O.K., I took at least a couple of minutes to understand David's
objection. He's right; Proposition 2 is unclear. There is nothing
unclear about the first sentence of Proposition 2, or about the
definition of a c.a.s.s. path. However, it is unclear what it means
for (y,z) to "consist" of a collection of c.a.s.s. paths. As David
said, (y,z) is a bunch of numbers, but is not a set of paths. In what
sense does this set of numbers "consist of a collection of c.a.s.s.
paths"? This needs to be formally defined.
moustap...@business.uconn.edu
THE Y'S AND Z'S ARE NUMBERS. BUT, THEY ARE ALSO VARIABLES THAT ARE
FURTHER DEFINED (IN ADDITION TO THEIR FORMAL DEFINITIONS) BY THE
CONSTRAINTS OF THE MATH PROG PROBLEM IN WHICH THEY ARE USED. WITHIN THE
MATH PROG PROBLEM THEY ARE CONSTRAINED SO THAT THEIR POSITIVE
COMPONENTS ALWAYS CORRESPOND TO (OR "CONSIST OF") SETS OF PATHS.
PROPOSITION 2 SIMPLY GIVES FURTHER CHARACTERIZATIONS OF THOSE PATHS.
Patricia Shanahan
> In article <1114994341....@f14g2000cwb.googlegroups.com>,
> <moustap...@business.uconn.edu> wrote:
>
>>However, a priori, the y_{isjkrt}'s and
>>z_{ijupvkrt}'s are only a collection of variables, and it is not
>>clear what it means to locate in them a path of positive flow, nor why
>>this should be possible.
>>
>>ARE YOU NOT STATING, AGAIN, THAT YOU DON'T UNDERSTAND? THE Y AND Z'S
>>ARE CONSTRAINED VARIABLES WITHIN A CLEARLY-STATED MODEL AND ARE PARTS
>>OF A DETAILED EXPOSITION. I THINK YOU SHOULD MAKE THE EFFORT TO
>>UNDERSTAND WHATEVER IS BEING SAID ABOUT THEM WITH RESPECT TO THESE OR
>>YOU SHOULD BE ABLE TO SHOW THAT WHAT IS BEING SAID CANNOT BE UNDERSTOOD
>>BECAUSE IT IS NONSENSE IN THE CONTEXT AT HAND.
>
>
> O.K., I took at least a couple of minutes to understand David's
> objection. He's right; Proposition 2 is unclear. There is nothing
> unclear about the first sentence of Proposition 2, or about the
> definition of a c.a.s.s. path. However, it is unclear what it means
> for (y,z) to "consist" of a collection of c.a.s.s. paths. As David
> said, (y,z) is a bunch of numbers, but is not a set of paths. In what
> sense does this set of numbers "consist of a collection of c.a.s.s.
> paths"? This needs to be formally defined.
I gave up at the same point. I knew I didn't fully grasp the
meaning of Proposition 2, and it seemed central to the rest
of the paper. Admittedly, I'm more of a computer scientist
than mathematician, but it's another data point.
Clarifying Proposition 2 would clearly tend to increase the
number of readers who get past that point in the paper.
My particular concern was the mapping from a solution to the
LP problem to a solution to the original TSP problem. In
order for the proof to be valid, that mapping must not only
be proved to exist, but must be proved to be computable in
polynomial time. I couldn't find where that was proved, but
it may be obvious given proper understanding of Proposition
2 and later points that depend on it.
Patricia
moustap...@business.uconn.edu
Patricia Shanahan wrote:
> tc...@lsa.umich.edu wrote:
>
> > O.K., I took at least a couple of minutes to understand David's
> > objection. He's right; Proposition 2 is unclear. There is nothing
> > unclear about the first sentence of Proposition 2, or about the
> > definition of a c.a.s.s. path. However, it is unclear what it
means
> > for (y,z) to "consist" of a collection of c.a.s.s. paths. As David
> > said, (y,z) is a bunch of numbers, but is not a set of paths. In
what
> > sense does this set of numbers "consist of a collection of c.a.s.s.
> > paths"? This needs to be formally defined.
>
> I gave up at the same point. I knew I didn't fully grasp the
> meaning of Proposition 2, and it seemed central to the rest
> of the paper. Admittedly, I'm more of a computer scientist
> than mathematician, but it's another data point.
ACTUALLY, I THINK THAT JUST LIKE THERE ARE DIFFERENCES BETWEEN
STATISTICS AND "PURE MATHEMATICS", THERE ARE DIFFERENCES BETWEEN
"MATHEMATICAL PROGRAMMING" AND "PURE MATHEMATICS." IN THE CASE OF
MATHEMATICAL PROGRAMMING, I THINK THAT THOSE DIFFERENCES ARISE
PRECISELY BECAUSE OF THE CONCEPTS OF "CONSTRAINTS." MY PAPER IS
WRITTEN FROM THE PERSPECTIVE OF A MATH. PROGRAMMER -WHICH, I CONSIDER
MYSELF TO BE- AND THAT SEEMS TO BE WHAT IS CREATING ALL THE APPARENT
COMMUNICATION PROBLEM.
>
> Clarifying Proposition 2 would clearly tend to increase the
> number of readers who get past that point in the paper.
I WILL TRY TO FIND ANOTHER WAY TO EXPRESS THE IDEA AND DO A POSTING.
>
> My particular concern was the mapping from a solution to the
> LP problem to a solution to the original TSP problem. In
> order for the proof to be valid, that mapping must not only
> be proved to exist, but must be proved to be computable in
> polynomial time. I couldn't find where that was proved, but
> it may be obvious given proper understanding of Proposition
> 2 and later points that depend on it.
I THINK THIS WILL FOLLOW ONCE YOU UNDERSTAND PROPOSITION 2, SINCE IT IS
WELL ESTABLISHED THAT LP'S CAN BE SOLVED IN POLYNOMIAL TIME.
>
> Patricia
Patricia Shanahan
> Patricia Shanahan wrote:
...
>> I gave up at the same point. I knew I didn't fully
>> grasp the meaning of Proposition 2, and it seemed
>> central to the rest of the paper. Admittedly, I'm more
>> of a computer scientist than mathematician, but it's
>> another data point.
>
>
> ACTUALLY, I THINK THAT JUST LIKE THERE ARE DIFFERENCES
> BETWEEN STATISTICS AND "PURE MATHEMATICS", THERE ARE
> DIFFERENCES BETWEEN "MATHEMATICAL PROGRAMMING" AND "PURE
> MATHEMATICS." IN THE CASE OF MATHEMATICAL PROGRAMMING, I
> THINK THAT THOSE DIFFERENCES ARISE PRECISELY BECAUSE OF
> THE CONCEPTS OF "CONSTRAINTS." MY PAPER IS WRITTEN FROM
> THE PERSPECTIVE OF A MATH. PROGRAMMER -WHICH, I CONSIDER
> MYSELF TO BE- AND THAT SEEMS TO BE WHAT IS CREATING ALL
> THE APPARENT COMMUNICATION PROBLEM.
Ah, that may be why you don't play the proof review game
quite the way the mathematicians expect it to be played.
The first thing is to realize that a proof is a form of
communication. Its purpose is to convince readers that the
proposition MUST be true. To achieve that, as well as being
logically valid, it must be understood. Although readers
will make reasonable efforts to understand, ultimately the
burden is on you to make your proof both clear and convincing.
You cannot insist on counter-examples. After all, anyone
could have claimed to have proved P != NP, by "Because I say
so", and insisted on a counterexample to invalidate their
proof. The great open questions are typically propositions
for which there is neither an accepted proof nor a known
counter-example. Your proof has to convince the rest of us
that there is no possibility that a counter-example exists.
If you go back to David Moews' article, he told you that one
of your propositions was unclear. Giving a possible
interpretation is a constructive way of handling something
that seems insufficiently defined. If it is the intended
interpretation, it advances the discussion. If it is not the
intended interpretation, it illustrates the ambiguity.
I read that as an invitation to either accept his
interpretation, changing Proposition 2 to incorporate it, or
to reword Proposition 2 to make his interpretation obviously
wrong and ensure that all readers will pick yours instead,
or to point out where, prior to Proposition 2, you defined
its terminology. Just telling people they need to read
better does not get you any closer to an understandable
proof, and isn't a valid move in the proof review game.
In general, people are going to poke at your proof by
pointing out steps that are either unclear or seem incorrect
to them. That poking does not mean they are hostile to you,
it is the proper role of readers in the proof review game.
Your role, as the writer of the proof, is to clarify the
unclear, correct any typos or other errors, and explain why
each questioned step is valid.
If your proof is valid, it is of incredible significance,
perhaps more so than you realize. It is a truly
extraordinary claim, and will be poked and prodded in every
possible way to try to find any weaknesses. If you play
along with the proof review game, and try to clarify and
correct as needed, the end result will either be
understanding of what is wrong with your article, or a clear
proof of a very important, and somewhat surprising, fact.
Incidentally, I would strongly recommend dropping the all
caps responses. I know, intellectually, that you are not
shouting at me. It still feels like shouting, because whole
word capitalization in newsgroup postings is normally used
for emphasis.
Patricia
moustap...@business.uconn.edu
I thank you for these constructive comments. //Moustapha.
David Moews
According to the 12-II-2005 revision of Diaby's paper, I believe
his proposed algorithm for solving the TSP is as follows:
-----
DEFINITION. A ``c.a.s.s. path'' is a choice, for each time in the
set {1, ..., n-1}, of a city in the set {2, ..., n},
such that each city is chosen exactly once.
DIABY TSP ALGORITHM.
INPUT. A number n of cities, and travel costs t_{ij} from
city i to city j, where i and j are in {1, ..., n}.
We assume that t_{ij} is nonnegative, and that it is
infinite if i = j.
OUTPUT. A sequence of numbers C_1, ..., C_n, where C_i is the
city visited at time i in the lowest-cost tour.
STEP 1. Using the t_{ij}'s, define the c_{isj}'s as on p. 6 of the Diaby
paper.
STEP 2. Find the optimal solution of the linear programming problem
\overline{IP} given on p. 12.
STEP 3. We now look at the variables y_{isjisj}. For some (unique) c.a.s.s.
path, it will be the case that for each i, s, and j, y_{isjisj} is
1 if city i is chosen by the path at time s and city j is chosen at
time s+1, and is 0 otherwise.
STEP 4. For i in {1, ..., n-1}, let C_i be the city chosen at time i
by the c.a.s.s. path determined in Step 3. Let C_n be 1.
-----
I hope that this clarifies the way in which the TSP solution is recovered
from the LP solution.
2. Prof. Diaby,
Putting aside the typo and the question of the clarity of the statement and
proof of Proposition 2, my main point is that the correctness of your
revised algorithm is still in conflict with Yannakakis's result, which,
assuming that your algorithm is as outlined above, implies that there is
some input on which it fails. For the record, I will give the proof below.
3. Tim,
The vagueness of Proposition 2 doesn't make it any more difficult to
find an example where Diaby's algorithm clearly fails to solve the
TSP. In fact, by 2., there has to be some such example, and
Yannakakis's proof can be used to easily construct one. Unfortunately,
the counterexample constructed will be rather large (59 cities.)
--
David Moews dmo...@xraysgi.ims.uconn.edu
-----
PROOF OF 2.---
For each two-element subset {i, j} of {2, ..., n}, define a new variable
x_{i,j} by
x_{i,j} := y_{i1ji1j} + ... + y_{i(n-2)ji(n-2)j}
+ y_{j1ij1i} + ... + y_{j(n-2)ij(n-2)i}.
[This definition should replace the definition used in
<cmote5$al6$1...@lydian.ccrwest.org>; that definition was incorrect.]
Look at the projection P of the feasible polytope of the LP problem
\overline{IP} onto the x_{i,j}'s. From (2.27), it follows that P
is bounded. Now, let Q be the complete graph with vertices {2, ..., n},
let H be the hypercube defined by the inequalities 0 <= x_{i,j} <= 1
(2 <= i < j <= n), and let V be the set of points { w_q | q a Hamiltonian
path of Q }, where the value of x_{i,j} at w_q is 1 if the edge {i,j} is
in q and 0 otherwise. If P is not contained in H, it must have some
vertex v outside of H; this vertex is clearly not in V. Otherwise, let P
be contained in H. For each v in V, there is some feasible solution of
problem \overline{IP} given in Diaby's Proposition 1 which projects onto
v, so v is in P. Each such v is a vertex of H and therefore must also be
a vertex of P. Now, take n to be large enough so that the constructions
in <cmote5$al6$1...@lydian.ccrwest.org> and Theorem 1 in Yannakakis
(J. Computer and System Sciences, 43, 441--466) can be carried out.
The reasoning in <cmote5$al6$1...@lydian.ccrwest.org> then demonstrates
that P cannot equal the convex hull of V. Therefore, P must have some
vertex which is not in V. We conclude in either case that P has some
vertex v' which is not in V. Let K be a supporting hyperplane of P
through v', let K have the equation
\sum_{ {i,j} } k_{i,j} x_{i,j} = u,
and let P be contained in the set
S := {x_{i,j}: \sum_{ {i,j} } k_{i,j} x_{i,j} >= u}.
The equations (2.14) and (2.15) give
\sum_{i, j} y_{isjisj} = 1 for each s in {1, ..., n-2},
and since we assume (p. 5) that t_{ii} is infinite, we also have c_{isi}
infinite, so we may as well assume that y_{isiisi} always equals 0.
Therefore, P is contained in the hyperplane
\sum_{ {i,j} } x_{i,j} = n-2.
It follows that, if for some D > 0, we increase each k_{i,j} by D and
increase u by D(n-2), K will still be a supporting hyperplane of P
through v' such that P is contained in S. By doing this for some
suitable D, we may assume that each k_{i,j} is positive. Now set
t_{ij} := infinity, if 1 <= i = j <= n,
t_{ij} := k_{i,j}, if 2 <= i <= n,
2 <= j <= n,
and i does not equal j,
and
t_{ij} := 0, if either
i = 1 and 2 <= j <= n or
2 <= i <= n and j = 1.
We now have
c_{isj} = k_{i,j}, if 2 <= i, j <= n,
1 <= s <= n-2,
and i does not equal j,
c_{isj} = infinity, if 2 <= i = j <= n,
1 <= s <= n-2.
Assuming as before that y_{isiisi} equals 0, the objective function
of problem \overline{IP} is then equal to
\sum_{ {i,j} } k_{i,j} x_{i,j},
so the optimal solution of problem \overline{IP} will be at v'. However,
if Step 3 of the Diaby algorithm succeeds, the y_{isjisj}'s must correspond
to some c.a.s.s. path, so the x_{i,j}'s must be at the corresponding
vertex in V. Since v' is not in V, we conclude that the Diaby algorithm
does not succeed.
--
David Moews dmo...@xraysgi.ims.uconn.edu
David Moews
completely explained why the y_{isiisi}'s can be taken to be zero.
The reason is as follows: by Proposition 1, we know that feasible
solutions to problem \overline{IP} exist with finite objective function.
Therefore, the optimal solution must also have finite objective function,
and since, if any y_{isi} is positive, the objective function is infinite,
the optimal solution must be in the subspace where each y_{isi} is zero.
The behavior of the Diaby algorithm is therefore not changed if
we add the constraints
y_{isi} = 0, i in {2, ..., n}, s in {1, ..., n-1}
to problem \overline{IP}, so, in our analysis of the algorithm, we can assume
that this has already been done. Since these constraints are
symmetric with respect to permutations of i, the construction in
<cmote5$al6$1...@lydian.ccrwest.org> still works.
--
David Moews dmo...@xraysgi.ims.uconn.edu
moustap...@business.uconn.edu
I hope you will respond to the points I made above?
dmo...@xraysgi.ims.uconn.edu
moustap...@business.uconn.edu
By the way, in my comments above, I meant to say that Yannakakis's
results apply to "symmetric LP's" (not "symmetric TSP's"). Also, the
unfinished sentence starting with " Your attitude" should be ignored.
It is just typo. //MD
tc...@lsa.umich.edu
<moustap...@business.uconn.edu> wrote:
>Your overall approach for demonstrating the contradiction you want
>(unless that approach is different from what you have posted before) is
>invalid. Yannakakis's results apply to symmetric TSP's. The approach
>you are using can be applied to any LP formulation of the TSP, which
>means that basically, your claim is really that the TSP cannot be
>formulated as an LP (any LP)! That is clearly not what Yannakakis says.
>(By the way, why do you think Yannakakis takes such great care to limit
>his results to symmetric problems? Do you think you know the scope of
>his work better than him?)
Actually, it is you that misunderstands the situation. Of course,
David Moews understands that Yannakakis's result applies only to
symmetric LP's. The structure of his argument is, at a high level,
that if your *non-symmetric* LP formulation is correct, then one
can construct a *symmetric* LP formulation in contradiction with
Yannakakis's theorem.
>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).
These paragraphs also betray a fundamental misunderstanding.
Yannakakis's theorem does not apply only to LP's without redundant
constraints. Of course, in practice one might apply pre-processing and
remove obviously redundant constraints, but this does not change the
statement of Yannakakis's theorem.
I don't have access to the journal version of Yannakakis's paper at the
moment, only the STOC extended abstract, but in the latter, the remark
about minimal LP's is irrelevant to the discussion at hand. The point
is that the statement of Yannakakis's theorem stands on its own, and
even if minimal LP's are considered at some point during the proof,
this does not mean that the theorem applies only to minimal LP's.
Craig Feinstein
I only have access to Diaby's paper, not Yannakakis'. Without referring
to Yannakakis, can you say where the logical flaw in Diaby's proof is,
assuming that a flaw exists?
Craig
David Moews
<moustap...@business.uconn.edu> wrote:
|Your overall approach for demonstrating the contradiction you want
|(unless that approach is different from what you have posted before) is
|invalid. Yannakakis's results apply to symmetric TSP's. The approach
|you are using can be applied to any LP formulation of the TSP, which
|means that basically, your claim is really that the TSP cannot be
|formulated as an LP (any LP)!
I don't think my approach can be applied to an arbitrary LP formulation
of the TSP. If you see a way to do this, I'd like to ask you to indicate
it, as the result that the TSP can't be formulated as a (small) LP problem
would be very interesting.
|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.
Introducing the x_{i, j}'s clearly does not change the shape of
the feasible polytope, although it raises the dimensionality of its
ambient space. The reason for introducing them is that we wish to
simplify the feasible polytope by projecting it onto the x_{i, j}'s.
|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).
Minimality is not relevant here. The logical flow of the proof is as follows:
1. We start with a formulation (minimal or not) of a linear programming
problem which claims to express the matching polytope and is symmetric
under vertex permutation.
2. Since the LP problem is symmetric, its feasible polytope is also symmetric.
3. Yannakakis now proves (JCSS 43, 441--466, at 448) that this polytope can
be described by a minimal symmetric LP problem.
The formulation we start with need not be minimal.
|[...]
|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.
As I have said, although it is not symmetric, Yannakakis's proof can be
adapted to handle it. Yannakakis's proof is as follows:
1. He proves (Theorem 1) that the matching polytope cannot be expressed
by a small symmetric LP.
2. He proves that if there is a small symmetric LP expression of the
TSP polytope, it can be used to construct a small symmetric LP expression
of the matching polytope.
3. Therefore, no small symmetric LP expression of the TSP polytope exists
(Theorem 2).
My construction is almost identical to Yannakakis's.
2'. I prove that if there is a small symmetric LP problem which expresses
the Hamiltonian path polytope, it can be used to construct a small
symmetric LP problem which expresses the matching polytope.
3'. Therefore, no small symmetric LP problem which expresses the Hamiltonian
path polytope exists.
4'. Your LP formulation of the TSP immediately gives a small symmetric LP
problem which expresses the Hamiltonian path polytope.
--
David Moews dmo...@xraysgi.ims.uconn.edu