Solver Max – Solver efficiency: 1989 vs 2024

5 January 2024

In our previous article, we solved a combined integer linear program (MILP) mannequin with greater than 8 million binary variables. Not way back, a mannequin of that dimension would have been unsolvable. But, as soon as we had a pc with ample reminiscence, the mannequin was solved to optimality by an open supply solver in 3 hours.

In fact, not all giant fashions are solvable – even some small fashions are unsolvable, or at the least exhausting to resolve. Nonetheless, fashionable solvers, in affiliation with fashionable computer systems, allow us to resolve fashions that not-so-long-ago have been past our capabilities.

In our subsequent article, we’ll look to compile crosswords utilizing a MILP mannequin. We’re not the primary to think about using a MILP mannequin to compile crosswords. An article printed in 1989 reported makes an attempt to compile small crosswords utilizing MILP fashions. The article’s conclusion was very pessimistic, noting that:

…the prospects of utilizing integer programming for any sort of puzzle of life like dimension and with a considerable lexicon stay bleak.

Wilson, 1989, Crossword compilation using integer programming

The issues Wilson encountered have been inadequate laptop reminiscence and the time wanted to resolve a really small crossword grid, regardless that he was utilizing a then state-of-the-art million greenback superminicomputer.

However lots has modified within the 35 years since 1989. Pc {hardware} is many instances quicker, and reminiscence capability has elevated enormously. As well as, optimization solver software program has improved by orders of magnitude. Fashions that have been troublesome to resolve in 1989 are actually trivial. Options that have been unimaginable to seek out in 1989 might now be inside attain.

On this article, we estimate the magnitude of pace enchancment for optimization solvers and laptop {hardware} within the 35 years from 1989 to 2024. The outcomes could also be stunning.

1989: Crossword compilation utilizing integer programming

As a motivating instance, we take into account an early try to compile crosswords utilizing a combined integer linear program (MILP). The paper Crossword compilation using integer programming, was printed in 1989 by J. M. Wilson. That article proposes two MILP mannequin formulations for compiling crosswords:

• Mannequin 1, entire phrases. Mannequin 1 makes an attempt to suit entire phrases right into a 4×4 totally interlocking puzzle (i.e. no black cells), as proven in Determine 1. With a lexicon of 100 4-letter phrases, the issue dimension was 800 variables and 524 constraints. An answer for this 4×4 double word square puzzle was present in 1,800 seconds.
• Mannequin 2, particular person letters. Mannequin 2 makes an attempt to put particular person letters right into a grid. It’s extra memory-efficient than Mannequin 1, however it failed to seek out any options inside 3,000 seconds, even for very small grids. In any case, Mannequin 2 has a unfastened formulation that may create “phrases” that aren’t within the lexicon, so an answer (if discovered) will not be legitimate.

From Wilson’s expertise, we observe that:

• A key modelling concern was reminiscence utilization, particularly because the lexicon dimension will increase. The fashions used a lexicon of 100 phrases, which could be very limiting provided that there are a number of thousand 4-letter English phrases.
• Options have been troublesome to seek out, even for very small grids.
• A mannequin with 800 variables and 524 constraints is now thought of to be small. In 1989 it was a big mannequin.
• Dense American-style puzzles (like Determine 1) are a lot more durable to resolve than sparser British-style crossword puzzles. That is probably as a result of a dense grid has extra phrase intersections. We’ll discover this concern additional in our subsequent article.
• The modelling was carried out on a Prime 750 superminicomputer, an instance of which is proven in Determine 2. The Prime 750 superminicomputer had as much as 8 MB of RAM and it ran at 1 million directions per second (MIPS). The Prime 750 was a state-of-the-art laptop on the time. Relying on configuration, a system cost several hundred thousand US dollars within the mid to late Nineteen Eighties. That equates to about US$1,000,000 at present, adjusted for inflation.

Wilson’s paper refers to another paper that makes use of a lexicon of 1,000 4-letter phrases to compile crosswords utilizing first-order predicate logic within the Prolog programming language, noting that, “This dimension of lexicon would current an virtually unimaginable job for an integer programming mannequin.”

General, Wilson was pessimistic about utilizing integer programming for compiling crosswords, contemplating it to be impractical, concluding that “the prospects of utilizing integer programming for any sort of puzzle of life like dimension and with a considerable lexicon stay bleak”.

So, integer programming was not a viable technique for compiling crossword puzzles in 1989. However lots has modified since then.

Computer systems and solvers have improved enormously

