Re: [Help-glpk] reincarnation of tspsol

[Andrew Makhorin]

> Probably n should be limited, say, by 1000. Tspsol doesn't use column
> generation, so the problem object includes *all* (n**2/2-n)

Must read ((n**2)-n)/2.

>  binary
> variables; e.g. for n = 1000 it is about 500,000 variables.
> 

I think n = 500 is a practical limit for tspsol. Below here is the
solver output for n = 318 on Intel Celeron 2.4 GHz:

TSP Solver for GLPK 4.56
Reading TSP data from 'tsplib/lin318.tsp'...
NAME: lin318
TYPE: TSP
COMMENT: 318-city problem (Lin/Kernighan)
DIMENSION: 318
EDGE_WEIGHT_TYPE: EUC_2D
325 lines were read
Solving initial LP relaxation...
GLPK Simplex Optimizer, v4.56
318 rows, 50403 columns, 100806 non-zeros
      0: obj =   0.000000000e+00 inf =   6.360e+02 (318)
    318: obj =   1.240830000e+05 inf =   0.000e+00 (0)
*   500: obj =   8.225700000e+04 inf =   0.000e+00 (1357)
*  1000: obj =   4.632700000e+04 inf =   0.000e+00 (595) 3
*  1355: obj =   3.896350000e+04 inf =   0.000e+00 (0) 2
OPTIMAL LP SOLUTION FOUND
GLPK Integer Optimizer, v4.56
318 rows, 50403 columns, 100806 non-zeros
50403 integer variables, all of which are binary
Integer optimization begins...
Gomory's cuts enabled
+  1355: mip =     not found yet >=              -inf        (1; 0)
+  1617: mip =     not found yet >=   3.942500000e+04        (1; 0)
[...]
+ 25866: mip =   4.202900000e+04 >=   4.202500000e+04 < 0.1% (3; 1504)
+ 25885: mip =   4.202900000e+04 >=     tree is empty   0.0% (0; 1527)
INTEGER OPTIMAL SOLUTION FOUND
Time used:   4972.3 secs
Memory used: 286.4 Mb (300261716 bytes)
Writing TSP solution to 'lin318.sol'...