> 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 _______________________________________________ Help-glpk mailing list [email protected] https://lists.gnu.org/mailman/listinfo/help-glpk
