0.mps.zipDescription: Zip archive
|
| From: | J. Friedman |
| Subject: | Re: [Help-glpk] TIPS FOR DEALING WITH LARGE PROBLEMS. |
| Date: | Sun, 17 Jun 2018 22:10:05 -0400 |
| 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 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 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. |
0.mps.zip
Description: Zip archive
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% |
| [Prev in Thread] | Current Thread | [Next in Thread] |