bug-glpk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Bug-glpk] Re: [Help-glpk] Problems with TSPSOL


From: Oscar Gustafsson
Subject: [Bug-glpk] Re: [Help-glpk] Problems with TSPSOL
Date: Fri, 9 Mar 2007 15:03:05 +0100 (MET)

On Fri, 9 Mar 2007, Andrew Makhorin wrote:
To check the tspsol's result you can solve your tsp with Concorde by
submitting it to the NEOS server:
http://neos.mcs.anl.gov/neos/solvers/co:concorde/TSP.html
I ended up with installing Concorde and running some examples.

What I came up with is the following:

tspsol prints the correct objective function in the .out-file, but the solution provided seems to be the earlier obtained solution.

hod 326% /usr/local/bin/tspsol example1_0_1.tsp -o example1_0_1.out
tsp_read_data: reading TSP data from `example1_0_1.tsp'...
tsp_read_data: NAME: example1_0_1
tsp_read_data: TYPE: TSP
tsp_read_data: COMMENT: Generated by generatetsp.m address@hidden
tsp_read_data: DIMENSION: 41
tsp_read_data: EDGE_WEIGHT_TYPE: EXPLICIT
tsp_read_data: EDGE_WEIGHT_FORMAT: LOWER_DIAG_ROW
tsp_read_data: 49 lines were read
Initial tour length: 4.65e+08
Solving initial LP relaxation...
lpx_adv_basis: size of triangular part = 40
      0:   objval =   3.740000000e+08   infeas =   1.000000000e+00 (0)
      1:   objval =   4.650000000e+08   infeas =   0.000000000e+00 (1)
*     1:   objval =   4.650000000e+08   infeas =   0.000000000e+00 (1)
*     2:   objval =   4.650000000e+08   infeas =   0.000000000e+00 (0)
FOUND OPTIMAL SOLUTION TO LP RELAXATION
Integer optimization begins...
+     2:   ip_obj =   4.650000000e+08 >=              -inf (1; 0)
+   262:   ip_obj =   4.630000000e+08 >=   4.630000000e+08 (4; 0)
lpx_print_sol: writing LP problem solution to `example1_0_1.out'...
+   262:   ip_obj =   4.630000000e+08 >=     tree is empty (0; 7)
INTEGER OPTIMAL SOLUTION FOUND

When I check this solution it has a cost of 465.

From Concorde (LK-heuristic)

hod 300% ./linkern -o example1_0_1.out 
~/glpkmodels/FIRMAC/paperexample2/example1_0_1.tsp
Host: hod.isy.liu.se  Current process id: 14421
./linkern -o example1_0_1.out 
/home/tde/oscarg/glpkmodels/FIRMAC/paperexample2/example1_0_1.tsp
Chained Lin-Kernighan with seed 1173448614
Problem Name: example1_0_1
Problem Type: TSP
Generated by generatetsp.m address@hidden
Number of Nodes: 41
Explicit Lengths (CC_MATRIXNORM)
Using junk-norm nearest code
 201 edges
Time to find 8 nearest: 0.00
Grow a Quick-Boruvka tour
Length of Quick-Boruvka Tour: 471000000.00
Time to grow tour: 0.00
linkern ...
Starting Cycle: 471000000
   0 Steps   Best: 463000000   0.00 seconds
  41 Total Steps.
Best cycle length: 463000000
Lin-Kernighan Running Time: 0.16
Final Cycle: 463000000
Total Running Time: 0.16

For which the solution evaluates to 463.

This is true for other problems tested as well, so I guess that at least occassionally this bug is triggered.

With best regards

Oscar Gustafsson

Attachment: example1_0_1.out
Description: Text document

Attachment: example1_0_1.tsp
Description: Text document

Attachment: example1_0_1.out
Description: Text document


reply via email to

[Prev in Thread] Current Thread [Next in Thread]