title: Why is this mixed integer program so inefficient to solve?
body: <p>I'm trying to solve a MIP using GLPK and CBC, and neither solver can efficiently find the solution. The GLPK solver log shows that it quickly finds a solution that is within 0.1% of the true optimum, but then takes forever trying to find that true optimum. </p>
  
  <p>I know I can use the <code>miptol</code> arg to set a tolerance -- my question is, what about this problem causes the solver to be so inefficient finding the true optimum? I routinely solve versions of this problem with slightly different inputs and they solve in less than a second.</p>
  
  <p>Here is a <a href="https://drive.google.com/file/d/0B25wYaqR0HY3dVoycUVZVGk4R28/view?usp=sharing" rel="nofollow noreferrer">file with my problem specification</a> which can be run in GLPK with <code>glpsol --cpxlp anonymizedlp.lp</code>.</p>
  
  <p>And below is some of the GLPK log -- you'll see that a near optimal MIP solution is found within 54K iterations, and then the branch tree just starts growing and growing:</p>
  
  <pre><code>GLPSOL: GLPK LP/MIP Solver, v4.61
  Parameter(s) specified in the command line:
   --cpxlp /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp -o
   /var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.sol
  Reading problem data from '/var/folders/g6/fs71g8j575v4_whqythqw7h40000gn/T/11446-pulp.lp'...
  664 rows, 781 columns, 2576 non-zeros
  443 integer variables, 338 of which are binary
  3195 lines were read
  GLPK Integer Optimizer, v4.61
  664 rows, 781 columns, 2576 non-zeros
  443 integer variables, 338 of which are binary
  Preprocessing...
  213 constraint coefficient(s) were reduced
  524 rows, 652 columns, 2246 non-zeros
  318 integer variables, 213 of which are binary
  Scaling...
   A: min|aij| =  1.282e-01  max|aij| =  1.060e+07  ratio =  8.267e+07
  GM: min|aij| =  7.573e-01  max|aij| =  1.320e+00  ratio =  1.744e+00
  EQ: min|aij| =  6.108e-01  max|aij| =  1.000e+00  ratio =  1.637e+00
  2N: min|aij| =  3.881e-01  max|aij| =  1.355e+00  ratio =  3.491e+00
  Constructing initial basis...
  Size of triangular part is 524
  Solving LP relaxation...
  GLPK Simplex Optimizer, v4.61
  524 rows, 652 columns, 2246 non-zeros
        0: obj =  -0.000000000e+00 inf =   2.507e+02 (195)
      238: obj =  -5.821025664e+06 inf =   0.000e+00 (0)
  *   363: obj =  -7.015287886e+04 inf =   0.000e+00 (0) 1
  OPTIMAL LP SOLUTION FOUND
  Integer optimization begins...
  +   363: mip =     not found yet &lt;=              +inf        (1; 0)
  +  8606: mip =     not found yet &lt;=  -7.015289436e+04        (8239; 0)
  + 13027: mip =     not found yet &lt;=  -7.015289436e+04        (12660; 0)
  + 16367: mip =     not found yet &lt;=  -7.015289436e+04        (16000; 0)
  + 19135: mip =     not found yet &lt;=  -7.015289436e+04        (18768; 0)
  + 21523: mip =     not found yet &lt;=  -7.015289436e+04        (21156; 0)
  + 23667: mip =     not found yet &lt;=  -7.015289436e+04        (23300; 0)
  + 25415: mip =     not found yet &lt;=  -7.015289436e+04        (25048; 0)
  + 27260: mip =     not found yet &lt;=  -7.015289436e+04        (26893; 0)
  + 29055: mip =     not found yet &lt;=  -7.015289436e+04        (28688; 0)
  + 30770: mip =     not found yet &lt;=  -7.015289436e+04        (30403; 0)
  + 32362: mip =     not found yet &lt;=  -7.015289436e+04        (31995; 0)
  Time used: 60.0 secs.  Memory used: 14.1 Mb.
  + 33876: mip =     not found yet &lt;=  -7.015289436e+04        (33509; 0)
  + 35338: mip =     not found yet &lt;=  -7.015289436e+04        (34971; 0)
  + 36721: mip =     not found yet &lt;=  -7.015289436e+04        (36354; 0)
  + 38080: mip =     not found yet &lt;=  -7.015289436e+04        (37713; 0)
  + 39372: mip =     not found yet &lt;=  -7.015289436e+04        (39005; 0)
  + 40601: mip =     not found yet &lt;=  -7.015289436e+04        (40234; 0)
  + 41837: mip =     not found yet &lt;=  -7.015289436e+04        (41470; 0)
  + 43036: mip =     not found yet &lt;=  -7.015289436e+04        (42669; 0)
  + 44192: mip =     not found yet &lt;=  -7.015289436e+04        (43825; 0)
  + 45350: mip =     not found yet &lt;=  -7.015289436e+04        (44983; 0)
  + 46374: mip =     not found yet &lt;=  -7.015289436e+04        (46007; 0)
  + 47281: mip =     not found yet &lt;=  -7.015289436e+04        (46914; 0)
  Time used: 120.0 secs.  Memory used: 20.4 Mb.
  + 48220: mip =     not found yet &lt;=  -7.015289436e+04        (47853; 0)
  + 49195: mip =     not found yet &lt;=  -7.015289436e+04        (48828; 0)
  + 50131: mip =     not found yet &lt;=  -7.015289436e+04        (49764; 0)
  + 51110: mip =     not found yet &lt;=  -7.015289436e+04        (50743; 0)
  + 52131: mip =     not found yet &lt;=  -7.015289436e+04        (51764; 0)
  + 53092: mip =     not found yet &lt;=  -7.015289436e+04        (52725; 0)
  + 53901: &gt;&gt;&gt;&gt;&gt;  -7.015398607e+04 &lt;=  -7.015289436e+04 &lt; 0.1% (53532; 0)
  + 61014: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (57365; 3302)
  + 64785: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (61136; 3302)
  + 67671: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (64022; 3302)
  + 70330: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (66681; 3302)
  + 72613: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (68964; 3302)
  + 74731: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (71082; 3302)
  Time used: 180.0 secs.  Memory used: 29.9 Mb.
  + 76685: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (73036; 3302)
  + 78508: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (74859; 3302)
  + 80220: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (76571; 3302)
  + 81852: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (78203; 3302)
  + 83368: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (79719; 3302)
  + 84815: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (81166; 3302)
  + 86126: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (82477; 3302)
  + 87358: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (83709; 3302)
  + 88612: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (84963; 3302)
  + 89821: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (86172; 3302)
  + 90989: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (87340; 3302)
  + 92031: mip =  -7.015398607e+04 &lt;=  -7.015290061e+04 &lt; 0.1% (88382; 3302)
  </code></pre>