[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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)
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'...
Re: [Help-glpk] reincarnation of tspsol, Heinrich Schuchardt, 2015/10/20