[Help-glpk] concorde + glpk lp solver

[Andrew Makhorin]

I fixed a (silly) bug in the cplex-like interface to glpk api (please
see the bug-glpk mailing list), and then compiled Concorde, the package
for solving the symmetric TSP, with glpk 4.33 used as a base LP solver.
Below here are some results for TSPLIB 95, a library of the symmetric TSP
instances. Now Concorde works surprisingly well, though some important
features like strong branching and pivotin/pivotout are not implemented.


Andrew Makhorin


------------------------------------------------------------------------
Solver:     Concorde-03.12.19 (options used: -s 99)
            http://www.tsp.gatech.edu/concorde.html
LP Solver:  GLPK 4.34 (CPLEX-like interface module examples/cplex)
Computer:   Intel Pentium 4 CPU 3GHz, 2GB of RAM
Platform:   Cygwin 1.5.24 (Windows XP 5.1 Build 2600 Service Pack 4)
Compiler:   GCC 3.4.4 (options used: -O2)
Test set:
http://www.iwr.uni-heidelberg.de/groups/comopt/software/TSPLIB95/

Problem     Solution   B&B   Time, s
---------   --------   ---   -------
a280            2579     1      3.09
ali535        202339     1     21.88
att48          10628     1      0.20
att532         27686     7     74.31
bayg29          1610     1      0.08
bays29          2020     1      0.08
berlin52        7542     1      0.11
bier127       118282     1      0.62
brazil58       25395     1      0.23
brd14051
brg180          1950     1      0.34
burma14         3323     1      0.06
ch130           6110     1      0.92
ch150           6528     1      1.69
d1291
d15112
d1655
d18512
d198           15780     3      4.92
d2103
d493           35002     5    123.89
d657           48913    11    148.17
dantzig42        699     1      0.08
dsj1000     18660188    13    251.00
eil101                                 (failed due to CPXgetijdiv)
eil51            426     1      0.17
eil76            538     1      0.11
fl1400
fl1577
fl3795
fl417          11861     1     47.20
fnl4461
fri26            937     1      0.05
gil262          2378     3     10.39
gr120           6942     1      0.66
gr137          69853     1      2.09
gr17            2085     1      0.03
gr202          40160     1      3.97
gr21            2707     1      0.03
gr229         134602     7     19.45
gr24            1272     1      0.03
gr431         171414     9     40.67
gr48            5046     1      0.22
gr666         294358     3     40.23
gr96           55209     1      1.22
hk48           11461     1      0.08
kroA100        21282     1      0.41
kroA150        26524     1      2.09
kroA200        29368     1      2.44
kroB100        22141     1      1.20
kroB150        26130     1      1.66
kroB200        29437     1      1.41
kroC100        20749     1      0.42
kroD100        21294     1      0.50
kroE100        22068     1      0.94
lin105         14379     1      0.23
lin318         42029     1      4.28
nrw1379
p654           34643     1     17.08
pa561           2763    15    370.70
pcb1173        56892    11    370.30
pcb3038
pcb442         59778    13     35.86
pla33810
pla7397
pla85900
pr1002        259045     1     23.08
pr107          44303     1      0.38
pr124          59030     1      1.23
pr136          96772     1      2.19
pr144          58537     1      0.89
pr152          73682     1      2.73
pr226          80369     1      2.72
pr2392
pr264          49135     1      1.61
pr299          48191     3     14.52
pr439         107217    15    117.75
pr76          108159     1      0.95
rat195          2323     5     12.91
rat575          6773    19    202.52
rat783          8806     1     37.92
rat99           1211     1      0.50
rd100           7910     1      0.28
rd400          15281    11     74.41
rl11849
rl1304
rl1323
rl1889
rl5915
rl5934
si1032         92650     1     82.09
si175          21407     3      8.97
si535          48450     1     71.28
st70             675     1      0.20
swiss42         1273     1      0.06
ts225         126643     1     21.25
tsp225          3916     1     10.14
u1060         224094    13    507.44
u1432
u159           42080     1      0.41
u1817
u2152
u2319
u574           36905     1     32.84
u724           41910    19    238.42
ulysses16       6859     1      0.19
ulysses22       7013     1      0.47
usa13509
vm1084        239297     9    543.38
vm1748