help-glpk
[Top][All Lists]

## Re: [Help-glpk] reincarnation of tspsol

 From: Andrew Makhorin Subject: Re: [Help-glpk] reincarnation of tspsol Date: Wed, 14 Oct 2015 22:10:18 +0300

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

>  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
NAME: lin318
TYPE: TSP
COMMENT: 318-city problem (Lin/Kernighan)
DIMENSION: 318
EDGE_WEIGHT_TYPE: EUC_2D
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
[...]
+ 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'...

```