Re: Discussion regarding Mr. Diabys algorithm


Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1163694465.097726.258570@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

Radoslaw Hofman wrote:
Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1163626104.127115.292010@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


In summary I must conclude that you haven't written in this document
anything not written by you before. We all expect that you will stop
writing
"[...] is impossible" but show us all WHY. Especially that I gave you
pseudo-math explanation of mine objection above (see 2). You didn't prove
that:


What I mean is this:

Consider arc (5, 4, 6) in your "valley" B of Figure 13. It is
*impossible* to have a set of positive y variables (
y(5,4,6),(i(s),s,j(s)), s = 4, ..., 23) along with a set of positive
z-variables (z(5,4,6),(i(s),s,j(s)),(i(t),t,j(t))), s = 5 to 22; t =s+1
to 23) such that they satisfy all the constraints of my model or
Proposition 2 in my paper.

Please, think about it a little!

How would flow on this arc "travel" from stage 4 to stage 23 without
"revisiting" any of the only 6 levels in your "valley" B, when there
are no "back-flows" allowed as stipulated in constraints 2.14, and as
you have already said there are none in this usenet?

I think it would be helpful if you can show one set of y and z-values
for arc (5,4,6) from your "counter-example" that satisfies all the
constraints of my model. (Forget everything else.)

That's the point - it is obvious that single flow cannot fit to your
constraints. That's why I use many flows which summary may fit to all
constraints perfectly.



To show you a bit of this in different way:

Let us assume that there are flows:

5_5_6->6_6_7->7_7_8->8_8_7

6_5_7....

7_5_8....

.....



If you will build every combination of legal flows (no backflow to first arc
in row - as in first and second) and sum them then you will see that on
"upper level" everything is ok. You may see that each row is equivalent to
some y starting with first letters. There is then no illegal y and after
joining them you obtain model.



Same with z but you must build flows omitting first two arcs.



Now if you get enough of such "flows" you may meet all equations.



Think (a little) in such way:

- I assume that you agree that x_isj is not enough

- if you pick one arc then you have n^3 of this insufficient models... when
you add them then you will meet all restrictions for y's

- if you pick 2 arcs then it is n^6 of this insufficient models...



What makes you think that this time it will be different and only correct
TSP solutions will be feasible? For 2 arcs chosen it is still nothing more
then x_isj model... It is enough to prepare large enough instance to show
it.



So please don't write "impossible" - rather show which constraint is
violated in counter example (and I assure you that you cannot show it
because everything is compliant with your model) and prove in formal way
that it cannot exist.



When "playing" with sums (and your model summarizes flows) it is difficult
to trace what was taken to sum. For value 1 if I tell you that it is sum of
10 numbers for which every meets 0<=x<=1 then you cannot expect that these
numbers have certain properties (being for example proper fractions). In
fact they can be any values so proving that feasible solution corresponds to
original problem is much more then *important*.



Best regards,



Radek Hofman


.

Relevant Pages

  • Re: P=NP: Linear Programming Formulation of the TSP
    ... Any feasible solution to IPBAR can be generated as a sum ... of flows along c.a.s.s. ... multiple sums of c.a.s.s. ... The constraints link certain sums of path-flows, but that's not, at least not obviously, enough. ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... If you will build every combination of legal flows (no backflow to first arc ... The "formal proof" is Proposition 2. ... to trace what was taken to sum. ...
    (comp.theory)
  • Re: P vs NP solved?
    ... >>> subtract balance flows from other balanced flows, ... >> feasible solution gives us only polynomial many (order ... >>I may have been off on the number of constraints being order ...
    (comp.theory)
  • Re: P vs NP solved?
    ... > subtract balance flows from other balanced flows, ... If we think of flows as also distinguishing the commodity flowing on the path, then the constraints are not strong enough to uniquely identify a set of flows. ... A feasible solution gives us only polynomial many equations, so we cannot in general solve for M! ...
    (comp.theory)