14 April 2024
Nathan Brixius has an interesting recent blog article about an old mixed integer programming (MIP) problem: Don Knuth’s MIP, 64 years later.
Don Knuth, a legendary computer scientist, wrote a paper in 1960 about optimizing computer performance, Minimizing drum latency time. Knuth formulated a MIP model, with 51 variables and 43 constraints. But he was unable to solve it after more than 10 hours of run time on an IBM 650 Data Processing Machine.
One issue was that the machine had only 10 kB of memory. The model was eventually solved, 35 years later in 1995, using CPLEX and a more modern computer.
Knuth describes the model, and its solution, in a note An integer programming problem unsolved for 35 years (in the "Unpublications" section).
Today, Knuth's formulation is a very small model. Demonstrating how much MIP solvers have improved over time, Nathan recreates the model and solves it with SCIP and Gurobi – each taking a fraction of a second to find an optimal solution.
This situation is reminiscent of our article Solver performance: 1989 vs 2024, in which we estimate how much the performance of MIP optimization solvers has improved over the last 35 years. Our analysis was prompted by a 1989 paper about an unsuccessful attempt to use MIP models to compile crossword puzzles. We have somewhat more success in our articles Crossword MILP - Model 1 and Crossword MILP - Model 2.
As Nathan says, the tremendous improvement in MIP solvers is another testament to the amazingly wonderful effectiveness of operations research!