Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time

Mr. Diaby,

I think that energy needed to download progrem generating all variables
with values and then all equations according to YOUR OWN model is thing
that is not exceeding your possibilities. After you would have done it
you would see exact counter example, and it not bigger then any
computer holding Windows XP could bare. And it is clear that for your
model this counter example is good - just run it!

Then you could possible see that EVERY EQUATION FORM YOUR MODEL
CONTAINING AT LEAST ONE NON-ZERO VARIABLE IS THERE! So wgat do you mean
by "poor mathematics" - it is your own model! I agree that mine
English is not as good as yours since I use this language occasionally,
but math? There is nothing but YOUR OWN EQUATIONS, so if you find them
"poor" then it is comment to your own article :-).

Finally I have pointed out proposition from your document which is
incorrect - proposition 4. You assume there that every possible
solution consists ONLY FROM VALID TSP TOURS! This is incorrect, because
you may combine some NON TSP TOURS and prepare instance perfectly
feasible for BLP having nothing common with solution for TSP.

You do not prove that BLP consists only from valid TSP tours, so if you
want gap to be found in your publication... here it is! You assume that
any path belongs to some hamiltion path, but in general we can have
many non-hamilton paths which combined together form model. This is
assumption in every proof in section about BLP... but think - what if
it is wrong? What if feasible for BLP model consist of non-TSP tours?
That is why I show it step by step - for !D, 2D and 3D...

This model would be correct if number of dimensions depended on
instance size for example log(n). But then complexity of your model
grows to 2^(3^log(n))=2^(n^c) what is greater then polynomial :-).

Let's think about in some figures. For n nodes we can have n!
solutions. If your BLP model is to present ANY subset of solutions than
it presents object from power-set over n!, this mean that it must be
strong enough to express 2^(n!) different objects (cardinality of
power-set). Your variables can define only X^(n^9) where X is some
constant presenting different values variables may have (remember that
problem is discrete!).

Then for any X, when n->inf. There is always 2^(n!) > X^(n^9), since
n!>c*n^9 for any constant c!

Hope that mine "poor math" including limens and powers is OK :-).

So it is clear that for large instances your model has limited
capability of presenting any set of solutions. If then it cannot
present every set of TSP tours then we may combine some non-TSP paths
that would look like set of TSP tours for your model.

Cheers,

Radek Hofman

.

Relevant Pages

  • Re: Discussion regarding Mr. Diabys algorithm
    ... that EVERY FEASIBLE SOLUTION IS COMBINATION OF TSP TOURS is false in same ... of BLP feasible solutions correspond ... if the polytope you are working on is a "hard one" (like the TSP ...
    (comp.theory)
  • Re: Discussion regarding Mr. Diabys algorithm
    ... any SET of tours. ... But after changing to non-integer version ... that BLP feasible solution cannot consist of non TSP-tours. ... feasible solution which has better overall cost then any of TSP solutions. ...
    (comp.theory)