[Top][All Lists]
[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
example1_0_1.out
Description: Text document
example1_0_1.tsp
Description: Text document
example1_0_1.out
Description: Text document
- [Bug-glpk] Re: [Help-glpk] Problems with TSPSOL,
Oscar Gustafsson <=