Re: Discussion regarding Mr. Diabys algorithm



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




As to Hoffman, I will make a more detailed document public when it is
ready, as I said previously.

//MD


See:
http://www.business.uconn.edu/users/mdiaby/tsplp/hofman/Ans_To_Hofman.pdf

//MD




That' it?? I'm disapointed - i really was hopeing to find some chalenge in
your answers. You described my way of construction the counter-example and
copied my figures... Only thing is few sentences in section 2. I shall quote
them:



"

2. Flaws in Hofman's "Constructs"

A major flaw in Hofman's "construction" scheme is that it overlooks the
impossibility of having the "salesman" (be it/he/she "full" or fractional)
visit n cities in more than n "travels" without visiting any city more than
once. This impossibility holds true in my model because of Propositions 2
and 3 in the paper. Furthermore, because of this impossibility, the flows
within each of the "valleys" where Hofman sends "fractional-salesmen" cannot
be feasible for my model.

"

Let me repeat:

1) visiting one city more then once is illegal for TSP, but your model
allows it as you cannot prevent such flow:

y_5_5_6_6_6_7 -> y_5_5_6_7_7_8 -> y_5_5_6_8_8_7 -> y_5_5_6_7_9_8 and so on
(cities 7 and 8 can be visited as many times as required when you "look"
from point of view of any chosen arc (of course if this chosen arc does not
link 7 nor 8)). Same for z - picking up two arcs for nodes a, b, c, d you
cannot prevent multi visits in cities e and f.

2) Your propositions concentrate on proving:

forall t in TSP-solutions exists b in BLP-feasible-solutions t subset b

But there is no proof in opposite direction:

exists b in BLP-feasible-solutions forall t in TSP-solutions overallCost(b)
= overallCost(t)

3) Maybe I am naïve but... How can you write "cannot be feasible for my
model" when such flow "lays" before your eyes, you have every variable with
value, every restriction from your model... and it exists!!!

4) Think about your model in such way:

- model having only x_isj variables can be decieved

- introducing y_isj_upv is nothing more then having n^3 models with x_isj

- if x_isj could be deceived then we can deceive each of n^3 models in such
way that they summary will sum up to flow "correct" for upper level

- introducing z_isj_upv_krt is nothing more then having n^3 models with
y_isj_upv or n^6 models with x_isj

- if x_isj and y_isj_upv could be deceived then we can deceive each of n^3
(or n^6) sub-models in such way that they summary will be "correct" for
upper levels



You can add another dimensions... If you cannot prevent x_isj to be correct
(remember that x_isj is enough for 0-1 programming!!) then how can you
expect that n^3 of such incorrect models will appear to be correct? Or n^6
of them? Or any other number of them?



If you really think that there is flaw in mine counter-example then you have
to show:

- equation from your BLP model being violated (all equations in equation
file are marked with number from your article - for example R211_X is for
Restriction 2.11 and X is next number)

- illegal variable - I think that you have already checked that there are
none of variables restricted by 2.14 in your paper, so all are legal



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:

forall b in BLP-feasible-solutions forall t in TSP-solutions
overallCost(b)>=overallCost(t)

and I have shown that it cannot be proved because:

exists b in BLP-feasible-solutions forall t in TSP-solutions
overallCost(b)<overallCost(t)

and this b is mine counter-example.



Best regards,



Radek Hofman


.