Re: Discussion regarding Mr. Diabys algorithm
 From: "Radoslaw Hofman" <radekh@xxxxxxxxx>
 Date: Sat, 11 Nov 2006 21:46:50 +0100
Uzytkownik "deepakc" <deepakc@xxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1163176404.767674.229170@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
king...@xxxxxxxxxxx wrote:
Hmmm...that will be possible, in my opinion. We could try and find a
counterexample, say with 6 cities, or 8 cities or 10 cities or 12
cities. But we have to do a lot of "playing around" with the intercity
costs, before such a counterexample for Diaby's Algorithm is found.
In fact, I would like to modify my above phrase from "Diaby's Algorithm
is absolutely independent of TSP size" to "the probability of finding a
counterexample increases with TSP size". And the reason is because the
overall number of constraints in Diaby's Model exceeds the number of
possible TSP tours, when N=6,8,10, or 12.
But I will stress that IT IS DEFINITELY POSSIBLE, for us to find a
counterexample for Diaby's Algorithm, when the N=6, 8, 10, etc. This
is because of the ILP to LP relaxation. But as I said, we have to a lot
of playing around with intercity costs, and some very good computers &
programs could help us do that.
Maybe it is possible to create such combination for small instances  my
goal was to to show that it has lower overall cost... It took me 32
cities... But if Diaby would have be more precise with his model (BLP would
have contained equation 2.13) then it would have been to weak  I would have
used 52 cities (remember that Moews predicted theoretical number of 59 as
"killing" for algorithm).
Best regards,
Radek Hofman
.
 References:
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: Radoslaw Hofman
 Re: Discussion regarding Mr. Diabys algorithm
 From: moustapha . diaby
 Re: Discussion regarding Mr. Diabys algorithm
 From: tchow
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: moustapha . diaby
 Re: Discussion regarding Mr. Diabys algorithm
 From: moustapha . diaby
 Re: Discussion regarding Mr. Diabys algorithm
 From: Radoslaw Hofman
 Re: Discussion regarding Mr. Diabys algorithm
 From: Radosław Hofman
 Re: Discussion regarding Mr. Diabys algorithm
 From: A . L .
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: Radoslaw Hofman
 Re: Discussion regarding Mr. Diabys algorithm
 From: Radosław Hofman
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 From: kingpin
 Re: Discussion regarding Mr. Diabys algorithm
 From: deepakc
 Re: Discussion regarding Mr. Diabys algorithm
 Prev by Date: Re: Discussion regarding Mr. Diabys algorithm
 Next by Date: Re: Discussion regarding Mr. Diabys algorithm
 Previous by thread: Re: Discussion regarding Mr. Diabys algorithm
 Next by thread: Re: Discussion regarding Mr. Diabys algorithm
 Index(es):
Relevant Pages
