Re: [Help-glpk] Modified-TSP Problem

[Andrew Makhorin]

> As an introduction to methods for solving linear programming problems
> for operations research I have been required in my course to test out
> various solvers. I have used various solvers on the NEOS server which
> worked well, CPLEX and GLPK.
> 
> I am battling with the GLPK to obtain an answer in a reasonable amount
> of time. The solver can literally go on for over a day. The problem is
> attached.
> 
> What are the optimal cutting techniques to speed up the optimization?
> 
> Below is what I have tried so far, and it seemed to never end:
> 
> GLPSOL: GLPK LP/MIP Solver, v4.43
> Parameter(s) specified in the command line:
>  -m Normal.txt --pcost --gomory -o PcostGomory.txt
> Reading model section from Normal.txt...
> Reading data section from Normal.txt...
> 3638 lines were read
> Generating total...
> Generating leave...
> Generating enter...
> Generating bigcity...
> Generating cap...
> Generating node...
> Model has been successfully generated
> GLPK Integer Optimizer, v4.43
> 3722 rows, 7080 columns, 24785 non-zeros
> 3540 integer variables, all of which are binary
> Preprocessing...
> 3721 rows, 7080 columns, 21245 non-zeros
> 3540 integer variables, all of which are binary
> Scaling...
>  A: min|aij| =  1.000e+00  max|aij| =  5.900e+01  ratio =  5.900e+01
> GM: min|aij| =  9.686e-01  max|aij| =  1.032e+00  ratio =  1.066e+00
> EQ: min|aij| =  9.383e-01  max|aij| =  1.000e+00  ratio =  1.066e+00
> 2N: min|aij| =  9.219e-01  max|aij| =  1.000e+00  ratio =  1.085e+00
> Constructing initial basis...
> Size of triangular part = 3719
> Solving LP relaxation...
> GLPK Simplex Optimizer, v4.43
> 3721 rows, 7080 columns, 21245 non-zeros
>       0: obj =   4.403600000e+04  infeas =  2.178e+03 (2)
> *   476: obj =   3.303622034e+04  infeas =  5.138e-15 (2)
> *   500: obj =   2.571249153e+04  infeas =  4.862e-15 (2)
> *  1000: obj =   1.036538983e+04  infeas =  4.169e-15 (2)
> *  1500: obj =   9.836271186e+03  infeas =  2.759e-15 (2)
> *  2000: obj =   8.280951036e+03  infeas =  2.863e-14 (2)
> *  2500: obj =   6.687677966e+03  infeas =  1.049e-14 (2)
> *  3000: obj =   5.834347458e+03  infeas =  1.996e-15 (2)
> *  3500: obj =   5.352648305e+03  infeas =  1.214e-14 (2)
> *  4000: obj =   5.120169492e+03  infeas =  7.071e-14 (2)
> *  4500: obj =   4.942915254e+03  infeas =  8.447e-15 (2)
> *  4662: obj =   4.840033898e+03  infeas =  1.360e-15 (2)
> OPTIMAL SOLUTION FOUND
> Integer optimization begins...
> Gomory's cuts enabled
> +  4662: mip =     not found yet >=              -inf        (1; 0)
> +  9276: mip =     not found yet >=   5.084000000e+03        (1; 0)
> + 11756: mip =     not found yet >=   5.090000000e+03        (1; 0)
> | 16500: obj =   5.110304039e+03  infeas =  2.883e-11 (2)
> | 17000: obj =   5.111620798e+03  infeas =  4.244e-12 (2)
> | 17154: obj =   5.111627679e+03  infeas =  9.756e-13 (2)
> Cuts on level 0: gmi = 17;
> Pseudocosts initialized for 48 of 108 variables
> Pseudocosts initialized for 97 of 108 variables
> + 17154: mip =     not found yet >=   5.112000000e+03        (2; 0)
> + 18997: mip =     not found yet >=   5.112000000e+03        (3; 0)
> + 23108: mip =     not found yet >=   5.112000000e+03        (5; 0)
> Time used: 62.9 secs.  Memory used: 15.5 Mb.
> + 24774: mip =     not found yet >=   5.112000000e+03        (6; 0)
> + 28332: mip =     not found yet >=   5.112000000e+03        (8; 0)
> + 31645: mip =     not found yet >=   5.112000000e+03        (11; 0)
> + 33858: mip =     not found yet >=   5.112000000e+03        (13; 0)
> + 36666: mip =     not found yet >=   5.112000000e+03        (13; 1)
> + 41943: mip =     not found yet >=   5.118000000e+03        (15; 1)
> + 47818: mip =     not found yet >=   5.118000000e+03        (17; 1)
> Time used: 125.9 secs.  Memory used: 15.6 Mb.
> + 51739: mip =     not found yet >=   5.118000000e+03        (20; 1)
> + 55125: mip =     not found yet >=   5.118000000e+03        (22; 1)
> + 58700: mip =     not found yet >=   5.118000000e+03        (24; 1)
> + 61927: mip =     not found yet >=   5.118000000e+03        (26; 1)
> + 64023: mip =     not found yet >=   5.118000000e+03        (27; 1)
> 

The tsp.mod model included in the glpk distribution is just an example,
and the mip formulation used there is not suitable for instances having
more than 20-25 cities. Besides, the tsp problem is one of hardest
combinatorial optimization problems, so large instances of this problem
(like yours) are hard for the glpk mip solver and cannot be solved for a
reasonable time. 

If you need to solve large tsp instances, you may use Concorde, 
a famous state-of-the-art tsp solver. For more details please see
glpk/examples/cplex/README and glpk/examples/cplex/concorde.txt.


Andrew Makhorin