Another difficult MIP

Some MIP models are small but very difficult. An example is described here (this model has 252 binary variables). Now I am working on a very small scheduling application with only 217 binary variables. Cplex finds good solutions very quickly, but it is not able to close the gap in any significant way in 6 hours.

Some fragments of the log:

       Nodes                                         Cuts/
 Node  Left     Objective  IInf  Best Integer     Best Node    ItCnt     Gap
 
*   0+    0                           16.1636                      0     ---
    0     0        0.1000   195       16.1636        0.1000     1406   99.38%
*   0+    0                           14.1636        0.1000     1406   99.29%
    0     0        0.1000   189       14.1636      Fract: 5     2050   99.29%
*   0+    0                           13.1636        0.1000     2050   99.24%
    0     2        0.1000   189       13.1636        0.1000     2050   99.24%
*  10+    4                            3.1636        0.1000    14281   96.84%
*  40+   32                            2.1636        0.1000    42176   95.38%
  100    94        1.3142    63        2.1636        0.1000    86823   95.38%
  200   171        0.3685   127        2.1636        0.1000   129897   95.38%
  300   259        0.3646   109        2.1636        0.1000   187075   95.38%
  400   346        0.2071   106        2.1636        0.1000   228382   95.38%
  500   428        0.1500   118        2.1636        0.1000   266899   95.38%
  600   167        1.3995    65        2.1636        0.1000   331430   95.38%
  700   208        2.1535    46        2.1636        0.1000   378191   95.38%
  800   247        0.8702    74        2.1636        0.1000   443716   95.38%
  900   323        0.1286   135        2.1636        0.1000   482839   95.38%
 1000   409        1.4927    48        2.1636        0.1000   518560   95.38%
Elapsed real time = 399.27 sec. (tree size =  0.39 MB, solutions = 5)
.....
61100 52481        1.1364    98        2.1636        0.1358 30494218   93.72%
61200 52569        1.2453    56        2.1636        0.1359 30547758   93.72%
61300 52657        0.9057   121        2.1636        0.1360 30590947   93.71%
61400 52749        0.7052   114        2.1636        0.1361 30643445   93.71%
61500 52837        2.1447    58        2.1636        0.1364 30695673   93.70%
61600 52921        0.8114   105        2.1636        0.1364 30735655   93.70%
61700 53005        2.1333    89        2.1636        0.1364 30790214   93.70%
61800 53087        cutoff              2.1636        0.1364 30824849   93.70%
61900 53174        0.1500   118        2.1636        0.1364 30878206   93.70%
62000 53262        0.6538   111        2.1636        0.1364 30942477   93.70%
Elapsed real time = 21434.12 sec. (tree size = 51.02 MB, solutions = 7)
62100 53348        1.1516    75        2.1636        0.1364 31008777   93.70%
62200 53434        1.1409   113        2.1636        0.1364 31064891   93.70%
62300 53527        1.2003    90        2.1636        0.1364 31107576   93.70%
62400 53610        0.9534    91        2.1636        0.1364 31154949   93.70%
62500 53696        cutoff              2.1636        0.1364 31192217   93.70%
...
Resource limit exceeded.
  
MIP Solution:            2.163636    (31215703 iterations, 62517 nodes)
Final Solve:             2.163636    (0 iterations)
  
Best possible:           0.136364
Absolute gap:            2.027273
Relative gap:            0.936975

An integer solution with obj=2.1636 is quickly found. Two other integer solutions are found down the road, but they don't improve on this significantly. The best relaxation bound is moving very slowly, and as a result the closing of the gap is sluggish.