Two curses affecting Mixed-integer programming computation

In today’s last post dedicated to the #MIP2013 workshop, I examine two sources of complexity affecting research in mixed-integer (linear and nonlinear) programming.

Curse of Dimensionality

Although the term was coined by Richard E. Bellman in context of dynamic programming, this applies to most aspects of integer programming. Even a LP-based polytope has an exponential number of extreme points, and a model with n binary variables allows for 2n possible combinations (they might be feasible or not). My point is, for any realistic-sized problem, we have to be clever because enumeration is just not possible. Probing, preprocessing, cutting planes and other techniques that cuts off large portions of the search space are thus really powerful – when applied with good measure.

That being said, MIP theory does not explain everything. Quite often, algorithms for which we have a very bad worst case performance (simplex, branch and bound, and so on) just work quite well in practice. Also, some other elements need to be taken into account when working in higher dimension, such as the use of cutting planes that can ultimately slow down a branch-and-cut algorithm. For better or worse, theoretical results are often left in the closet in favor of compromises found through empirical experimentation. I’m sure the solver developer veterans have a lot to say about this.

Curse of instance-dependent parameters

Mixed-integer computation is complex, and Lodi would say, inherently heuristic. Every tool out of the toolbox (cutting planes, branching rules, heuristics, preprocessing or probing techniques) works great on some models while being useless in others. Worse, the “best” settings often differ between instances of a given problem, making any kind of performance prediction difficult. Whereas it’s relatively easy to determine what are the best parameters to solve a given model – just try everything, it’s difficult to know a priori what will work best. Some authors have worked on this very problem [1], but much more work remains to be done in this matter.

Curse of Performance Variability

According to Koch et al. (2011) [2] one often experiences difference in behavior when using the same solver to solve the same model. Performance-neutral changes such as the input order of the constraints often affect performance in unexpected yet profound ways. At Forac, where I work, we often have problems with a scripting engine written in Python, not because it’s too slow but because we have no control over how elements are put into a set – and thus, in which order constraints are entered into CPLEX.

Performance variability is especially hard to explain to end users, who quite often expect sustainable performance (i.e. with very low variance) and have trouble understanding why today’s production planning model is difficult to solve while yesterdays was really easy and took 2 seconds. Overcoming these curses will be quite a challenge for MIPpers, whether they work on the theory or practice side of MIP.

A foreword

I wish to thank this year’s MIP Workshop organizers as the venue was great and the schedule allowed for plenty of time to discuss and exchange with one another. Thanks to the speakers too, for the talks were pretty much interesting.

[1] Frank Hutter, Holger H. Hoos, Kevin Leyton-Brown, and Thomas Stützle. ParamILS: An Automatic Algorithm Configuration Framework, Journal of Artificial Research 36, 2009, pages 267-306.

[2] Thorsten Koch et al.  MIPLIB 2010, Mathematical Programming Computation 3, 2011, pages 103-163.

Comments

  1. You make two good points (at least) here: first, complexity theory isn’t very useful as it mostly focuses on worst case analysis. In practice, algorithms behave much better than worst case (or their wouldn’t be much practice…)
    But, worst case can pop up still, yielding to performance variability difficult to explain to layman. I’m afraid we’ll experience some of it for a while, unless someone fixes worst case once and for all (eg by proving P=NP).

Speak Your Mind

*