Re: TIPS FOR DEALING WITH LARGE PROBLEMS.
"J. Friedman" <[email protected]>
| Newsgroups | gmane.comp.gnu.glpk |
|---|---|
| Message-ID | <[email protected]> |
The advantage of using Python to model your MIPs is that you can change the solver from GLPK, to SCIP, to CBC, or Gurobi if the other’s can’t solve it.
For my students I recorded a screen-cast that explains how to use python to model a Gurobi MIP to solve a scheduling problem: https://www.youtube.com/watch?v=hcbfQORsClY&t=1261s <https://www.youtube.com/watch?v=hcbfQORsClY&t=1261s>
But it will be useful to you no matter which solver you choose.
If you want to stay with GLPK try http://pymprog.sourceforge.net/advanced.html#the-traveling-sales-man-tsp <http://pymprog.sourceforge.net/advanced.html#the-traveling-sales-man-tsp>
The Python Math Prog library is pretty neat.
I tried to solve a timetabling program with a 0-1 integer program and I found it is easy to program, but very hard to solve. I started with MathProg and learned how modeling software works. But very soon, I couldn’t solve it with GLPK once the complexity increased. I got a little farther with SCIP and CBC but they couldn’t solve it either. I had no choice, and being an academic user, I switched to Gurobi. Though when I write up my paper, I would have much preferred to use only an open source solver. Hopefully in the next decade, open source solvers will catch up.
I did some experiments. I took a baby version of the timetabling program I am solving, and made a baby version of that (baby**2). I attached the MPS file (zipped).
With a 1 thread,
After 1448 seconds, GLPK: No INTEGER solution found yet (see below for the logs)
After 1189 second, SCIP: No INTEGER solution found yet (see below for the logs)
After 1241 seconds, CBC found the best solution, and proved it was optimal. It found a solution with big gap after 82 seconds
After 8 seconds, Gurobi found the best solution, but took 70 seconds to prove it was optimal.
With 8 threads, Gurobi proved optimality in 50 seconds.
(The above on a MacBook Pro laptop).
With 16 threads (and on one of the new Xeon Scalable Gold’s) Gurobi proved optimality in 10 seconds.
snapdragon:v2june17 joshua$ glpsol 0.mps
GLPSOL: GLPK LP/MIP Solver, v4.65
Parameter(s) specified in the command line:
0.mps
Reading problem data from '0.mps'...
Problem: TIP
Objective: OBJ
13409 rows, 10198 columns, 60262 non-zeros
10198 integer variables, all of which are binary
95233 records were read
One free row was removed
GLPK Integer Optimizer, v4.65
13408 rows, 10198 columns, 59307 non-zeros
10198 integer variables, all of which are binary
Preprocessing...
787 hidden packing inequaliti(es) were detected
1746 hidden covering inequaliti(es) were detected
25 constraint coefficient(s) were reduced
11187 rows, 7702 columns, 52768 non-zeros
7702 integer variables, all of which are binary
Scaling...
A: min|aij| = 1.000e+00 max|aij| = 1.500e+01 ratio = 1.500e+01
GM: min|aij| = 4.891e-01 max|aij| = 2.044e+00 ratio = 4.180e+00
EQ: min|aij| = 2.472e-01 max|aij| = 1.000e+00 ratio = 4.045e+00
2N: min|aij| = 2.500e-01 max|aij| = 1.500e+00 ratio = 6.000e+00
Constructing initial basis...
Size of triangular part is 10663
Solving LP relaxation...
GLPK Simplex Optimizer, v4.65
11187 rows, 7702 columns, 52768 non-zeros
0: obj = -7.957400000e+05 inf = 9.420e+02 (833)
1958: obj = 4.714783073e+06 inf = 2.674e-14 (0) 16
Perturbing LP to avoid stalling [4839]...
Removing LP perturbation [6333]...
* 6333: obj = -1.013100000e+06 inf = 5.736e-13 (0) 40
OPTIMAL LP SOLUTION FOUND
Integer optimization begins...
Long-step dual simplex will be used
+ 6333: mip = not found yet >= -inf (1; 0)
+ 7615: mip = not found yet >= -1.011340000e+06 (18; 0)
+ 12582: mip = not found yet >= -1.011340000e+06 (25; 0)
+ 14868: mip = not found yet >= -1.011340000e+06 (36; 0)
+ 17001: mip = not found yet >= -1.011340000e+06 (44; 0)
+ 20641: mip = not found yet >= -1.011340000e+06 (50; 0)
+ 21551: mip = not found yet >= -1.011340000e+06 (58; 0)
+ 24696: mip = not found yet >= -1.011340000e+06 (66; 0)
+ 26572: mip = not found yet >= -1.011340000e+06 (76; 0)
+ 29446: mip = not found yet >= -1.011340000e+06 (84; 2)
+ 31774: mip = not found yet >= -1.011340000e+06 (98; 2)
+ 33783: mip = not found yet >= -1.011340000e+06 (108; 2)
Time used: 60.4 secs. Memory used: 18.3 Mb.
+ 35334: mip = not found yet >= -1.011340000e+06 (116; 2)
+ 37583: mip = not found yet >= -1.011340000e+06 (124; 2)
+ 40981: mip = not found yet >= -1.011340000e+06 (138; 3)
+ 46813: mip = not found yet >= -1.011340000e+06 (143; 3)
+ 48535: mip = not found yet >= -1.011340000e+06 (150; 3)
+ 51722: mip = not found yet >= -1.011340000e+06 (158; 4)
+ 54544: mip = not found yet >= -1.011340000e+06 (173; 4)
+ 57474: mip = not found yet >= -1.011340000e+06 (188; 4)
+ 62011: mip = not found yet >= -1.011340000e+06 (198; 5)
+ 65043: mip = not found yet >= -1.011340000e+06 (206; 6)
+ 68414: mip = not found yet >= -1.011340000e+06 (218; 6)
Time used: 120.6 secs. Memory used: 19.1 Mb.
+ 72139: mip = not found yet >= -1.011340000e+06 (230; 7)
+ 74665: mip = not found yet >= -1.011340000e+06 (239; 7)
+ 76708: mip = not found yet >= -1.011340000e+06 (250; 7)
+ 79043: mip = not found yet >= -1.011340000e+06 (262; 7)
+ 80289: mip = not found yet >= -1.011340000e+06 (276; 7)
+ 85136: mip = not found yet >= -1.011340000e+06 (287; 7)
+ 89324: mip = not found yet >= -1.011340000e+06 (296; 8)
+ 93637: mip = not found yet >= -1.011340000e+06 (303; 8)
+ 96785: mip = not found yet >= -1.011340000e+06 (312; 8)
+101469: mip = not found yet >= -1.011340000e+06 (321; 10)
Time used: 180.6 secs. Memory used: 20.0 Mb.
+103486: mip = not found yet >= -1.011340000e+06 (333; 10)
+107391: mip = not found yet >= -1.011340000e+06 (343; 10)
+113023: mip = not found yet >= -1.011340000e+06 (350; 10)
+115447: mip = not found yet >= -1.011340000e+06 (359; 10)
+117312: mip = not found yet >= -1.011340000e+06 (370; 10)
+120760: mip = not found yet >= -1.011340000e+06 (377; 11)
+123481: mip = not found yet >= -1.011340000e+06 (388; 11)
+126727: mip = not found yet >= -1.011340000e+06 (396; 12)
+129440: mip = not found yet >= -1.011340000e+06 (404; 12)
+136876: mip = not found yet >= -1.011340000e+06 (411; 13)
+138792: mip = not found yet >= -1.011340000e+06 (424; 13)
Time used: 240.9 secs. Memory used: 20.9 Mb.
+141943: mip = not found yet >= -1.011340000e+06 (437; 13)
+144797: mip = not found yet >= -1.011340000e+06 (447; 13)
+146862: mip = not found yet >= -1.011340000e+06 (458; 14)
+149127: mip = not found yet >= -1.011340000e+06 (471; 14)
+150279: mip = not found yet >= -1.011340000e+06 (482; 15)
+152112: mip = not found yet >= -1.011340000e+06 (492; 15)
+156302: mip = not found yet >= -1.011340000e+06 (494; 15)
+160338: mip = not found yet >= -1.011340000e+06 (501; 15)
+162461: mip = not found yet >= -1.011340000e+06 (509; 15)
+163722: mip = not found yet >= -1.011340000e+06 (518; 15)
+166498: mip = not found yet >= -1.011340000e+06 (528; 15)
Time used: 301.5 secs. Memory used: 21.6 Mb.
+170633: mip = not found yet >= -1.011340000e+06 (532; 16)
+172283: mip = not found yet >= -1.011340000e+06 (542; 16)
+175249: mip = not found yet >= -1.011340000e+06 (546; 16)
+178070: mip = not found yet >= -1.011340000e+06 (553; 16)
+180555: mip = not found yet >= -1.011340000e+06 (562; 16)
+182675: mip = not found yet >= -1.011340000e+06 (569; 16)
+185623: mip = not found yet >= -1.011340000e+06 (579; 16)
+189021: mip = not found yet >= -1.011340000e+06 (589; 16)
+191444: mip = not found yet >= -1.011340000e+06 (598; 17)
+193255: mip = not found yet >= -1.011340000e+06 (605; 17)
+195261: mip = not found yet >= -1.011340000e+06 (615; 17)
Time used: 361.7 secs. Memory used: 22.2 Mb.
+196250: mip = not found yet >= -1.011340000e+06 (625; 17)
+198880: mip = not found yet >= -1.011340000e+06 (636; 17)
+200871: mip = not found yet >= -1.011340000e+06 (650; 17)
+204995: mip = not found yet >= -1.011340000e+06 (660; 17)
+208761: mip = not found yet >= -1.011340000e+06 (668; 18)
+211464: mip = not found yet >= -1.011340000e+06 (682; 18)
+213872: mip = not found yet >= -1.011340000e+06 (692; 19)
+215311: mip = not found yet >= -1.011340000e+06 (701; 19)
+216007: mip = not found yet >= -1.011340000e+06 (707; 19)
+220366: mip = not found yet >= -1.011340000e+06 (711; 19)
+222816: mip = not found yet >= -1.011340000e+06 (717; 20)
+226132: mip = not found yet >= -1.011340000e+06 (722; 20)
Time used: 422.1 secs. Memory used: 23.0 Mb.
+226959: mip = not found yet >= -1.011340000e+06 (731; 20)
+229329: mip = not found yet >= -1.011340000e+06 (739; 20)
+231348: mip = not found yet >= -1.011340000e+06 (745; 20)
+233410: mip = not found yet >= -1.011340000e+06 (753; 20)
+236599: mip = not found yet >= -1.011340000e+06 (756; 21)
+241058: mip = not found yet >= -1.011340000e+06 (759; 21)
+244228: mip = not found yet >= -1.011340000e+06 (767; 21)
+247033: mip = not found yet >= -1.011340000e+06 (773; 21)
+248366: mip = not found yet >= -1.011340000e+06 (781; 21)
+249473: mip = not found yet >= -1.011340000e+06 (789; 21)
Time used: 482.5 secs. Memory used: 23.4 Mb.
+250851: mip = not found yet >= -1.011340000e+06 (798; 22)
+252561: mip = not found yet >= -1.011340000e+06 (808; 22)
+255921: mip = not found yet >= -1.011340000e+06 (817; 22)
+258784: mip = not found yet >= -1.011340000e+06 (828; 22)
+261685: mip = not found yet >= -1.011340000e+06 (838; 23)
+265102: mip = not found yet >= -1.011340000e+06 (845; 23)
+267795: mip = not found yet >= -1.011340000e+06 (855; 24)
+270173: mip = not found yet >= -1.011340000e+06 (867; 24)
+272617: mip = not found yet >= -1.011340000e+06 (874; 24)
+275931: mip = not found yet >= -1.011340000e+06 (880; 24)
+277524: mip = not found yet >= -1.011340000e+06 (892; 24)
Time used: 542.7 secs. Memory used: 24.0 Mb.
+280548: mip = not found yet >= -1.011340000e+06 (902; 25)
+283577: mip = not found yet >= -1.011340000e+06 (908; 25)
+285071: mip = not found yet >= -1.011340000e+06 (917; 25)
+286943: mip = not found yet >= -1.011340000e+06 (928; 25)
+289274: mip = not found yet >= -1.011340000e+06 (938; 25)
+291997: mip = not found yet >= -1.011340000e+06 (947; 25)
+295183: mip = not found yet >= -1.011340000e+06 (958; 26)
+297054: mip = not found yet >= -1.011340000e+06 (971; 26)
+298915: mip = not found yet >= -1.011340000e+06 (981; 26)
+300257: mip = not found yet >= -1.011340000e+06 (991; 26)
+302192: mip = not found yet >= -1.011340000e+06 (1001; 27)
Time used: 602.8 secs. Memory used: 24.8 Mb.
+305189: mip = not found yet >= -1.011340000e+06 (1007; 27)
+306238: mip = not found yet >= -1.011340000e+06 (1014; 27)
+308479: mip = not found yet >= -1.011340000e+06 (1025; 27)
+312034: mip = not found yet >= -1.011340000e+06 (1036; 27)
+315755: mip = not found yet >= -1.011340000e+06 (1050; 27)
+319768: mip = not found yet >= -1.011340000e+06 (1058; 28)
+322213: mip = not found yet >= -1.011340000e+06 (1066; 28)
+324785: mip = not found yet >= -1.011340000e+06 (1072; 29)
+329785: mip = not found yet >= -1.011340000e+06 (1080; 29)
+331373: mip = not found yet >= -1.011340000e+06 (1089; 30)
+332996: mip = not found yet >= -1.011340000e+06 (1096; 30)
Time used: 662.9 secs. Memory used: 25.5 Mb.
+335217: mip = not found yet >= -1.011340000e+06 (1103; 30)
+337643: mip = not found yet >= -1.011340000e+06 (1109; 30)
+339875: mip = not found yet >= -1.011340000e+06 (1119; 30)
+343494: mip = not found yet >= -1.011340000e+06 (1131; 31)
+346227: mip = not found yet >= -1.011340000e+06 (1146; 31)
+348347: mip = not found yet >= -1.011340000e+06 (1153; 31)
+351760: mip = not found yet >= -1.011340000e+06 (1162; 32)
+354902: mip = not found yet >= -1.011340000e+06 (1173; 33)
+357496: mip = not found yet >= -1.011340000e+06 (1184; 33)
+360361: mip = not found yet >= -1.011340000e+06 (1190; 34)
+361360: mip = not found yet >= -1.011340000e+06 (1201; 34)
Time used: 723.0 secs. Memory used: 26.2 Mb.
+364173: mip = not found yet >= -1.011340000e+06 (1209; 34)
+367845: mip = not found yet >= -1.011340000e+06 (1214; 34)
+369116: mip = not found yet >= -1.011340000e+06 (1223; 34)
snapdragon:v2june17 joshua$ scip -f 0.mps
SCIP version 3.2.1 [precision: 8 byte] [memory: block] [mode: optimized] [LP solver: SoPlex 2.2.1] [GitHash: c7c6c02]
Copyright (c) 2002-2016 Konrad-Zuse-Zentrum fuer Informationstechnik Berlin (ZIB)
External codes:
SoPlex 2.2.1 Linear Programming Solver developed at Zuse Institute Berlin (soplex.zib.de) [GitHash: 267a44a]
cppad-20140000.3 Algorithmic Differentiation of C++ algorithms developed by B. Bell (www.coin-or.org/CppAD)
ZLIB 1.2.5 General purpose compression library by J. Gailly and M. Adler (zlib.net)
GMP 6.0.0 GNU Multiple Precision Arithmetic Library developed by T. Granlund (gmplib.org)
ZIMPL 3.3.3 Zuse Institute Mathematical Programming Language developed by T. Koch (zimpl.zib.de)
Ipopt 3.12.4 Interior Point Optimizer developed by A. Waechter et.al. (www.coin-or.org/Ipopt)
user parameter file <scip.set> not found - using default parameters
read problem <0.mps>
============
original problem has 10198 variables (10198 bin, 0 int, 0 impl, 0 cont) and 13408 constraints
solve problem
=============
presolving:
(round 1, fast) 3552 del vars, 3144 del conss, 0 add conss, 557 chg bounds, 81 chg sides, 33 chg coeffs, 0 upgd conss, 0 impls, 4220 clqs
(round 2, fast) 3780 del vars, 3492 del conss, 0 add conss, 712 chg bounds, 81 chg sides, 40 chg coeffs, 0 upgd conss, 0 impls, 4479 clqs
(round 3, exhaustive) 3780 del vars, 4440 del conss, 0 add conss, 712 chg bounds, 121 chg sides, 40 chg coeffs, 0 upgd conss, 0 impls, 4479 clqs
(round 4, exhaustive) 3780 del vars, 4440 del conss, 0 add conss, 712 chg bounds, 121 chg sides, 40 chg coeffs, 8696 upgd conss, 0 impls, 4479 clqs
(round 5, medium) 3942 del vars, 4830 del conss, 721 add conss, 712 chg bounds, 546 chg sides, 1772 chg coeffs, 8696 upgd conss, 0 impls, 5383 clqs
(round 6, fast) 3942 del vars, 4905 del conss, 721 add conss, 712 chg bounds, 546 chg sides, 1772 chg coeffs, 8696 upgd conss, 0 impls, 5394 clqs
(round 7, exhaustive) 3942 del vars, 4913 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1772 chg coeffs, 8696 upgd conss, 0 impls, 5394 clqs
(round 8, exhaustive) 3942 del vars, 4933 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1787 chg coeffs, 8696 upgd conss, 0 impls, 5395 clqs
(round 9, fast) 3962 del vars, 4933 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1787 chg coeffs, 8696 upgd conss, 0 impls, 5395 clqs
(round 10, exhaustive) 3962 del vars, 4933 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1787 chg coeffs, 8800 upgd conss, 0 impls, 5465 clqs
(round 11, exhaustive) 3962 del vars, 4953 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1787 chg coeffs, 8800 upgd conss, 0 impls, 5465 clqs
(round 12, exhaustive) 3962 del vars, 5191 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1820 chg coeffs, 8800 upgd conss, 0 impls, 5465 clqs
(round 13, exhaustive) 3988 del vars, 5191 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1820 chg coeffs, 8800 upgd conss, 0 impls, 8277 clqs
(round 14, fast) 3988 del vars, 5277 del conss, 725 add conss, 712 chg bounds, 546 chg sides, 1823 chg coeffs, 8800 upgd conss, 0 impls, 8277 clqs
(round 15, exhaustive) 4015 del vars, 5277 del conss, 725 add conss, 712 chg bounds, 552 chg sides, 1846 chg coeffs, 8800 upgd conss, 0 impls, 14329 clqs
(round 16, fast) 4015 del vars, 5310 del conss, 725 add conss, 712 chg bounds, 552 chg sides, 1846 chg coeffs, 8800 upgd conss, 0 impls, 14334 clqs
(round 17, exhaustive) 4040 del vars, 5310 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16696 clqs
(round 18, fast) 4040 del vars, 5337 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16696 clqs
(round 19, exhaustive) 4040 del vars, 5413 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16696 clqs
(round 20, exhaustive) 4040 del vars, 5422 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16696 clqs
(round 21, exhaustive) 4065 del vars, 5423 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16840 clqs
(round 22, fast) 4065 del vars, 5450 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 16840 clqs
(0.8s) probing: 671/6257 (10.7%) - 18 fixings, 97 aggregations, 14207 implications, 0 bound changes
(0.8s) probing aborted: 50/50 successive totally useless probings
(round 23, exhaustive) 4078 del vars, 5451 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 19116 clqs
(round 24, fast) 4078 del vars, 5464 del conss, 725 add conss, 712 chg bounds, 554 chg sides, 1852 chg coeffs, 8800 upgd conss, 0 impls, 19117 clqs
(0.8s) probing: 676/6257 (10.8%) - 18 fixings, 97 aggregations, 14207 implications, 0 bound changes
(0.8s) probing aborted: 50/50 successive totally useless probings
presolving (25 rounds: 25 fast, 16 medium, 15 exhaustive):
4078 deleted vars, 5464 deleted constraints, 725 added constraints, 712 tightened bounds, 0 added holes, 554 changed sides, 1852 changed coefficients
0 implications, 19117 cliques
presolved problem has 6142 variables (6142 bin, 0 int, 0 impl, 0 cont) and 8669 constraints
137 constraints of type <knapsack>
4063 constraints of type <setppc>
60 constraints of type <xor>
165 constraints of type <linear>
4244 constraints of type <logicor>
transformed objective value is always integral (scale: 10)
Presolving Time: 0.77
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
1.0s| 1 | 0 | 1551 | - | 48M| 0 | 114 |6142 |8671 |6142 |8669 | 0 | 2 | 0 | 2.970000e+03 | -- | Inf
7.2s| 1 | 0 | 24062 | - | 51M| 0 | 454 |6142 |8671 |6142 |8747 | 78 | 3 | 0 | 3.547500e+03 | -- | Inf
8.5s| 1 | 0 | 25343 | - | 58M| 0 | 415 |6142 |8673 |6142 |8793 | 124 | 5 | 0 | 3.707262e+03 | -- | Inf
9.4s| 1 | 0 | 27588 | - | 63M| 0 | 602 |6142 |8674 |6142 |8841 | 172 | 6 | 0 | 3.807202e+03 | -- | Inf
10.7s| 1 | 0 | 28477 | - | 70M| 0 | 679 |6142 |8675 |6142 |8887 | 218 | 7 | 0 | 3.857415e+03 | -- | Inf
11.6s| 1 | 0 | 28820 | - | 71M| 0 | 730 |6142 |8676 |6142 |8905 | 236 | 8 | 0 | 3.868146e+03 | -- | Inf
13.1s| 1 | 0 | 29185 | - | 81M| 0 | 704 |6142 |8677 |6142 |8952 | 283 | 9 | 0 | 3.873294e+03 | -- | Inf
14.1s| 1 | 0 | 29664 | - | 81M| 0 | 692 |6142 |8679 |6142 |8963 | 294 | 11 | 0 | 3.910416e+03 | -- | Inf
15.1s| 1 | 0 | 30230 | - | 82M| 0 | 666 |6142 |8680 |6142 |8971 | 302 | 12 | 0 | 3.923831e+03 | -- | Inf
16.1s| 1 | 0 | 30908 | - | 82M| 0 | 653 |6142 |8681 |6142 |8978 | 309 | 13 | 0 | 3.927076e+03 | -- | Inf
17.0s| 1 | 0 | 31178 | - | 82M| 0 | 691 |6142 |8682 |6142 |8987 | 318 | 14 | 0 | 3.927448e+03 | -- | Inf
17.5s| 1 | 0 | 31197 | - | 82M| 0 | 692 |6142 |8682 |6142 |8993 | 324 | 14 | 0 | 3.927448e+03 | -- | Inf
18.0s| 1 | 0 | 31224 | - | 82M| 0 | 697 |6142 |8683 |6142 |9001 | 332 | 15 | 0 | 3.927448e+03 | -- | Inf
24.5s| 1 | 2 | 31224 | - | 82M| 0 | 697 |6142 |8683 |6142 |9001 | 332 | 15 | 32 | 3.952667e+03 | -- | Inf
98.3s| 100 | 93 |158374 |1284.3 | 84M| 15 | 429 |6142 |8742 |6142 |8745 | 332 | 80 | 303 | 3.952667e+03 | -- | Inf
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
145s| 200 | 173 |291001 |1305.4 | 86M| 29 | 479 |6142 |8797 |6142 |8745 | 332 | 144 | 386 | 3.952667e+03 | -- | Inf
174s| 300 | 267 |361209 |1103.6 | 87M| 29 | 436 |6142 |8825 |6142 |8745 | 332 | 173 | 436 | 4.153319e+03 | -- | Inf
210s| 400 | 355 |461348 |1078.0 | 87M| 29 | 409 |6142 |8881 |6142 |8745 | 332 | 231 | 487 | 4.153319e+03 | -- | Inf
243s| 500 | 431 |546889 |1033.4 | 88M| 29 | 532 |6142 |8919 |6142 |8745 | 332 | 271 | 550 | 4.153319e+03 | -- | Inf
281s| 600 | 529 |650702 |1034.2 | 89M| 31 | 168 |6142 |8999 |6142 |8745 | 332 | 364 | 627 | 4.153319e+03 | -- | Inf
326s| 700 | 615 |753692 |1033.6 | 90M| 31 | 494 |6142 |9027 |6142 |8745 | 332 | 410 | 708 | 4.153319e+03 | -- | Inf
380s| 800 | 705 |861468 |1039.1 | 90M| 31 | 364 |6142 |9087 |6142 |8745 | 332 | 481 | 765 | 4.153319e+03 | -- | Inf
422s| 900 | 801 |973081 |1047.7 | 91M| 33 | 603 |6142 |9122 |6142 |8745 | 332 | 528 | 869 | 4.153319e+03 | -- | Inf
473s| 1000 | 879 | 1091k|1061.2 | 92M| 33 | 250 |6142 |9173 |6142 |8745 | 332 | 587 | 968 | 4.153319e+03 | -- | Inf
528s| 1100 | 954 | 1203k|1066.8 | 92M| 48 | 451 |6142 |9257 |6142 |8745 | 332 | 679 |1083 | 4.153319e+03 | -- | Inf
578s| 1200 | 1036 | 1321k|1076.1 | 93M| 57 | - |6142 |9297 |6142 |8745 | 332 | 729 |1169 | 4.153319e+03 | -- | Inf
631s| 1300 | 1109 | 1433k|1079.5 | 94M| 57 | - |6142 |9343 | 0 | 0 | 332 | 788 |1261 | 4.153319e+03 | -- | Inf
679s| 1400 | 1178 | 1531k|1072.1 | 94M| 57 | 345 |6142 |9419 |6142 |8745 | 332 | 901 |1343 | 4.153319e+03 | -- | Inf
731s| 1500 | 1251 | 1630k|1067.0 | 95M| 57 | 613 |6142 |9455 |6142 |8745 | 332 | 972 |1438 | 4.153319e+03 | -- | Inf
778s| 1600 | 1316 | 1727k|1061.0 | 95M| 57 | 479 |6142 |9527 |6142 |8745 | 332 |1078 |1533 | 4.153319e+03 | -- | Inf
time | node | left |LP iter|LP it/n| mem |mdpt |frac |vars |cons |cols |rows |cuts |confs|strbr| dualbound | primalbound | gap
845s| 1700 | 1385 | 1850k|1071.0 | 96M| 57 | 381 |6142 |9601 |6142 |8745 | 332 |1173 |1664 | 4.153319e+03 | -- | Inf
886s| 1800 | 1457 | 1922k|1051.3 | 97M| 57 | 60 |6142 |9636 |6142 |8745 | 332 |1230 |1723 | 4.153319e+03 | -- | Inf
932s| 1900 | 1537 | 2023k|1048.9 | 97M| 61 | 405 |6142 |9671 |6142 |8745 | 332 |1328 |1816 | 4.153319e+03 | -- | Inf
977s| 2000 | 1602 | 2118k|1044.1 | 98M| 71 | - |6142 |9860 | 0 | 0 | 332 |1615 |1927 | 4.153319e+03 | -- | Inf
1036s| 2100 | 1674 | 2229k|1047.3 | 99M| 71 | 326 |6142 |9867 |6142 |8745 | 332 |1729 |2022 | 4.153319e+03 | -- | Inf
1081s| 2200 | 1724 | 2319k|1040.7 | 99M| 71 | 309 |6142 |9908 |6142 |8745 | 332 |1837 |2104 | 4.153319e+03 | -- | Inf
1146s| 2300 | 1788 | 2443k|1049.2 | 100M| 71 | 464 |6142 |9928 |6142 |8745 | 332 |1924 |2189 | 4.153319e+03 | -- | Inf
1189s| 2400 | 1864 | 2526k|1040.2 | 101M| 71 | 613 |6142 |9927 |6142 |8745 | 332 |1991 |2260 | 4.153319e+03 | -- | Inf
^Cpressed CTRL-C 1 times (5 times for forcing termination)
SCIP Status : solving was interrupted [user interrupt]
Solving Time (sec) : 1201.71
Solving Nodes : 2422
Primal Bound : +1.00000000000000e+20 (0 solutions)
Dual Bound : +4.15331912196794e+03
Gap : infinite
primal solution (original space):
=================================
no solution available
Statistics
==========
SCIP Status : solving was interrupted [user interrupt]
Total Time : 1201.77
solving : 1201.71
presolving : 0.77 (included in solving)
reading : 0.06
copying : 0.03 (1 #copies) (minimal 0.03, maximal 0.03, average 0.03)
Original Problem :
Problem name : TIP
Variables : 10198 (10198 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 13408 initial, 13408 maximal
Objective sense : minimize
Presolved Problem :
Problem name : t_TIP
Variables : 6142 (6142 binary, 0 integer, 0 implicit integer, 0 continuous)
Constraints : 8669 initial, 9940 maximal
Presolvers : ExecTime SetupTime Calls FixedVars AggrVars ChgTypes ChgBounds AddHoles DelCons AddCons ChgSides ChgCoefs
boundshift : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
components : 0.01 0.00 1 0 0 0 0 0 0 0 0 0
convertinttobin : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
domcol : 0.04 0.00 6 0 0 0 0 0 0 0 0 0
dualagg : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
dualinfer : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
gateextraction : 0.09 0.00 13 0 0 0 0 0 8 4 0 0
implfree : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
implics : 0.00 0.00 16 0 0 0 0 0 0 0 0 0
inttobinary : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
redvub : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
stuffing : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
trivial : 0.02 0.00 25 21 0 0 0 0 0 0 0 0
tworowbnd : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
dualfix : 0.01 0.00 25 2517 0 0 0 0 0 0 0 0
genvbounds : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
probing : 0.27 0.00 6 18 97 0 0 0 0 0 0 0
pseudoobj : 0.00 0.00 0 0 0 0 0 0 0 0 0 0
knapsack : 0.00 0.00 47 0 0 0 0 0 180 721 385 1330
setppc : 0.14 0.00 47 0 162 0 0 0 546 0 48 48
xor : 0.01 0.00 44 0 0 0 0 0 20 0 0 0
linear : 0.07 0.01 35 712 529 0 712 0 4442 0 121 40
logicor : 0.10 0.00 42 1 0 0 0 0 268 0 0 434
root node : - - - 11 - - 11 - - - - -
Constraints : Number MaxNumber #Separate #Propagate #EnfoLP #EnfoPS #Check #ResProp Cutoffs DomReds Cuts Applied Conss Children
integral : 0 0 0 0 2301 0 1673 0 0 1607 0 0 520 4322
knapsack : 137 137 12 29494 0 0 1672 444 2 1763 63 3 0 0
setppc : 4063+ 4275 12 29492 0 0 1559 15570 53 61674 0 0 0 0
xor : 60 60 12 29439 0 0 0 673 101 2017 0 0 0 0
linear : 165 165 12 29338 0 0 0 17574 266 79263 7 1 0 0
logicor : 4244+ 5307 12 15377 0 0 0 9555 121 8711 0 0 0 0
countsols : 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Constraint Timings : TotalTime SetupTime Separate Propagate EnfoLP EnfoPS Check ResProp SB-Prop
integral : 397.81 0.00 0.00 0.00 397.53 0.00 0.28 0.00 0.00
knapsack : 0.28 0.00 0.00 0.11 0.00 0.00 0.07 0.00 0.10
setppc : 0.59 0.00 0.00 0.29 0.00 0.00 0.03 0.06 0.21
xor : 1.62 0.00 0.00 1.61 0.00 0.00 0.00 0.00 0.01
linear : 0.86 0.01 0.14 0.43 0.00 0.00 0.00 0.03 0.25
logicor : 0.39 0.00 0.01 0.22 0.00 0.00 0.00 0.01 0.15
countsols : 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00 0.00
Propagators : #Propagate #ResProp Cutoffs DomReds
dualfix : 1 0 0 0
genvbounds : 0 0 0 0
obbt : 0 0 0 0
probing : 0 0 0 0
pseudoobj : 10782 0 0 0
redcost : 14 0 0 0
rootredcost : 1 0 0 0
vbounds : 29913 0 0 0
Propagator Timings : TotalTime SetupTime Presolve Propagate ResProp SB-Prop
dualfix : 0.01 0.00 0.01 0.00 0.00 0.00
genvbounds : 0.04 0.00 0.00 0.02 0.00 0.02
obbt : 0.00 0.00 0.00 0.00 0.00 0.00
probing : 0.27 0.00 0.27 0.00 0.00 0.00
pseudoobj : 0.06 0.00 0.00 0.05 0.00 0.01
redcost : 0.02 0.00 0.00 0.00 0.00 0.02
rootredcost : 0.01 0.00 0.00 0.00 0.00 0.01
vbounds : 0.27 0.00 0.00 0.24 0.00 0.03
Conflict Analysis : Time Calls Success DomReds Conflicts Literals Reconvs ReconvLits LP Iters
propagation : 0.12 430 423 - 1149 15.0 74 6.3 -
infeasible LP : 0.43 289 289 - 1575 98.3 82 4.4 0
bound exceed. LP : 0.00 0 0 - 0 0.0 0 0.0 0
strong branching : 0.00 0 0 - 0 0.0 0 0.0 0
pseudo solution : 0.00 0 0 - 0 0.0 0 0.0 -
applied globally : 0.02 - - 0 2000 33.9 - - -
applied locally : - - - 0 0 0.0 - - -
Separators : ExecTime SetupTime Calls Cutoffs DomReds Cuts Applied Conss
cut pool : 0.02 11 - - 373 - - (maximal pool size: 1159)
cgmip : 0.00 0.00 0 0 0 0 0 0
clique : 0.35 0.00 12 0 0 56 40 0
closecuts : 0.00 0.00 0 0 0 0 0 0
cmir : 0.14 0.00 10 0 0 30 17 0
disjunctive : 0.00 0.00 0 0 0 0 0 0
eccuts : 0.00 0.00 0 0 0 0 0 0
flowcover : 0.71 0.00 12 0 0 236 141 0
gomory : 3.36 0.00 10 0 0 0 0 0
impliedbounds : 0.02 0.00 12 0 0 91 58 0
intobj : 0.00 0.00 0 0 0 0 0 0
mcf : 0.01 0.00 1 0 0 0 0 0
oddcycle : 0.00 0.00 0 0 0 0 0 0
rapidlearning : 0.00 0.00 0 0 0 0 0 0
strongcg : 4.10 0.00 12 0 0 2557 72 0
zerohalf : 0.00 0.00 0 0 0 0 0 0
Pricers : ExecTime SetupTime Calls Vars
problem variables: 0.00 - 0 0
Branching Rules : ExecTime SetupTime BranchLP BranchExt BranchPS Cutoffs DomReds Cuts Conss Children
allfullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
cloud : 0.00 0.00 0 0 0 0 0 0 0 0
distribution : 0.00 0.00 0 0 0 0 0 0 0 0
fullstrong : 0.00 0.00 0 0 0 0 0 0 0 0
inference : 0.00 0.00 0 0 0 0 0 0 0 0
leastinf : 0.00 0.00 0 0 0 0 0 0 0 0
mostinf : 0.00 0.00 0 0 0 0 0 0 0 0
multaggr : 0.00 0.00 0 0 0 0 0 0 0 0
nodereopt : 0.00 0.00 0 0 0 0 0 0 0 0
pscost : 0.00 0.00 0 0 0 0 0 0 0 0
random : 0.00 0.00 0 0 0 0 0 0 0 0
relpscost : 397.52 0.00 2301 0 0 0 1607 0 467 4322
Primal Heuristics : ExecTime SetupTime Calls Found
LP solutions : 0.00 - - 0
pseudo solutions : 0.00 - - 0
strong branching : 0.02 - - 0
actconsdiving : 0.00 0.00 0 0
bound : 0.00 0.00 0 0
clique : 0.00 0.00 0 0
coefdiving : 4.92 0.00 12 0
crossover : 0.00 0.00 0 0
dins : 0.00 0.00 0 0
distributiondivin: 16.21 0.00 11 0
dualval : 0.00 0.00 0 0
feaspump : 16.70 0.00 6 0
fixandinfer : 0.00 0.00 0 0
fracdiving : 5.81 0.00 11 0
guideddiving : 0.00 0.00 0 0
indicator : 0.01 0.00 0 0
intdiving : 0.00 0.00 0 0
intshifting : 0.00 0.00 0 0
linesearchdiving : 5.04 0.00 11 0
localbranching : 0.00 0.00 0 0
mutation : 0.00 0.00 0 0
nlpdiving : 0.00 0.00 0 0
objpscostdiving : 19.70 0.00 6 0
octane : 0.00 0.00 0 0
ofins : 0.00 0.00 0 0
oneopt : 0.00 0.00 0 0
proximity : 0.00 0.00 0 0
pscostdiving : 14.72 0.00 11 0
randrounding : 0.31 0.00 125 0
rens : 0.10 0.00 1 0
reoptsols : 0.00 0.00 0 0
rins : 0.01 0.00 0 0
rootsoldiving : 16.50 0.00 6 0
rounding : 0.43 0.00 623 0
shiftandpropagate: 0.05 0.00 1 0
shifting : 1.98 0.00 175 0
simplerounding : 0.00 0.00 2311 0
subnlp : 0.00 0.00 0 0
trivial : 0.01 0.00 2 0
trivialnegation : 0.00 0.00 0 0
trysol : 0.00 0.00 0 0
twoopt : 0.00 0.00 0 0
undercover : 0.00 0.00 0 0
vbounds : 0.00 0.00 0 0
veclendiving : 4.55 0.00 11 0
zeroobj : 0.00 0.00 0 0
zirounding : 0.18 0.00 1000 0
other solutions : - - - 0
Diving Statistics : Calls Nodes LP Iters Backtracks MinDepth MaxDepth AvgDepth NLeafSols MinSolDpt MaxSolDpt AvgSolDpt
actconsdiving : 0 - - - - - - - - - -
coefdiving : 12 261 20856 57 30 78 46.5 - - - -
distributiondivin: 11 583 55205 20 40 156 76.5 - - - -
fracdiving : 11 696 23259 42 38 179 88.7 - - - -
guideddiving : 0 - - - - - - - - - -
linesearchdiving : 11 1141 18600 25 51 270 131.6 - - - -
pscostdiving : 11 1391 62695 14 50 321 152.9 - - - -
veclendiving : 11 371 16816 87 35 99 55.8 - - - -
LP : Time Calls Iterations Iter/call Iter/sec Time-0-It Calls-0-It
primal LP : 0.00 1 0 0.00 - 0.00 1
dual LP : 680.27 2440 2161467 897.62 3177.37 0.04 32
lex dual LP : 0.00 0 0 0.00 -
barrier LP : 0.00 0 0 0.00 - 0.00 0
diving/probing LP: 103.59 370 395225 1068.18 3815.28
strong branching : 390.45 2282 1221083 535.09 3127.37
(at root node) : - 32 24220 756.88 -
conflict analysis: 0.00 0 0 0.00 -
B&B Tree :
number of runs : 1
nodes : 2422 (2161 internal, 261 leaves)
nodes (total) : 2422 (2161 internal, 261 leaves)
nodes left : 1886
max depth : 71
max depth (total): 71
backtracks : 117 (4.8%)
delayed cutoffs : 15
repropagations : 1661 (4583 domain reductions, 13 cutoffs)
avg switch length: 3.65
switching time : 0.73
Root Node :
First LP value : +2.97000000000000e+03
First LP Iters : 1551 (10340.00 Iter/sec)
First LP Time : 0.15
Final Dual Bound : +3.95266666666663e+03
Final Root Iters : 31224
Solution :
Solutions found : 0 (0 improvements)
Primal Bound : -
Dual Bound : +4.15331912196794e+03
Gap : infinite
Avg. Gap : 100.00 % (120171.00 primal-dual integral)
snapdragon:v2june17 joshua$
snapdragon:v2june17 joshua$ cbc 0.mps
Welcome to the CBC MILP Solver
Version: 2.9.8
Build Date: Nov 20 2016
command line - cbc 0.mps (default strategy 1)
At line 1 NAME TIP
At line 2 ROWS
At line 13412 COLUMNS
At line 74818 RHS
At line 85034 BOUNDS
At line 95233 ENDATA
Problem TIP has 13408 rows, 10198 columns and 59307 elements
Coin0008I TIP read with 0 errors
Continuous objective value is 1131.43 - 0.14 seconds
Cgl0003I 22 fixed, 0 tightened bounds, 5633 strengthened rows, 163 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2465 strengthened rows, 2 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2877 strengthened rows, 30 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 2375 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1882 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 1199 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 655 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 423 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 403 strengthened rows, 0 substitutions
Cgl0003I 0 fixed, 0 tightened bounds, 302 strengthened rows, 0 substitutions
Cgl0004I processed model has 7878 rows, 6274 columns (6274 integer (6273 of which binary)) and 57234 elements
Cutoff increment increased from 1e-05 to 0.9999
Cbc0038I Initial state - 258 integers unsatisfied sum - 69.3905
Cbc0038I Pass 1: (14.55 seconds) suminf. 34.48165 (408) obj. 2.12666e+06 iterations 5384
Cbc0038I Pass 2: (15.91 seconds) suminf. 32.22177 (163) obj. 2.04113e+06 iterations 2783
Cbc0038I Pass 3: (16.03 seconds) suminf. 29.09589 (161) obj. 2.05953e+06 iterations 237
Cbc0038I Pass 4: (16.06 seconds) suminf. 28.94167 (160) obj. 2.05942e+06 iterations 57
Cbc0038I Pass 5: (16.28 seconds) suminf. 27.78294 (131) obj. 2.395e+06 iterations 482
Cbc0038I Pass 6: (16.40 seconds) suminf. 26.56029 (127) obj. 2.05329e+06 iterations 262
Cbc0038I Pass 7: (16.48 seconds) suminf. 24.19124 (127) obj. 2.05347e+06 iterations 157
Cbc0038I Pass 8: (16.55 seconds) suminf. 22.22100 (114) obj. 2.05347e+06 iterations 143
Cbc0038I Pass 9: (16.59 seconds) suminf. 21.82815 (115) obj. 2.05347e+06 iterations 90
Cbc0038I Pass 10: (16.62 seconds) suminf. 21.82815 (115) obj. 2.05347e+06 iterations 18
Cbc0038I Pass 11: (16.74 seconds) suminf. 21.63810 (109) obj. 2.06188e+06 iterations 251
Cbc0038I Pass 12: (16.88 seconds) suminf. 21.00672 (109) obj. 2.05347e+06 iterations 273
Cbc0038I Pass 13: (16.90 seconds) suminf. 21.00672 (109) obj. 2.05347e+06 iterations 37
Cbc0038I Pass 14: (16.95 seconds) suminf. 20.97100 (113) obj. 2.05347e+06 iterations 73
Cbc0038I Pass 15: (17.05 seconds) suminf. 21.49524 (106) obj. 2.06188e+06 iterations 179
Cbc0038I Pass 16: (17.80 seconds) suminf. 25.17081 (129) obj. 2.2629e+06 iterations 1439
Cbc0038I Pass 17: (18.53 seconds) suminf. 22.13810 (104) obj. 2.26188e+06 iterations 1381
Cbc0038I Pass 18: (18.71 seconds) suminf. 21.28648 (122) obj. 2.25347e+06 iterations 347
Cbc0038I Pass 19: (18.90 seconds) suminf. 21.42619 (117) obj. 2.26188e+06 iterations 353
Cbc0038I Pass 20: (19.06 seconds) suminf. 21.16148 (119) obj. 2.25351e+06 iterations 307
Cbc0038I Pass 21: (19.25 seconds) suminf. 20.98333 (116) obj. 2.26184e+06 iterations 342
Cbc0038I Pass 22: (19.42 seconds) suminf. 20.82815 (121) obj. 2.25347e+06 iterations 297
Cbc0038I Pass 23: (19.59 seconds) suminf. 21.90833 (116) obj. 2.26194e+06 iterations 305
Cbc0038I Pass 24: (20.33 seconds) suminf. 24.79881 (106) obj. 2.61194e+06 iterations 1319
Cbc0038I Pass 25: (20.83 seconds) suminf. 22.83571 (120) obj. 2.61184e+06 iterations 1056
Cbc0038I Pass 26: (20.90 seconds) suminf. 22.69762 (118) obj. 2.61181e+06 iterations 134
Cbc0038I Pass 27: (21.00 seconds) suminf. 22.47696 (123) obj. 2.61181e+06 iterations 177
Cbc0038I Pass 28: (21.10 seconds) suminf. 22.47696 (123) obj. 2.61181e+06 iterations 162
Cbc0038I Pass 29: (21.17 seconds) suminf. 22.47696 (123) obj. 2.61181e+06 iterations 110
Cbc0038I Pass 30: (21.84 seconds) suminf. 25.47100 (120) obj. 4.89752e+06 iterations 1333
Cbc0038I No solution found this major pass
Cbc0038I Before mini branch and bound, 5616 integers at bound fixed and 0 continuous
Cbc0038I Mini branch and bound did not improve solution (21.85 seconds)
Cbc0038I After 21.85 seconds - Feasibility pump exiting - took 9.49 seconds
Cbc0031I 36 added rows had average density of 257.27778
Cbc0013I At root node, 36 cuts changed objective from 1595 to 3726.485 in 16 passes
Cbc0014I Cut generator 0 (Probing) - 348 row cuts average 2.1 elements, 0 column cuts (0 active) in 0.872 seconds - new frequency is 1
Cbc0014I Cut generator 1 (Gomory) - 306 row cuts average 629.1 elements, 0 column cuts (0 active) in 1.784 seconds - new frequency is 1
Cbc0014I Cut generator 2 (Knapsack) - 220 row cuts average 9.1 elements, 0 column cuts (0 active) in 0.351 seconds - new frequency is 1
Cbc0014I Cut generator 3 (Clique) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.013 seconds - new frequency is -100
Cbc0014I Cut generator 4 (MixedIntegerRounding2) - 10 row cuts average 85.6 elements, 0 column cuts (0 active) in 0.186 seconds - new frequency is -100
Cbc0014I Cut generator 5 (FlowCover) - 0 row cuts average 0.0 elements, 0 column cuts (0 active) in 0.012 seconds - new frequency is -100
Cbc0014I Cut generator 6 (TwoMirCuts) - 340 row cuts average 139.9 elements, 0 column cuts (0 active) in 0.573 seconds - new frequency is 1
Cbc0010I After 0 nodes, 1 on tree, 1e+50 best solution, best possible 3726.485 (32.23 seconds)
Cbc0004I Integer solution of 22000 found after 60846 iterations and 54 nodes (82.25 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 398 rows 191 columns
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 554 rows 303 columns
Cbc0010I After 100 nodes, 47 on tree, 22000 best solution, best possible 3726.485 (145.71 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 409 rows 221 columns
Cbc0010I After 200 nodes, 91 on tree, 22000 best solution, best possible 3726.485 (254.44 seconds)
Cbc0004I Integer solution of 12320 found after 407027 iterations and 248 nodes (296.70 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 464 rows 237 columns
Cbc0010I After 300 nodes, 108 on tree, 12320 best solution, best possible 3726.485 (338.32 seconds)
Cbc0004I Integer solution of 11220 found after 484593 iterations and 312 nodes (348.20 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 611 rows 328 columns
Cbc0010I After 400 nodes, 133 on tree, 11220 best solution, best possible 3726.485 (406.89 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 526 rows 271 columns
Cbc0010I After 500 nodes, 173 on tree, 11220 best solution, best possible 3726.485 (468.77 seconds)
Cbc0004I Integer solution of 10560 found after 713473 iterations and 535 nodes (487.84 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 1114 rows 558 columns
Cbc0010I After 600 nodes, 193 on tree, 10560 best solution, best possible 3726.485 (529.99 seconds)
Cbc0010I After 700 nodes, 230 on tree, 10560 best solution, best possible 3726.485 (597.53 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 805 rows 379 columns
Cbc0010I After 800 nodes, 260 on tree, 10560 best solution, best possible 3726.485 (669.03 seconds)
Cbc0004I Integer solution of 9240 found after 1009270 iterations and 833 nodes (687.91 seconds)
Cbc0004I Integer solution of 9020 found after 1019787 iterations and 852 nodes (696.64 seconds)
Cbc0010I After 900 nodes, 178 on tree, 9020 best solution, best possible 3726.485 (724.82 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 424 rows 192 columns
Cbc0010I After 1000 nodes, 179 on tree, 9020 best solution, best possible 3726.485 (775.06 seconds)
Cbc0010I After 1100 nodes, 165 on tree, 9020 best solution, best possible 3726.485 (803.27 seconds)
Cbc0010I After 1200 nodes, 152 on tree, 9020 best solution, best possible 3726.485 (831.41 seconds)
Cbc0010I After 1300 nodes, 148 on tree, 9020 best solution, best possible 3726.485 (863.80 seconds)
Cbc0010I After 1400 nodes, 134 on tree, 9020 best solution, best possible 3726.485 (891.51 seconds)
Cbc0010I After 1500 nodes, 111 on tree, 9020 best solution, best possible 3726.485 (915.17 seconds)
Cbc0010I After 1600 nodes, 101 on tree, 9020 best solution, best possible 3726.485 (946.40 seconds)
Cbc0010I After 1700 nodes, 84 on tree, 9020 best solution, best possible 3726.485 (971.88 seconds)
Cbc0010I After 1800 nodes, 76 on tree, 9020 best solution, best possible 3726.485 (1003.15 seconds)
Cbc0010I After 1900 nodes, 64 on tree, 9020 best solution, best possible 3726.485 (1033.27 seconds)
Cbc0010I After 2000 nodes, 53 on tree, 9020 best solution, best possible 3726.485 (1060.32 seconds)
Cbc0010I After 2100 nodes, 41 on tree, 9020 best solution, best possible 3726.485 (1085.07 seconds)
Cbc0004I Integer solution of 8800 found after 1668751 iterations and 2134 nodes (1094.59 seconds)
Cbc0010I After 2200 nodes, 40 on tree, 8800 best solution, best possible 3726.485 (1120.30 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 484 rows 250 columns
Cbc0010I After 2300 nodes, 24 on tree, 8800 best solution, best possible 3726.485 (1148.54 seconds)
Cbc0038I Full problem 7878 rows 6274 columns, reduced to 709 rows 338 columns
Cbc0010I After 2400 nodes, 7 on tree, 8800 best solution, best possible 3726.485 (1178.25 seconds)
Cbc0010I After 2500 nodes, 3 on tree, 8800 best solution, best possible 3726.485 (1226.43 seconds)
Cbc0001I Search completed - best objective 8800, took 1944652 iterations and 2522 nodes (1242.28 seconds)
Cbc0032I Strong branching done 19354 times (1699716 iterations), fathomed 22 nodes and fixed 107 variables
Cbc0035I Maximum depth 39, 151652 variables fixed on reduced cost
Cuts at root node changed objective from 1595 to 3726.48
Probing was tried 2457 times and created 63547 cuts of which 0 were active after adding rounds of cuts (18.517 seconds)
Gomory was tried 2345 times and created 4342 cuts of which 0 were active after adding rounds of cuts (48.659 seconds)
Knapsack was tried 2345 times and created 18033 cuts of which 0 were active after adding rounds of cuts (39.799 seconds)
Clique was tried 16 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.013 seconds)
MixedIntegerRounding2 was tried 16 times and created 10 cuts of which 0 were active after adding rounds of cuts (0.186 seconds)
FlowCover was tried 16 times and created 0 cuts of which 0 were active after adding rounds of cuts (0.012 seconds)
TwoMirCuts was tried 2345 times and created 2130 cuts of which 0 were active after adding rounds of cuts (18.864 seconds)
ImplicationCuts was tried 155 times and created 1731 cuts of which 0 were active after adding rounds of cuts (0.146 seconds)
Result - Optimal solution found
Objective value: 8800.00000000
Enumerated nodes: 2522
Total iterations: 1944652
Time (CPU seconds): 1242.56
Time (Wallclock seconds): 1254.64
Total time (CPU seconds): 1242.61 (Wallclock seconds): 1254.69
snapdragon:v2june17 joshua$
snapdragon:v2june17 joshua$ gurobi_cl Threads=1 0.mps
Set parameter Threads to value 1
Gurobi Optimizer version 8.0.0 build v8.0.0rc0 (mac64)
Copyright (c) 2018, Gurobi Optimization, LLC
Read MPS format model from file 0.mps
Reading time = 0.04 seconds
TIP: 13408 rows, 10198 columns, 59307 nonzeros
Optimize a model with 13408 rows, 10198 columns and 59307 nonzeros
Variable types: 0 continuous, 10198 integer (10198 binary)
Coefficient statistics:
Matrix range [1e+00, 2e+01]
Objective range [1e+02, 2e+06]
Bounds range [1e+00, 1e+00]
RHS range [1e+00, 6e+01]
Presolve removed 7113 rows and 4144 columns
Presolve time: 0.59s
Presolved: 6295 rows, 6054 columns, 30797 nonzeros
Variable types: 0 continuous, 6054 integer (6053 binary)
Root relaxation: objective 3.300000e+03, 1690 iterations, 0.10 seconds
Nodes | Current Node | Objective Bounds | Work
Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time
0 0 3300.00000 0 103 - 3300.00000 - - 0s
0 0 3538.33333 0 288 - 3538.33333 - - 1s
0 0 3538.33333 0 293 - 3538.33333 - - 1s
0 0 3797.61905 0 427 - 3797.61905 - - 1s
0 0 3797.61905 0 411 - 3797.61905 - - 1s
0 0 4041.63158 0 478 - 4041.63158 - - 1s
0 0 4041.63158 0 473 - 4041.63158 - - 2s
0 0 4188.05395 0 555 - 4188.05395 - - 2s
0 0 4206.60521 0 460 - 4206.60521 - - 2s
0 0 4206.60521 0 460 - 4206.60521 - - 2s
0 0 4262.08955 0 438 - 4262.08955 - - 2s
0 0 4262.08955 0 438 - 4262.08955 - - 2s
0 0 4356.42308 0 499 - 4356.42308 - - 2s
0 0 4356.95652 0 454 - 4356.95652 - - 2s
0 0 4356.95652 0 455 - 4356.95652 - - 2s
0 0 4378.09955 0 563 - 4378.09955 - - 2s
0 0 4378.11100 0 558 - 4378.11100 - - 3s
0 0 4427.78499 0 687 - 4427.78499 - - 3s
0 0 4429.07282 0 694 - 4429.07282 - - 3s
0 0 4429.46639 0 698 - 4429.46639 - - 3s
0 0 4444.50491 0 640 - 4444.50491 - - 3s
0 0 4449.74359 0 635 - 4449.74359 - - 3s
0 0 4449.74359 0 632 - 4449.74359 - - 3s
0 0 4450.54054 0 538 - 4450.54054 - - 3s
0 0 4452.74854 0 632 - 4452.74854 - - 3s
0 0 4453.28537 0 647 - 4453.28537 - - 3s
0 0 4460.00000 0 519 - 4460.00000 - - 3s
0 0 4460.00000 0 523 - 4460.00000 - - 3s
0 0 4462.42599 0 586 - 4462.42599 - - 3s
0 0 4462.54133 0 513 - 4462.54133 - - 3s
0 0 4462.54133 0 508 - 4462.54133 - - 3s
0 0 4462.54133 0 509 - 4462.54133 - - 3s
0 0 4462.54133 0 535 - 4462.54133 - - 4s
0 0 4462.54133 0 534 - 4462.54133 - - 4s
0 0 4462.54133 0 496 - 4462.54133 - - 4s
0 0 4462.54133 0 495 - 4462.54133 - - 4s
0 2 4463.23820 0 488 - 4463.23820 - - 6s
* 28 23 18 8800.0000000 4511.77500 48.7% 567 8s
60 34 5005.00000 3 338 8800.00000 4642.00000 47.2% 414 10s
203 74 6532.77778 5 345 8800.00000 5192.00000 41.0% 292 15s
351 122 8337.84722 9 355 8800.00000 5525.71429 37.2% 276 20s
521 135 7970.00000 10 371 8800.00000 6028.00000 31.5% 261 25s
686 146 7822.22222 8 317 8800.00000 6361.80451 27.7% 254 30s
839 150 7024.28571 5 384 8800.00000 6600.00000 25.0% 254 35s
1000 162 7464.28571 8 196 8800.00000 6820.00000 22.5% 247 40s
1158 166 8530.00000 13 360 8800.00000 7040.00000 20.0% 245 45s
1323 160 8030.00000 8 351 8800.00000 7145.76923 18.8% 240 50s
1445 149 7333.33333 9 177 8800.00000 7275.71429 17.3% 241 55s
1594 125 7796.25000 10 426 8800.00000 7505.10870 14.7% 236 60s
1776 91 8552.50000 12 249 8800.00000 7777.80488 11.6% 232 65s
1967 37 8417.20000 9 357 8800.00000 8240.00000 6.36% 226 70s
Cutting planes:
Gomory: 2
Cover: 214
Implied bound: 2
Clique: 91
MIR: 44
StrongCG: 1
Flow cover: 1
GUB cover: 19
Inf proof: 6
Zero half: 30
Mod-K: 1
Explored 2041 nodes (472817 simplex iterations) in 71.76 seconds
Thread count was 1 (of 8 available processors)
Solution count 1: 8800
Optimal solution found (tolerance 1.00e-04)
Best objective 8.800000000000e+03, best bound 8.800000000000e+03, gap 0.0000%
_______________________________________________
Help-glpk mailing list
[email protected]
https://lists.gnu.org/mailman/listinfo/help-glpk