# 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

counter-example, 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 inter-city

costs, before such a counter-example 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

counter-example 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

counter-example 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 inter-city 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

- 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):