The Dark Side is strong within this year’s community

This post is written in the context of the 2013 Mixed Integer Programming workshop, held in Madison WI.  It is humorous rather than serious in nature, so please do not take this post too seriously. Day #1 from MIP 2013 workshop was rich and diverse in terms of technical content. Talks from speakers such as Tobias Achterberg and Pietro Belloti are difficult to summarize in a few words. So I would like to use an analogy taken from the world of Star Wars to describe what I found during day 1.

What is the Dark Side of OR?

Andrea Lodi often refers to heuristics as the “dark side” of MIP solvers [1]. Dark Side OR practitioners are ready to use any tool if it helps solve optimization problems more quickly and efficiently. Primal heuristics, presolving, probing and heuristic techniques are fine as long as it helps solve more problems faster. Dark Side OR does not ask the question whether a concept is elegant or based on theorems and proofs, but seeks to strike a mix of short computation time for the maximum reduction in total computing effort required to solve a model.

The Dark Side was quite present in both Tobias Achterberg’s and George Nemhauser’s talks. Probing techniques offer no guarantee that the time invested is worth the effort, but a technique is implemented as long as it helps solve a significant proportion of various MIP models more quickly and it doesn’t hurt overall performance. Although it is based on the well-known branch-and-bound technique, George Nemhauser’s relax-and-restrict search is inherently heuristic in nature.

A well known symptom of the Dark Side in OR is the use of many parameters.

What about the Light Side?

The light side is comprised of several talks that take root in mixed-integer programming theory. Light side operations researchers seek to develop cutting planes and clever reformulations so as to enumerate facets of the polytopes of known problems, characterize convex hulls, or design approximation algorithms. Proofs of finite convergence to optimality is a substantial advantage in the world of light side OR.

In this year’s context, the Light Side shines most in the poster sessions, where you can find many theoretical results as well as improved characterizations of classical OR problems. Parameter-free methods are favored because they are more robust and don’t require fine-tuning steps.

Lessons from Star Wars

Just like dark side, often heuristics seem to be more powerful. But just like Yoda warns young Force users, the dark side is only easier… heuristics look more appealing, until the urge to use heuristics everywhere controls you. If you catch this disease, you may no longer be able to converge to a provable optimum. Worse, you may even discover that you no longer care for the optimum and just look for a “good” solution that can be used as soon as possible.

[1] A. Lodi, The The Heuristic (Dark) Side of MIP Solvers, in Hybrid Metaheuristics, Studies in Computational Intelligence Volume 434, 2013, pp 273-284.

Speak Your Mind