Monday, December 29, 2008

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.

4 comments:

  1. I have a very similiar situation. any thought why they are so difficult to converge ? I am guessing some constraints are too expensive....

    ReplyDelete
  2. For a MIP more equations is actually often better, so constraints being 'too expensive' is probably not an issue.

    ReplyDelete
  3. what I mean by expensive is the struture of the constraints not the numbers. The constraints may be too loose to narrow down the solutions especially in some continuous-type representation rather than discrete models.

    ReplyDelete
  4. In my case the problem is highly combinatorial, with lots of symmetry, and a poorly defined cost structure to distinguish solutions. I got better performance by removing some of the symmetry. About your case: there is very little I can say in general, without studying the actual model.

    ReplyDelete