Suresh Venkatasubramanian, of the excellent Geomblog, is at SODA and covered some preconference conferences. When covering a paper that used integer programming (via CPLEX), his comment was:
It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages.
Oh, he didn’t say that, did he?
I spend most of my life “solving algorithms problems in practice by using large industrial strength packages”. I solve sports scheduling problems, logistics problems, and even problems in social choice with large scale integer programming software as my primary tool. Who says I am not sexy? Or, worse, that my research is not sexy?
I can think of a few misconceptions that might lead one to doubt the sexiness of integer programming.
- Integer Programming is uncreative. After all, you just formulate the problem in terms of variables, linear objective, and linear constraints, toss it in a code, and you are done. Where is the research?
Such a view ignores the tremendous number of choices once must make in formulating integer programming. The choice of variables, constraints, and objective can have a tremendous impact on the effectiveness of the solver. While solvers continue to get better at automatically identifying formulation improvements, formulating integer programs is still an art. It is an art, however, enhanced by theory. As we better understand the polyhedral characteristics of integer programming formulations, we create better and better formulations.
This creative effort is expanded when alternatives to “basic” formulations are included. Creating a branch-and-price, branch-and-cut, Benders, or other type of formulation can be the key to solving real problems, but may require significant research effort.
- Integer programming is slow. This seems to be the most common response I get from those outside the integer programming subfield. One quote from a person at a well-known computer science-oriented firm: “I tried integer programming. It doesn’t work.” Not “It doesn’t work for this problem” or “I couldn’t make it work”. Just “It doesn’t work”. How can a topic be sexy if it doesn’t work?
I think one of the great stories in all of mathematics and business is the incredible confluence between increased data, faster computers, algorithmic improvements, and implementation successes that have led to many orders of magnitude speed increases in integer programs. Over the last fifteen years, we have gotten much, much better at solving integer programming models. With the underlying linear programming solvers being more than million times faster (no hyperbole: both computers and algorithms provide more than a 1000 time speedup each), lots of instances formerly out of reach can now be solved routinely.
Of course, integer programming is exponential time in the worst case. But I am not sure why a polynomial time algorithm that gets an approximate solution within a factor of, say, 42 is any “sexier” than an algorithm that finds the optimal solution in a reasonable amount of time for any instance of practical import.
- Integer programming is expensive. Hey, if you have to spend tens of thousands of dollars for solutions, that really doesn’t count does it? It is like a troll dressed up in a $5,000 suit: it might look OK, but it’s not sexy!
No one has to pay a lot for high quality integer programming software. Suresh refers to this in his post:
This was surprising to me on two levels: firstly, that CPLEX is actually free for academic use (who knew!) and that such a simple approach is so effective.
Actually, all the major programs offer a way for free academic use. I particularly like Gurobi’s approach, which is based on periodic validation through a “.edu” domain, but academics can also get CPLEX (as you would have read on my blog last year) and XPRESS.
And if you are not an academic? COIN-OR offers “industrial strength” linear and integer programming in an open source approach.
In Suresh’s defense, here is the full quote, where he makes clear his support for this type of research:
It’s not the “sexiest” thing in the world to solve algorithms problems in practice by using large industrial strength packages. However, both CPLEX and SAT solvers are examples of tools that can be used in practice to solve fairly intractable problems. It still takes a lot of engineering and skill to make the heuristics work well, but it’s something that we should be using as a matter of course when designing heuristics before trying to invent an algorithm from scratch.
Suresh obviously gets it: let’s hope his post expands interest in integer programming methods for these problems.
Integer programming is useful, fast, and cheap. If that isn’t sexy (for an algorithm!), then I don’t know what is.
It’s worth pointing out that there are many situations in which getting an answer within (e.g.) 5% of optimal is good enough. Ideally you want to be able to pick a point on the trade-off between getting fast solutions and getting solutions within some % of optimality.
Heuristics aren’t certain to get you there and many approximation algorithms have fixed approximation levels that aren’t practically useful. There are polynomial time approximation schemes for some problems that can be useful for this, but there are lots of problems for which there is no PTAS.
Integer programming handles this beautifully- tell the solver you want a solution with 1.5% of optimal and it will get it for you, typically much faster than if you ask for a fully optimal solution.
The argument “Integer programming is expensive” or variants on other types of optimization are often heard. But hey if optimizing your business decisions can not out weight the cost of a commercial solver, then I am inclined to say the problem faced is not a key decision and time and energy can be spend better.
Let’s face it OR will never be sexy integral or not 🙂
And, of course, COIN-OR offers other benefits for academics besides being free (as in free beer). Open source means that you can build on prior art to customize, extend, and improve code to make it work for your problem.
Now that I’ve brought down the wrath of OR on my head, let me attempt to explain myself. The offending statement was my paraphrasing of the common feeling in the cstheory community, where it’s perceived cooler to work hard to get a worst-case approximation guarantee than engineer a solution that works well in practice.
I think that this view is misguided for practical work, and I’ll say more about it in another post. But for better or worse, this is a common view in our community.
Perhaps if MIP were fast and easy, it could be considered sexy.
How about “decent MIP solver is hard to implement from scratch”, is that a myth?… I wonder if the essential parts of modern MIP solvers could be condensed to key principles that a single person could implement in a couple of months
A colleague of mine has developed an effective Constraint Programming-based approach — a model made of existing global constraints, an ad-hoc branching heuristic, the whole run by an open CP solver — for a real-world/real-scale sheduling problem. This work was submitted this year to a major conference in Computer Systems, making one of the reviewers says:
“I worried that the clarity and cleanliness of the solution is a side-effect of being too toy-like, rather than actually benefiting from real deployment with real customers and their requirements.”
Perhaps modeling is too fun and clean to be sexy.
And the review to follow:
“Constraint solvers are notoriously difficult to use effectively in a real-world situation and I applaud the authors for managing to do so here.”
I guess modeling is effective now but it will be sexy only once prejudgments vanish.
@Yaroslav, yes, it is hard to implement a good MIP solver from scratch. Good MIP solvers embody a broad array of algorithm engineering techniques, most importantly, robust numerical analysis methods that are hard to implement well in their own right.
To begin with, you need a good LP solver, and even that’s a challenging project. Doing it well requires efficient and robust sparse linear algebra libraries, sophisticated updating techniques, and good control of error propagation. Then, it’s not just a matter of implementing simple rules for branching–the number of nodes in the enumeration tree can easily get out of hand, even on modest-sized problems. Clever branching (often problem-specific), a sizeable library of cutting plane generators (with their own efficiency and robustness issues) and a scheme for managing the cuts effectively are all critical components of an effective MIP solver. And even with all that, there’s no guarantee that on any particular problem your solver will find provably optimal solution in a timely manner. We are, after all, talking about NP-hard problems here.
While legend has it that John Forrest implemented the predecessor of COIN-OR’s CBC in a few hours, he had a lot of those components already available to him. And CBC and its component parts have been the subject of continuous improvement since its initial release. The same can be said of the commercial solvers, which is one reason they command the prices they do.
@Matt “While legend has it that John Forrest implemented the predecessor of COIN-OR’s CBC in a few hours” I have spend the whole day fixing a bug in my LU module, now I feel really stupid, since I realize it’s feasible (for some people) to make a complete MIP solver in the same amount of time…damn that’s fast 🙂 When it comes to developing optimizers hours is sadly not my unit of measurement, though I wish it was.
At my current job only Bayesian networks are sexy, 🙁
@Bo, it’s certainly unreasonable for most of us to compare ourselves against John, who’s been building optimization tools since before I punched my first Hollerith card, but the point is really that (1) SBB (that original version) was built on an existing robust infrastructure (John’s own CLP for LPs, which certainly didn’t take only a few hours and is still undergoing improvements, and CGL for cuts), and (2) its performance wasn’t all that impressive at the end of those few hours. It’s taken much longer to bring CBC to the level it’s at today.
1.Some people published their work on dedicated algorithms, with IP (CPLEX) as a beachmark. However, I always find that their IP formulations are poor. That is, they were comparing their algo. with a poor-formulated IP model.
2.Yes, IP is sexy enough. I wonder if CP(Constraint Programming) is sexy. Who can talk about the experience in CP, compared to IP?
Hmm, i see a left v/s right wing opinions here. On the left, we have CS theorists who live in an abstract world, where the more hard core ones have fallen in love with their daisy chain of clever reductions and intellectual aesthetics until kingdom come. On the right (where i belong), we have the applied folks (OR) who want to solve real problems and/or make money. For example, I have seen some novel and elegant column generation crew scheduling models for sudden and monstrous business problems conjuring up incremental savings of least 10M$ per year seemingly out of nowhere for an airline on the brink of bankruptcy. This may seem a small amount, but given the context, no model ever looked more jaw-droppingly sexier to the VP’s of the business areas. often wish i could put that reaction on my resume 🙂
p.s: those models also used sophisticated “CP”, except it was called pre-processing before the real thing 🙂
IP is smarter than sexy!
People must mind that to leverage their approaches.
After reading this post, I wrote a few lines about it this afternoon:
http://tatu-search.posterous.com/integer-programming-is-smarter-than-sexy
I guess people tend to think their own field is the sexiest thing 🙂 It is very involving to solve real world problem, even with the help of a commercial solver. In some sense, a commercial solver is like a programming language, e.g. Java. You may know the language Java well, but that doesn’t guarantee you can write a good piece of code 🙂