Re: My LP Formulation of the TSP: Conclusions


Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1175174009.499980.223400@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
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.

You could not accept my codes, so why should I bother and modify them in
aspect of risk that you will refuse to agree... I want to do it on yours :).

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

Wow, text below is exact presentation of your conceptual error!

1. Feasible set of IP includes all TSP tours
=> true

2. Feasible set of IP = Subset of feasible set of LP relaxation of IP
=> true

3. Feasible set of LP relaxation includes all TSP tours
=> true

4. (Convex Hull of LP) = (Set of convex combinations of extreme points
of LP), includes all TSP tours
=> true

But... there is still most important part missing
We all agree that LP includes all TSP tours, but... it contains MORE. You
couldn't prove that it is not inclusion but equivalence. Using your symbols:
(Convex Hull of LP) includes all TSP tours but (Convex Hull of LP) is not
equal to all TSP tours. There are fesible LP solutions that have nothing to
do with TSP tours.

Consider once more point 2. Fesible set of IP = SUBSET OF LP SOLUTIONS. But
there is other subset of LP solutions which intersection with IP is empty...
Even if you assume that this subset has another subset of solutions having
value between lowest and highest cost of TSP tour, there are still objects
outside. You couldn't prove that this last subset is empty.

In math language:
Set Of LP Feasible Solutions = Set of IP Feasible Solution UNION Set of IP
not-feasible solutions
Set of IP not-feasible solutions = Set of solutions with value between
lowest and highest cost of tour UNION Set of solutions with cost lower then
lowest tour or higher then highest cost of tsp tour

You have to agree that if this last set is NOT EMPTY then solution is
incorrect (any of such solutions cannot be considered as combination of
other solutions). You cannot prove that it is empty... I have showed that it
is not empty. Conclusions?

Radek Hofman



.