Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- From: "Radoslaw Hofman" <radekh@xxxxxxxxx>
- Date: Sun, 22 Oct 2006 15:15:00 +0200
Hi again,
I have lookead back at equation 2.14 you mention - in mine counter example
it is fulfilled perfectly because I do not generate any variable which may
cause violation of this restriction (it is checked in check_x and check_y
procedure. This is equivalent to setting them to zero.
For example - in 2.14 you do not allow such variable y_{i,r,j,k,r,t} for
i!=k and j!=t - in check y I'am chesking that no y with same stage appears
in any equation.
Please use program I prepared and posted in previous post - it implements
EVERY restriction from your latest article! And shows why solution is
incorrect.
I am uploading (at this moment) ziped version of program to my website, and
it'll be avaliable under adresses:
http://www.teycom.pl/diaby/diaby_counter_example.zip - program itself 5,7 kb
http://www.teycom.pl/diaby/variables_z.zip - variables with their values 7
Mb
http://www.teycom.pl/diaby/equations.zip - variables with their values
(don't know yet - it is uploading) Mb
Please notice that to avoid decimal values I set TOTAL FLOW2592, so if you
want it to be from 0 to 1 you have to divide every value by 2592 (but not
necessarly - it is the same :) ).
Cheers,
Radek Hofman
Uzytkownik <moustapha.diaby@xxxxxxxxxxxxxxxxxx> napisal w wiadomosci
news:1161355180.138222.138850@xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
Mr. Hofman,
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.
//MD
.
- References:
- Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- From: Radosław Hofman
- Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- From: moustapha . diaby
- Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- Prev by Date: Re: Top down parsing
- Next by Date: Re: Parse tree problem
- Previous by thread: Re: Counter example for Mr. Diaby algorithm solving TSP problem in polynomial time
- Next by thread: Parse tree problem
- Index(es):
Relevant Pages
|
