23
$\begingroup$

Mixed-integer programming is a super powerful tool for operations researchers to solve many difficult problems.

As described by Bixby[1] there has been an overall improvement in the performance of a factor of over 1.1M X since the early 1990s. Giving a ~1.8x speed-up per year.

We have Moores law, predicting the exponential increase in computer power, and Kryder's Law predicting the exponential increase in storage capacity. I have though never seen a similar prediction for mixed-integer programming performance despite fairly consistent algorithmic improvements.

  • What speed-up is it most likely we will see in the next 10 years?
  • What are the reasons for a lower rate in the future than what we have seen in the last 30 years?
  • What are the reasons for a higher rate in the future than what we have seen in the last 30 years?
  • Which trends and technologies will have an impact on this?

[1]https://people.bath.ac.uk/masjhd/Others/Bixby2015a.pdf

$\endgroup$
10
  • 12
    $\begingroup$ Be sure to read "Amazing Solver Speedups" bob4er.blogspot.com from 2015 by Bob Fourer. $\endgroup$ Nov 5 '20 at 17:41
  • $\begingroup$ Thanks a lot for your interesting comment, Mark. We knew this note by Bob and we like it. Everything is clearly explained. More generally, take a problem for which your algorithm is slow, work a little bit to improve, then claim to have terrific speedup. Or how to transform bad news into good news. Nice marketing. $\endgroup$ Nov 6 '20 at 1:01
  • $\begingroup$ Great blog post. Thanks for sharing! The way to define "speed-up" is surely debatable. $\endgroup$ Nov 6 '20 at 7:49
  • 1
    $\begingroup$ This seems like it will attract answers that are Primarily Opinion Based... $\endgroup$ Nov 10 '20 at 1:33
  • 2
    $\begingroup$ @MarkL.Stone I see your perspective but this isn't really the place for sarcastic comments like that. OP asked me a question, I answered honestly. I'm trying to engage respectfully, and with the idea that I might be wrong. If you want to discuss, I'm happy to discuss in chat or on Meta. $\endgroup$ Nov 11 '20 at 13:23
21
+50
$\begingroup$

I work at a solver company (SAS Institute Inc.) and can probably weigh in on this a little bit.

The problem with saying anything about performance is that there is a lot of variability between instances in mixed integer programming. Naturally that evens out a bit if looking at a longer time frame and more instances. In the past solver developers typically lacked the resources to get data from running a lot of instances (and almost never added randomization). This has been changing in the last few years so benchmarking got better but that meant that the resulting perceived gains got smaller.

What speed-up is it most likely we will see in the next 10 years?

From my experience, and also from talking to other people in my field, I would guess that an average improvement on a big set of instances (thousands) of about factor 1.3 year-to-year is a good year in solver development. This might vary a lot, but that is the number that is in my head.

What are the reasons for a lower rate in the future than what we have seen in the last 30 years?

There was a time in the late 90s and early 2000s in which the solver companies mined the research community for useful results and achieved a lot of speedup. Recently, in my perception, less research is focused on mixed integer linear programming, so there is probably less to mine there.

What are the reasons for a higher rate in the future than what we have seen in the last 30 years?

More computing resources allow for more benchmarking and more experimentation. Also storing more test data is less of a problem than it used to be. There is always a chance that revolutionary new algorithm idea emerges, but I would not hold my breath for that. Solvers are very sophisticated, any significant improvement kind of has to build on what we already have or it will be very time consuming to re-do all the previous work in a different framework.

Which trends and technologies will have an impact on this?

Some people claim that tuning and making decisions in the solver with machine learning will make a huge impact, but I personally am skeptical and am not aware of a real breakthrough result there. More cores and more parallelization are also not going to help, except maybe from improvements in compilers and programming languages, such as micro-threading and the like. From all information I have, quantum computing is many, many years away from being reliable and accurate enough to matter for linear algebra heavy applications, if it ever gets there, so I don't think it will matter in your 10 year timeframe. The best bet is improvements from theoretical results that are successfully transferred into working code. In the past that was what made solvers faster, the last big innovation there, symmetry handling through orbital branching, was such a deeply mathematical result applied in a clever way to solve certain instances.

$\endgroup$
5
  • $\begingroup$ Kudos for mentioning quantum computing! $\endgroup$
    – Kuifje
    Nov 12 '20 at 10:40
  • $\begingroup$ Well-thought out and measured answer! But OB "deeply mathematical result" and "clever"? That is nonsense. $\endgroup$ Nov 12 '20 at 13:28
  • 2
    $\begingroup$ Well, the use of group theory and symmetry to understand why symmetric instances are hard is pretty mathematical, think Francois Margots papers. Orbital branching is a clever and elegant way to exploit these results in an implementable way. $\endgroup$ Nov 12 '20 at 13:44
  • 2
    $\begingroup$ That was a joke. Apparently not a very good one, as I needed to explain that it indeed was a joke. $\endgroup$ Nov 14 '20 at 14:53
  • $\begingroup$ Thanks for a good and well-founded answer! $\endgroup$ Nov 16 '20 at 7:54
4
$\begingroup$

More than speedup improvement factors on a bunch of abstract LP/MPS files, we at LocalSolver think that this is more interesting to look at problems. We look at academic problems, used as benchmarks by the research, and at the core of many industrial problems. Here are some examples: traveling salesman, vehicle routing, job scheduling, multidimensional knapsack, bin packing, facility location, quadratic assignment, clustering like k-means, unit commitment, network design, optimal power flow, pooling, portfolio optimization, pricing optimization, etc. We look at problems posed in the context of OR competitions like the ROADEF challenges. But mostly, we look at the problems of our clients.

For each problem, we benchmark LocalSolver against the latest research. We mostly look at the size of the instances which are solvable to near optimality in minutes. Because according to us, this is what users want in the industry. For each problem, the goal is to reach the scale of the instances encountered in practice. We first concentrate on delivering near-optimal solutions in minutes, even with bad lower bounds. Then, we work to reach near-optimal lower bounds, that is, the holy grail of near-optimal gaps.

Over the next 10 years, what will be really interesting will be to have more problems "solved" according to the definition above. For example, we started working on the Capacitated Vehicle Routing Problem (CVRP) almost 10 years ago. In the prototype version developed in 2010, modeling the CVRP was tedious and we got almost no feasible solution to instances with just 10 clients to serve. With the last 9.5 version released in 2020, LocalSolver finds near-optimal solutions in minutes to CVRP instances with hundreds of clients to serve. Moreover, this is possible by using using a 10-line mathematical model. In the next version 10, LocalSolver will provide quality lower bounds for instances with 100 clients.

Our goal is not to make publicity here but to share views and practices that may help to improve optimization solvers, which are important tools for the practice of OR.

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