Re: My LP Formulation of the TSP: Conclusions

On Mar 29, 7:48 am, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
Uzytkownik <moustapha.di...@xxxxxxxxxxxxxxxxxx> napisal w wiadomoscinews:1175165597.236162.220620@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx

The formulation is very "robust." So, even relaxations of it produce
optimal solutions in a lot of cases. That is why, we have to
ultimately rely on the mathematics of the situation.

Ok, so you are going to show us some mathematics now? There is no
"mathematics" in you paper...

Wow... that is what was written by me half year ago (that after inclusion
of
2.13 counter-example is invalid)... But you wrot that it is IMPOSIBLE to
check, so what happen that it is possible now?

The "spirit" of your "construction" scheme is destroyed in the final
model.

No... :)
If you let us all source codes of your program then I shall show you CE for
your model with 2.13 :)

The code will be made public in due course.

Meanwhile, I don't see why you should not be able to use the code you
used before to produce a new "counter-examples" for my model IMECS
proceedings model and the final model I just made public.


BTW: I still cannot understand why are you refusing to think about these
facts:
A. for polytope with 2^n vertexes there are O(2^n-1) facets
B. having O(n^7) (or even O(n^15)) restrictions it is IMPOSSIBLE to "cover"
every facet
C. if facet is not covered by restriction, then target function "paralell"
to this facet will give incorrect result


If you apply these argument to the case of the Assignment Polytope,
you will understand why they are invalid. By this reasining of yours,
the Assignment Polytope should require an exponential number of
constraints to describe.

....But, we have been here before, and I don't want to start going in
circles again.

It works even in 2D! Consider example: generate 2^n points fulfilling
(x-3)^2+(y-3)^2=1. Now you are trying to convince us that your linear model
containing O(n^c) lines will produce ALWAYS for ANY POSSIBLE TARGET FUNCTION
correct solution (correct distance between zero and nearest point from
generated solution set). It is obvious that it is not true! See examplehttp://www.teycom.pl/diaby/eq2.png

You have been going to extreme lengths to state the obvious: Namely,
that the solution to the LP relaxation of an IP need not be integer.


Why then having complicated multi-dimensional structure you claim to have
model "covering" any possible of O(2^n-1) facets? You do not know how this
structure "looks like" for n=100 because it is impossible to generate all
vertexes and check if you model is still correct. Unless you prove (using
mathematics) that number of facets is polynomially bounded untill your model
cannot be considered as correct.

You are are "hung up" on the obvious here also.

Here is what I hope will be a short resolution of this issue for you
(And, I am sorry, but I will not continue this discussion unless I
feel I can add to these):

1. Feasible set of IP includes all TSP tours
2. Feasible set of IP = Subset of feasible set of LP relaxation of IP
Hence,
3. Feasible set of LP relaxation includes all TSP tours
Hence,
4. (Convex Hull of LP) = (Set of convex combinations of extreme points
of LP), includes all TSP tours

Now,

5. Sometimes, Convex hull of LP relaxation = Convex Hull of IP. This
is the case of the Assignment Problem, which my model is a
reformulation of.

//MD


.