Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time



On Oct 24, 12:59 pm, "Radoslaw Hofman" <rad...@xxxxxxxxx> wrote:
Hi,

Eeee... Are you joking? I asked in previous post to have a careful read of
mine paper... :)

In my paper it is clear that counter example is one with 32 nodes. I
stressed it several times in emails and posted program generating all
x_i_s_j, y_i_s_j_u_p_v and z_i_s_j_u_p_v_k_r_t. Now you gave me example with
8 nodes - I assume that this is one presented by me in section 2.1, but it
is there JUST TO SHOW IDEA!

In my paper I show idea: how you can "beat" first dimension of variables,
then second and finally third. And this third is counter example for your
method, as you are using 3 dimension of variables z_(1D)_(2D)_(3D).

Number of dimensions you define is so large that incorrect solutions can
only be seen on large instances - not 8 nodes you are showing, and claiming
that counter example is wrong :)
* for first dimension using 4 nodes is enough for counter example (see
section 2.1)
* for 2 dimensions (x and y variables) it is enough to have 20 nodes (see
section 2.2)
* for 3 dimensions (x, y and z) there is example with 32 nodes (in section
2.3)

BTW: what is largest instance you used your algorithm for?

In filehttp://www.teycom.pl/diaby/equations.zipyou can find EVERY EQUATION
you defined in latest version of article in section 3, and overall cost of
solution is better then optimal for TSP while every restriction is
fulfilled! So how are you going to "solve" this problem in other way? If
EVERY equation is there, and variables have their values assigned making
every equation correct then it is compliant with your model...

So please, before writting that you solved counter example:
Download program generating variables, costs and equations:http://www.teycom.pl/diaby/diaby_counter_example.zip

Or variables generated:http://www.teycom.pl/diaby/variables_z.zip

Or solve instance of 32 nodes with cost function described by algorithm
(nodes are grupped in four valleys A, D with 4 nodes, and B, C with 12
nodes - within valley cost is always 1 between valleys it is 1000):
sub get_cost
{
my ($i,$j)=@_;
my ($i_valley,$j_valley)=(0,0);
$i_valley='A' if (($i>=1)&&($i<=4));
$i_valley='B' if (($i>=4+1)&&($i<=4+12));
$i_valley='C' if (($i>=4+12+1)&&($i<=4+2*12));
$i_valley='D' if (($i>=4+2*12+1)&&($i<=4+2*12+4));
$j_valley='A' if (($j>=1)&&($j<=4));
$j_valley='B' if (($j>=4+1)&&($j<=4+12));
$j_valley='C' if (($j>=4+12+1)&&($j<=4+2*12));
$j_valley='D' if (($j>=4+2*12+1)&&($j<=4+2*12+4));
return 1 if ($i_valley eq $j_valley);
return 1000;

}Cheers,

Radek Hofman

Uzytkownik <moustapha.di...@xxxxxxxxxxxxxxxxxx> napisal w wiadomoscinews:1161706167.440628.61370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx



Mr. Hofman:

I do not have access to computing resources that can handle LP's with
a number on the order of 32^9 variables, and 32^7 constraints...

So, in a last effort, I am going to refer you back to my first posting:


"There are errors in your document. The flow structures you describe in
your figures 2 and 3 are not possible in my model. Specifically, in
Figure 3, the flow patterns over rows 5 -6 and rows 7-8 would violate
the "visit restrictions" constraints (constraints 2.14 in latest
version) of my model. Similarly, the flow patterns in Figure 4 (row 10,
columns 9&15) and (row 11, columns 4&10) and (row 16, cols 10&15)
violate the same constraints."

and point out to you that the above applies to all the figures with
"valleys" you have in your document.

//MD





Mr. Hofman,

I have written my LP model for your problem and run it in OSL. It
solves correctly (see
http://www.business.uconn.edu/users/mdiaby/tsplp/hofman).

//MD

.