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

This post is repeated, because (I think that it is problem with attachenent)
it was not delivered to every NNTP server.

Attachement can be downloaded from
http://www.teycom.pl/diaby/diaby_counter_example.zip

New revision of mine text (including source of this program and EXPLAINED
how counter example is built (it is on page 20) is on the server (same
address:
http://www.teycom.pl/docs/Report_on_article_P_eq_NP.pdf )

Cheers

Radek Hofman

U¿ytkownik "Rados³aw Hofman" <radekh@xxxxxxxxx> napisa³ w wiadomo¶ci
news:ehe05g$i5h$1@xxxxxxxxxxxxxxxxxxxxxx
Hi,

Please read text carefully :)

Figures you mention correspond to y's model, so it is no problem that it
violates some z's restrictions... Please think of huge instances build in
way I have shown - and think why for presented models they produce
incorrect
instances :) In section 2.3 there is example for z's model.

I'll update six valleys example to 8 - it'll be bit more clear.

I've prepared all restrictions for y model (mentioned in original article
and added by me (to make it more difficult) and every equation is OK while
solution is better then optimal for TSP. The same instance is good enough
to
beat model from latest version of article (4 valleys, 3 paths in each)
because restriction 2.25 from previous version of article (the only one not
met by 4-valleys counter example) is removed :) )

Because of that all equations may be checked directly. I attach program in
perl (it can be run on any system) which will generate file with all
variables (it'll take even hours (it takes almost 3 h on my laptop) up to
512 MB of RAM and written files will take 33 MB (variables) and 169 MB
equations - there are 997'419 equations generated) and after that it will
generate Soplex LPT file with all equations. Moreover - every equation is
parsed, values of variables are substituted and equality is checked. Even
without soplex you are able to see that all conditions from your latest
version of article are fulfilled, and solution is incorrect (it is 4
valleys
with 3 paths example described in section 2.3 of mine article). If you
cannot find attachment (due to your news server restrictions) please check
new revision of article (it'll be in section 5.3 in few days).

Please notice that program produces all output to STDOUT (except variables,
which are stored in "variables_z.txt") so running it should look like:
perl program_name.pl >equations.lpt

Then you can run soplex with parameter -d0 (maximum violation of boundaries
set to 0). Running soplex is not necessary (as I mentioned all equations
are
evaluated - you may treat it as independent proof). If one wants to see
checking then I suggest that you:

- run program first time and wait until variables are generated, then you
can break with Ctrl+C
- edit file setting my $debug=1; on 25 line - this will produce additional
text for every equation

You may run it with debug for the first time as well, but generating
variables took me 2 GB of debug info, and I don't remember if I have
cleared
unnecessary prints :).

File is so small because in every loop I check if generating variables
makes
sense - I assume that all variables not generated by mine algorithm are
equal to 0, then checking check_any_x($i,'*',$j) returns answer if there is
flow from i-->j - if there is not, then all y's and z's including i,r,j are
equal to 0 and whole equation may be omitted (as far as 0==0 :-) ).


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









.