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

Hi,

I expected such answer. In mine opinion generating so large structures
is unpossible at all (think of time required - if one equation takes 1
second then definition itself requires 1.115.689 YEARS!!!

That's why I have designed flow "by hand" and then generated ONLY THIS
EQUATIONS that apply to mine FLOW. You have to look at source code -
especially in part where all equations are generated (it is quite clear
and I even use your symbols y_i_r_j_u_p_v ect.). I assume that all
other variables are equal to zero.

You may check that:
- every equation containing non-zero variable is generated
- every non zero variables is used in all equations it should be
- every equation from section 3 of your article is implemented

And it is consistent (in terms of your model) solution.

Once again - to see why your method is incorrect you have to check
large instances. If you point out that on figures for 1 dimension there
are "errors" in terms of 3D restrictions... that is obvious :). And I
write it in my paper (after introducing y's example for x's is solved
correctly). Then I show 2D example being counter example for y's...
which for sure can be solved correctly after introducing z's. But then
we can show example how to beat restrictions for z's model... And so
ON. If your model contained N dimensions then we could build (N+1)
dimension "valleys" as counter example...

Looking from other hand - if you think of integer programming only xisj
is enough to make every solution correct... But after relaxing
"integer" requirement it does not. Why do you think that making 3D
restrictions is enouhg? Why not 4D? Or 6D? That refers to your
proposition 4. You claim that every feasible solution for BLP consists
of TSP tours. What I'm showing is that feasible solution for BLP
consists of "paths" which are not TSP tours, but when we join them we
have feasible solution. in "proof" of this proposition at every step
you assume that tours are correct solutions for TSP but in general they
may be incorrect.

Cheers,

Radek Hofman

On Oct 24, 10:02 pm, moustapha.di...@xxxxxxxxxxxxxxxxxx wrote:
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.zipyoucan 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@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx 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- Hide quoted text -- Show quoted text -- Hide quoted text -- Show quoted text -

.

Relevant Pages

  • =?windows-1252?Q?The_Time=92s_Completion=2C_or_End_of_the_Times_=28by_Rom?= =?windows-1252?Q
    ... This count is scientifically based on the power 10^22 of ... 3×3 of the energy of the same flow). ... dimension of the electro-magnetic flow. ... Have we to avoid this DIVINE HELP... ...
    (alt.religion.christian)
  • To know the end of the world by calculus
    ... This count is scientifically based on the power 10^22 of ... 3×3 of the energy of the same flow). ... dimension of the electro-magnetic flow. ... Have we to avoid this DIVINE HELP... ...
    (sci.physics.relativity)
  • Is time only a half dimension?
    ... Time seems for now to be able to flow only in one direction. ... Why in relativity equation time is taken as a full dimension, ... Can be thinking that relativity equation are all wrong, ... How would the realtivity equation look like using time as a half ...
    (sci.physics.relativity)