Tuesday, July 20, 2010

Tough little MIP's

These are two instances (related to http://yetanothermathprogrammingconsultant.blogspot.com/2010/07/multiple-length-cutting-stock-problem.html) of very small MIP models that are very tough to solve to optimality. Size is very small: 26 rows and 73 columns. The first data set solves slowly, but the second one is really tough even for the best MIP solvers (at least with default settings).

Usually models of this size solve very quickly, but with MIP’s one should always be prepared for surprises.

Workaround: just stop after a little while: the obj is most likely optimal just not proven optimal. This behavior is not unusual: the mip solvers have good heuristics so they actually find the (near) optimal solution very quickly. But proving optimality by working on the best bound is not that easy and turns out to be very expensive. A second approach would be to use the alternative formulation mentioned in http://yetanothermathprogrammingconsultant.blogspot.com/2010/07/multiple-length-cutting-stock-problem.html.

To prove optimality it makes sense to use an option like MipEmphasis (Cplex) or MipFocus (Gurobi) to move the best bound. Dataset 1 then solves quite quickly but dataset 2 is still terrible.