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

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 file http://www.teycom.pl/diaby/equations.zip you 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.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1161706167.440628.61370@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxx


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


.

Relevant Pages

  • Re: The economics of Harry Potter
    ... Magic has a cost, it requires effort by magicians or spirits. ... Where does the extra energy come from? ... It could come from another dimension. ... For science fiction about conservation of energy and alternate ...
    (rec.arts.sf.written)
  • allowed member set MDX expression
    ... I'm trying to implement dynamic dimension security in a SSAS 2005 ... I have the "Cost Object" dimension consisting of two hierarchies: ... Cost Object Hierarchy ...
    (microsoft.public.sqlserver.olap)
  • Blank pivot when displaying a dimension member and a calculated member.
    ... And I have a calculated member called "TOTAL COST" created from ... this dimension which is. ... When I show the pivot, I have a case, where REVENUE is zero and COST ...
    (microsoft.public.office.developer.web.components)
  • Re: Multiselect dimension
    ... division dimension. ... Cost Division dimension is not used in the MDX source query. ... in calculated member, can you give example. ...
    (microsoft.public.sqlserver.olap)