How much can we expect to increase the speed of mixed integer programming in the next 10 years?

Question

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}

Answer 1

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.

Answer 2

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.