8
$\begingroup$

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?

$\endgroup$
9
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Highly appreciated. So one might say that on average I can not expect myself to be better informed than the total of all developers working on a solver. Sometimes though the best solution might be known in which case I could bypass a solver; but if the solution is well known, it is likely to be included in the solver anyway. $\endgroup$ – spdrnl Nov 30 '20 at 21:50
  • $\begingroup$ @spdrnl "On average" being the key term - it's perfectly possible to know something the solver developers either (i) don't know or (ii) haven't added to the solver (we have finite time to work on things), but that's pretty rare for problems that are well-known. If we know that many people need a certain performance boost for commonly encountered math it's much more likely that we've spent time implementing something special for that case. $\endgroup$ – Nikos Kazazakis Nov 30 '20 at 23:07
11
$\begingroup$

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:

  • presolve
  • cutting planes
  • heuristics
  • branching strategies

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.

$\endgroup$
2
  • $\begingroup$ You may find the cutting-plane game interesting, where you can understand how cutting planes help creating "better" solutions to the node LP solution: columbia.edu/~gm2543/cpgame.html $\endgroup$ – Richard Nov 30 '20 at 8:40
  • $\begingroup$ Got it, so MIP solvers strategize around branch and bound. Thanks! And thank you for the added references. $\endgroup$ – spdrnl Nov 30 '20 at 10:27
7
$\begingroup$

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...

$\endgroup$
1
  • $\begingroup$ Thanks for your explanation. Your explanation is more in line with my original understanding. Following up on @Sina, besides exploring MIP solvers, more direct approaches are still worth exploring for a given problem. In other words, a MIP formulation of a problem ensures the application of a lot of smart machinery, but it might or might not contain the best algorithm, depending on the quality of the solver. $\endgroup$ – spdrnl Nov 30 '20 at 12:45
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.