18 April 2024
When doing analysis with an optimization model we commonly need to run many cases. For example, exploring a range of input value scenarios or evaluating a set of alternative designs.
In this article, we explore running optimization model cases in parallel. Specifically, we use the Python multiprocessing and mpi4py libraries to fully use the many CPU cores/threads in modern computers.
Our goals are to:
- Illustrate how to apply the multiprocessing and mpi4py libraries to running optimization model cases in parallel.
- Measure the performance of running cases in parallel compared with serially.
- Compare the performance of an old 4 core / 4 thread CPU with a new 20 core / 28 thread CPU, using the HiGHS solver.
As an example, we convert the serial model from a previous article, Warehouse space for free: Exogenous enumeration, to run multiple cases in parallel.
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!
27 March 2024
We conclude our project to improve the efficiency of a pallet warehouse by redesigning the warehouse's racks and shelves.
In part 2 of this article series, we linearized our warehouse racks and shelves design model with the hope of making it easier to solve at the full scale we need. It didn't work. Model 2 is even slower than the non-linear Model 1 we built in part 1.
In this article, we simplify our modelling by taking some of the variables out of the model and making them exogenous inputs. We enumerate all possible combinations of those exogenous inputs, then solve the simplified model for each combination. Hopefully, this time, our model will be solvable at the scale we need.
18 March 2024
In the first part of this article series, we formulated and implemented Model 1 for redesigning a pallet warehouse. Model 1, which in non-linear, works OK for small data sets, but it fails to find a good solution for the full data set.
In this article, we linearize our model using a standard technique. The idea is that, all going well, a linear model will be solvable at the scale we need.
11 March 2024
A common problem for warehouse managers is finding enough space to store everything:
We just don't have enough storage space. There used to be, but the company grew. Now, we have pallets stored in the dispatch area. They get in the way, and it's a health and safety hazard.
Warehouse Manager
In this article series, we look at improving the efficiency of a pallet warehouse (also known as a unit-load warehouse), where all items are stored on standard-size pallets.
Most pallet warehouses use a rack design where all shelves are the same size. This may not be the best design. Specifically, if the pallets have varying heights, then a single shelf height – designed to accommodate the tallest pallet – leaves unused space above some pallets. Depending on the mix of pallet heights, there's potentially a lot of unused space in aggregate.
To address this issue, we build a model of the warehouse's racks and shelves. Our objective is to find a design that minimizes the number of racks required to accommodate all pallets in the warehouse.
Along the way, we:
- Formulate a non-linear model of the situation.
- Compare several solvers, to see how they perform.
- Linearize our model to, hopefully, make it easier to solve.
- Disaggregate our model to make some variables exogenous, then iterate over an enumeration of the exogenous variables.
- Demonstrate use of Pyomo's
last()andnext()functions, which enable us to work with elements of ordered sets. - Turn off a constraint using Pyomo's
deactivate()function.
Importantly, we show that there's a surprising amount of extra storage space available for free, or minimal cost, just by redesigning the warehouse's racks and shelves.
13 February 2024
We're often asked questions about the seemingly odd behaviour of some models:
- Why does my model find different solutions each time I run it?
- The solver says the different solutions are all optimal. But some solutions are better than others. How can that be true?
- What can I do to make my model find the overall best solution?
In most cases, the answers are:
- The model is non-linear with multiple local optima. The solver may use a process that includes random elements that lead it to different neighbourhoods of the feasible region.
- Each solution is locally optimal, meaning that it is the best solution in that neighbourhood of the feasible region.
- To find the overall best solution, either use a solver than finds globally optimal solutions for that type of model, or solve the model multiple times, with different initial conditions, to make it more likely that the solver finds the best neighbourhood.
These answers generally require explanation, So, in this article, we explore some aspects of solver behaviour when solving non-linear optimization models. Our goal is to provide insights into what the solvers are doing, why they may find different solutions, and how we can improve our chances of finding at least a good, and hopefully a globally optimal, solution.
10 January 2024
In Part 1 of this series, we formulated a Mixed Integer Linear Program (MILP) for compiling crossword puzzles. Model 1 works OK, provided the crossword grid is small, not too dense, and the lexicon isn't too large. But as the grid gets denser and/or the lexicon gets larger, Model 1 struggles to find solutions.
We can do better. Model 1 uses a general formulation, where we specify the form of each constraint and then let the solver work out which variables and constraint instances aren't needed, given a specific data set. For many models, this approach is sufficient – largely because modern optimization solvers are very good at eliminating unnecessary terms in a model, especially in the presolve phase.
But solvers use general-purpose procedures for tightening models. Sometimes we can make use of our knowledge about the specific situation to help the solver.
In this article, we discuss techniques for fine-tuning the model-building process in Pyomo, to make a smaller and faster model. Specifically, we:
- Select only those words in the lexicon that fit in the current grid.
- Pre-populate some grid word slots with random words, to give the solver a head start.
- Omit constraint terms that don't meet some criteria.
- Skip some constraint instances entirely.
- Fix some binary variable values at zero, when we know they cannot have a value of one.
These steps tighten the model, making it easier for the solver to find a solution. We'll then look to solve larger crossword compilation problems.
10 January 2024
Completing crossword puzzles is a popular pastime. There are many puzzle variations, ranging from simple to fiendishly difficult.
The process of creating a crossword puzzle – known as "compiling" – is difficult. Compiling a crossword can be thought of as a type of search problem, where we need to find a set of words that fits the rules for filling a specific crossword grid. Unsurprisingly, many crossword compilers use software to help them find a suitable set of words.
One approach is described in an excellent recent article on Philippe Olivier's blog: Generating crossword grids using Constraint Programming. That article inspired us to try using a different method: Mixed Integer Linear Programming (MILP).
We're not the first to consider using MILP to compile crosswords. An article published by Wilson in 1989 reported attempts to compile small crosswords using MILP models, as discussed in our previous article Solver performance - 1989 vs 2024. Wilson's conclusion was very pessimistic, noting that "the prospects of using integer programming for any type of puzzle of realistic size and with a substantial lexicon remain bleak". The problems were insufficient computer memory and the time need to solve even a small crossword grid using a then state-of-the-art, million-dollar superminicomputer.
But a lot has changed in the 35 years since 1989. Computers are thousands of times faster, and their memory capacity has increased by a similar factor. In addition, optimization solver software is literally millions of times faster. Models that were difficult to solve in 1989 are now trivial. Solutions that were impossible to find in 1989 may now be within reach. Does that include compiling crosswords of realistic size?
In this series of articles, we discuss:
- Representing a word puzzle in mathematical terms, enabling us to formulate the crossword compilation problem as a MILP model.
- Techniques for fine-tuning the model-building process in Pyomo, to make a model smaller and faster, including omitting constraint terms, skipping constraints, and fixing variable values.
5 January 2024
In our previous article, we solved a mixed integer linear program (MILP) model with more than 8 million binary variables. Not long ago, a model of that size would have been unsolvable. Yet, once we had a computer with sufficient memory, the model was solved to optimality by an open source solver in 3 hours.
Of course, not all large models are solvable – even some small models are unsolvable, or at least hard to solve. Nonetheless, modern solvers, in association with modern computers, enable us to solve models that not-so-long-ago were beyond our capabilities.
In our next article, we look to compile crosswords using a MILP model. We're not the first to consider using a MILP model to compile crosswords. An article published in 1989 reported attempts to compile small crosswords using MILP models. The article's conclusion was very pessimistic, noting that:
...the prospects of using integer programming for any type of puzzle of realistic size and with a substantial lexicon remain bleak.
Wilson, 1989, Crossword compilation using integer programming
The problems Wilson encountered were insufficient computer memory and the time needed to solve a very small crossword grid, even though he was using a then state-of-the-art million dollar superminicomputer.
But a lot has changed in the 35 years since 1989. Computer hardware is many times faster, and memory capacity has increased enormously. In addition, optimization solver software has improved by orders of magnitude. Models that were difficult to solve in 1989 are now trivial. Solutions that were impossible to find in 1989 may now be within reach.
In this article, we estimate the magnitude of speed improvement for optimization solvers and computer hardware in the 35 years from 1989 to 2024. The results may be surprising.
13 December 2023
We conclude our article series looking at a common modelling issue: The solution is optimal, but not practical.
In a previous article of this series, we solved Model 3 to optimality with the full data set of 100 items. Given the large memory requirements of Model 3, a data set with 100 items is close to the maximum that we can solve on our modelling computer. But what if we need to solve a larger data set?
Model 4 provides one approach, using a heuristic random column generation technique that finds very good solutions, though they are not guaranteed to be globally optimal.
The variants of Model 5 all have even more variables and constraints than Model 3, so they don't help us solve larger data sets.
To find guaranteed, globally optimal solutions we need to use Model 3. That requires a computer with more memory – potentially a lot more memory. We could upgrade our modelling computer. If there's a need to often solve very large models, then that would likely be the best option. But if the need is less frequent, then a potentially cost-effective solution is to use a virtual machine in "the cloud".
In this article, we adopt the latter approach. We describe, in detail, setting up a Google Compute Engine, provisioned with 128 GB RAM, and using it to solve Model 3 to global optimality with a data set that is larger than we can solve on our local computer.