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
_______________________________________________
Help-glpk mailing list
Help-glpk@gnu.org
http://lists.gnu.org/mailman/listinfo/help-glpk