Wilson’s paper was printed in 1989. As we write this text in early 2024, that is 35 years in the past. Since 1989, computer systems have grow to be a lot quicker, and so they have much more reminiscence. As well as, linear programming solvers have improved in each pace and class.

Within the following sections we try to estimate the magnitude of enchancment within the 35 years since 1989.

Pc enhancements

Pc pace enchancment: 1989-2024

Pc processing pace has elevated enormously over time. Based on the 50 years of microprocessor trend knowledge proven in Determine 3, single-thread Pc Processing Unit (CPU) efficiency (utilizing the SpecINT benchmark) improved from a median rating of 67 in 1988-1989 to 105,300 in 2021. That equates to an element of 1,572 instances quicker.

From 2021 to 2023, CPU single thread benchmark scores improved by an additional 10%, for a complete issue from 1989 to 2023 of 1,729 instances quicker.

Till 2004, virtually all CPUs had a single processing core. Since then, the variety of logical CPU cores (i.e., bodily cores and/or parallel threads inside a bodily core) has been rising. A typical desktop laptop now has at the least a number of cores, with many having one or two dozen cores. Some CPUs have a whole bunch of cores. Graphics card GPUs sometimes have hundreds of cores, although that could be a totally different story.

Many solvers can use a number of CPU cores, to a larger or lesser extent. For instance:

• Gurobi and CPLEX use a number of cores, by default, when fixing fashions.
• The Octeract solver engine depends on parallel processing for its excessive efficiency in fixing non-linear fashions.
• The open-source HiGHS solver has “restricted alternatives for exploiting parallel computing”, although larger use of a number of CPU cores is deliberate quickly.

Nevertheless, the pace enchancment for a number of cores in contrast with a single core, in line with Amdahl’s law, is usually a lot lower than a linear a number of of the variety of cores.

For this evaluation, we make the sweeping assumption that utilizing a number of CPUs considerably greater than doubles the efficiency of a single CPU. That’s, we estimate that complete laptop processing pace elevated by an element of about 4,000 instances (= 2.3 x 1,729) from 1989 to 2024.

Computer systems have much more reminiscence

The Prime 750 superminicomputer utilized by Wilson may have as much as 8 MB of RAM (although some installations had solely 2 or 4 MB of RAM). A contemporary desktop PC might have 8 GB of RAM – i.e., 1,024 instances as a lot reminiscence.

Although 8 GB of RAM is kind of small for a pc in 2024. For instance, the digital machine we utilized in our previous article has 128 GB of RAM – that is 16,384 instances the utmost reminiscence out there in one million greenback laptop in 1989.

Pc reminiscence in 2024 can also be many instances quicker than it was in 1989. We assume that the reminiscence pace doesn’t materially change our estimate of CPU pace enhance.

Pc prices has plummeted

On this evaluation, we’re evaluating a 1989 superminicomputer with a 2024 desktop PC – as a result of these are the machines that will sometimes be used for optimization modelling of their respective eras. However this isn’t a wholly truthful comparability, because the superminicomputer value one million {dollars} (in at present’s cash), whereas a excessive specification desktop laptop now prices just a few thousand {dollars} – a discount of greater than 99%. If we maintained value parity, then the efficiency of a 2024 laptop can be even larger.

Abstract of laptop {hardware} enhancements

In contrast with 35 years in the past, computer systems are hundreds of instances quicker, with hundreds of instances extra reminiscence, and their value has fallen by greater than 99%.

Solver enhancements

Our estimate is predicated on aggregating separate estimates for durations of time

The perfect estimate we are able to discover of how a lot optimization solvers have improved is printed by Gurobi. We begin with an evaluation by Gurobi estimating the computation progress in linear and mixed integer programming from 1991 to 2008. We then have a look at an up to date evaluation to 2020, which we lengthen to 2023.

CPLEX efficiency enchancment: 1991 to 2008

Determine 4 exhibits Gurobi’s evaluation of pace enchancment for the CPLEX solver when fixing MILP fashions, for every main software program model (bars) and cumulative (line), from 1991 to 2008.

The whole cumulative pace enchancment is an element of just about 30,000 instances quicker (word the log scale for the right-hand axis).

Over these 17 years, this equates to about 1.8 instances quicker each year, on common. Although enhancements do not happen at a gentle price, with particularly giant enhancements occurring in CPLEX variations 2.1-3.0 (inclusion of the twin simplex technique) and in CPLEX variations 6.0-6.5 (many enhancements gleaned from “mining” the tutorial literature).

Importantly, this estimate is simply the advance in solver software program efficiency, not permitting for the pace enhance of laptop {hardware} over the identical interval.

