Operations Research Stack Exchange is a question and answer site for operations research and analytics professionals, educators, and students. It only takes a minute to sign up.
Sign up to join this community
I would like to verify if I understand the nature or workings of integer programming solvers.
My understanding is that for integer programming problems like the knapsack problem or the traveling salesman problem several algorithms can be used to solve these problems. Integer programming solvers under the hood formulate a strategy using these algorithms to solve a formalized integer programming problem.
Am I correct?
I'd like to share a MIP solver developer's perspective on how our process works and what that means for the user.
A MIP solver is a massive toolbox of algorithmic tools and tricks. Because MIP is generally NP-Hard, when we design a solver we set up a basic framework (for MIP typically branch-and-bound, some parallel functionality, and a bunch of acceleration & primal heuristics), and then enter a painstaking cycle of testing combintions of algorithms on real problems and understanding implementation & algorithmic bottlenecks.
MIP solver developers combine fundamental algorithmic tools with this empirical experience to (i) elucidate and exploit special structure, and (ii) tweak algorithms & parameters to skip all calculations that can be skipped.
From the user's perspective, this all just works automatically: we identify special structure, reformulate the problem for you, resolve numerical issues in the formulation, quickly test algorithms to see what may or may not perform well in a particular situation, swap algorithms on-the-fly, and so on.
This is a process that never ends - people always come up with something we've never seen before (especially in MINLP which is my area of expertise), and the way we make it work in practice is that we start tweaking algorithms and observing changes in behaviour. It is often the case that minor tweaks can make all the difference, but a lot of the time this process leads to the development of brand-new algorithms altogether.
We try our best to make sure that the solvers will work well out of the box 100% of the time, but of course this is theoretically impossible - there's always edge cases where the default tuning just doesn't work, which is why solvers also come with options to change some of the algorithms and parameters that the solver will use.
The backbone of modern MIP solvers is the so-called branch-and-bound algorithm.
Nowadays, MIP solvers employ a variety of algorithmic tools, such as:
You can have a look at this paper by R. Bixby for an overview of such techniques, and their historical context. It is a few years old, but not a difficult read.
It's the (non-trivial) combination & interplay of all these tools that make MIP solvers so efficient.
As mtanneau said the core algorithm in MIP solvers is branch-and-bound (actually branch-and-cut) and a lot of machinery around it. But to a certain degree, solvers try to identify problem structures and might employ more problem specific algorithms if they detect a certain structure or adjust their overall solving strategy. Single constraint knapsack problems are a good example for that. Depending on the coefficients involved it is way more efficient to use a problem specific dynamic programming algorithm to solve them than using branch-and-cut. Since some of the machinery (cutting place separators for cover and flow cover cuts) require a knapsack solver anyways and it is only natural that some MIP solvers will simply call that code if they realize they got a single constraint knapsack problem as input. For other problems it might not be that straight forward, but I can say for certain that some solvers use problem structure specific heuristics to ensure they find good solutions early for problems that, for example, have some form of a traveling salesman structure (and SAS Optimization that I work on actually includes a separate TSP solver if that is what is needed). With all these things it is important to remember that MIP solver developers try to implement techniques that are as general as possible and apply to more than a narrow class of problems. But some classes of problems just can't be solved without very specific techniques (at the moment) and then that rule can be muddled up to the point of implementing very specific algorithms for very specific problems...
Modeling this problems and other types of problems like network flow problems as MIP and solving them with MIP solvers is just one of the available solutions. There are other kinds of algorithms like dynamic programming that may work better than MIP to solve this problems. As I know MIP solvers don't support this kind of algorithms. You can use solvers API and Implement the algorithm in a programming language. This allows you to combine different algorithms.