Word that we ignore any enchancment in solver efficiency from 1989 to 1991, as we do not have that data. But when the identical price of enchancment (1.8 instances each year) had occurred in these 3 years, then we might have one other issue of just about 6 instances quicker.

Gurobi efficiency enchancment: 2009 to 2023

Dr. Bixby, one of many founders of Gurobi, introduced an updated analysis of solver efficiency enchancment in 2021, as proven in Determine 5.

The determine states a cumulative enchancment issue of three,730,625 instances, from CPLEX 1.2 to Gurobi 9.1 (launched in 2020). Given the CPLEX enchancment issue of 29,530 above, this suggests a further enchancment for Gurobi of 126 instances for the interval 2009 to 2020.

Subsequent variations of Gurobi declare efficiency enhancements for MILP fashions of:

Combining these modifications, we estimate that from 2009 to 2023 the Gurobi solver’s pace improved by an element of about 178 instances.

An element of 178 over 14 years equates to a median price of about 1.45 instances each year. That is decrease than the 1.8 instances annual common price from 1991 to 2009, however it’s nonetheless spectacular nonetheless.

Solver efficiency enchancment: 1989 to 2024

General, by combining every of the solver-related steps above, we are able to estimate the cumulative enchancment in solver efficiency over the past 35 years.

The result’s that MILP solver efficiency improved by an element of 5 million instances (in spherical numbers) from 1989 to 2024. That is conservative estimate, as we exclude any enchancment which will have occurred from 1989 to 1991, and from 2023 to 2024.

This enchancment, assuming the identical laptop {hardware}, is equal to a mannequin that takes 60 seconds to resolve in 2023 taking 10 years to resolve if began in 1989. That’s, if it was potential to resolve in any respect in 1989.

Word that our solver efficiency enhance estimate is predicated on the business solvers CPLEX and Gurobi. An open-source solver, like HiGHS, is usually not as quick as CPLEX or Gurobi – maybe by an order of magnitude, more-or-less, relying on the mannequin. Although that hardly appears vital, given the magnitude of pace enhancements over the previous three+ a long time.

Solver + laptop efficiency enchancment: 1989 to 2024

Mixed end result

Combining the pc {hardware} pace enhance of 4,000 instances with the solver software program efficiency enchancment of 5 million instances, the overall enchancment from 1989 to 2024 is an element of 20 billion instances quicker!

At that price, a mannequin that takes 60 seconds to resolve in 2023 would have taken 38,000 years to resolve if began in 1989.

A grain of salt

In fact, we should not take these estimates too actually.

Firstly, there’s substantial room for variation in our estimates. Some numbers are unsure, whereas others are merely guesses. Additionally, aggregating the varied components in a multiplicative method will not be completely legitimate.

Secondly, there are lots of parts that contribute to how briskly, and even whether or not, a MILP mannequin will be solved, along with laptop and solver uncooked pace. Different parts embody reminiscence dimension, programming language options, the match between solver methodology and a mannequin’s particular traits, and modifications in solver options.

Nonetheless, the magnitude of pace will increase we have described on this article absolutely assist in fixing bigger, tougher MILP fashions. Quite a bit.

Conclusion

On this article, we estimate the pace enchancment in laptop {hardware} and optimization solver software program since 1989. This evaluation is motivated by an educational paper by Wilson, printed 35 years in the past, describing an try to compile crossword puzzles utilizing combined integer linear programming (MILP). That try was largely unsuccessful, as the duty was past the potential of MILP solvers at the moment.

However each computer systems and MILP solvers have superior enormously since 1989 – by a mixed issue of round 20 billion time quicker! That enchancment must be sufficient to offset at the least a few of Wilson’s pessimism about with the ability to compile crossword puzzles utilizing MILP fashions. Likewise for a lot of different optimization fashions.

Within the subsequent article, we try to formulate and resolve a MILP to compile crossword puzzles. That is nonetheless a troublesome downside, although given the advance in laptop and solver pace, there’s some foundation for optimism that the duty is now potential.

If you need assist with your personal fashions, then please contact us.

References

The principle references used on this article are listed beneath. Different data is linked throughout the article.

Gurobi Optimization, 2015. Computational progress in linear and mixed integer programming, accessed 13 December 2023.

Passmark Software program, 2023. Single thread CPU performance, accessed 13 December 2023.

Rupp, Ok., 2023. Microprocessor trend data, accessed 13 December 2023.

Wilson, J.M., 1989. Crossword compilation using integer programming, The Pc Journal, Quantity 32, Quantity 3, Pages 273–275.