1 December 2023
We continue our article series looking at a common modelling issue: The solution is optimal, but not practical.
In the previous article of this series, we explicitly formulated either/or constraints by manually creating $BigM$ constraints. That technique works, though it can be a bit tricky to get right.
An alternative approach, since we're using Pyomo, is to use the Generalized Disjunctive Programming (GDP) extension that is part of Pyomo. GDP can represent a variety of logical implications, like either/or, and automatically translate them into a form that a solver can work with.
In this article, we describe how the GDP extension can be used to represent either/or constraints in a simple linear program. Along the way, we compare $BigM$ constraints that we create manually with $BigM$ constraints created automatically by the GDP extension. Then we use the GDP extension to build either/or constraints in our paper coverage situation, as variant Model 5c.
21 November 2023
We continue our article series looking at a common modelling issue: The solution is optimal, but not practical.
In the first article of this series, we made the assertion that we can implicitly mimic rotation of the items by sorting the item dimensions so that the width is always the longer side. Therefore, we didn't need to explicitly represent the orientation of the items in our earlier models.
This insight may not be obvious, so in this article we explicitly model rotation of the items using either/or constraints. That is, we want to represent items that are in either portrait or landscape orientation, with the model choosing only one of the orientations for each product.
The problem is that, in a mathematical programming model, all constraints are always evaluated. So, we can't have a condition like:
If orientation is portrait
then use constraint for portrait
else use constraint for landscape
Instead, we need to create a pair of constraints that behave the way we want, while both are always evaluated. This is done using a binary variable, which acts as a switch to decide which constraint is "active", and some $BigM$ parameters that change each constraint's right-hand-side in a very specific way.
Our objectives in this article are to:
- Illustrate how to formulate and implement either/or constraints in an integer programming model, using $BigM$ constraints.
- See how our model behaves when explicitly including either/or constraints.
- Demonstrate that our dimension sorting assertion is correct.
11 November 2023
We continue our article series looking at a common modelling issue: The solution is optimal, but not practical.
In the previous article, we built Model 3 for our paper coverage problem – a linear model that enumerates all possible stock paper size combinations, then chooses the sizes that minimize trim waste. Model 3 finds globally optimal solutions for each case, so we've solved the original problem. But, from a modelling perspective, there's more we can learn from this situation.
An issue with Model 3 is that it is close to the maximum size we can solve, due to memory usage. This is somewhat unusual – normally, we're concerned about the time to solve a model, but for this model the concern is the amount of memory it needs. Specifically, the number of variables and the amount of memory used both increase with the cube of the number of items. For example, an instance with 100 items has more than 1,000,000 variables, and the HiGHS solver uses up to 7.5 GB of RAM. If we double the number of items, to 200, then the model would have more than 8,000,000 variables and require more RAM than our PC has (we tried).
So, if we can't use Model 3 with a larger data set, then what can we do? Model 2 found good, though mostly sub-optimal, solutions by considering only a 1% subset of the possible stock product combinations. In this article, we develop Model 4 which extends Model 2 by adding randomly generated stock product candidates. The idea is that the solver might be able to find better solutions using a larger subset of candidates, without needing to consider every possible candidate simultaneously.
Our approach for Model 4 is a type of random column generation technique. Strictly speaking, we're not doing standard column generation, which uses a sub-model to decide which columns to add. Instead, we randomly generate columns, solve the model, then repeat some number of times while noting the best solution found. This approach isn't guaranteed to find globally optimal solutions, but it should get close.
4 November 2023
We continue our article series looking at a common modelling issue: The solution is optimal, but not practical.
In the previous article, we built Model 2 for our paper coverage problem – a linear model that considered a subset of the possible stock paper size combinations. Model 2 found optimal solutions for each case in around 2 seconds, which is an enormous improvement compared with the performance of the non-linear Model 1. However, because we use only a subset of the possible combinations, Model 2's solutions are not globally optimal.
In this article, we extend Model 2 to consider all possible combinations of stock paper sizes. Consequently, Model 3 is quite large, with more than 1 million binary variables. If we can solve this model, then it should produce globally optimal solutions.
24 October 2023
We continue our article series looking at a common modelling issue: The solution is optimal, but not practical.
In the previous article, we identified a theoretically perfect solution that is impractical to implement due to its complexity. We then developed a non-linear model of the situation, limited to just a few stock product sizes, but that model was difficult to solve.
In this article, we formulate and implement a linear model, with the hope that it will be easier to solve. We focus on considering only a partial set of potential solutions, as a step towards a full linear model.
10 October 2023
We address a common modelling issue: The solution is optimal, but not practical.
In our situation, the stated objective is to minimize trim waste in our paper manufacturing process. This is a type of coverage optimization problem. There is a theoretically perfect solution, with zero waste, but it is impractical to implement due to its complexity.
So, in reality, we have two intertwined objectives that we need to satisfy:
- Quantitative: Minimize trim waste in our manufacturing process.
- Qualitative: Make the solution simple and practical.
We can model the quantitative objective, but the qualitative objective has at least equal importance. Having an optimal, but impractical, solution is common in real-world optimization problems. The conflict between perfect and practical makes our situation both challenging and interesting.
In this series of articles, we use a variety of techniques to create several models. Along the way, we address the trade-off between our quantitative and qualitative objectives, enabling the decision maker to make an informed decision to implement an efficient and practical solution.
8 September 2023
Microsoft recently announced a new Excel feature, Python embedded within Excel. This is great news, as it combines our two favourite tools: Excel and Python. Since our focus is on optimization modelling, we immediately wondered if it is possible to use a Python library to solve optimization models directly within Excel. Spoiler alert, it is!
In this article, we experiment with building and solving a linear program in Excel using the Python SciPy library. Specifically, we replicate the Production Mix model that we previously solved using SciPy as part of our Rosetta Stone series of articles that looked at various Python optimization tools.
23 August 2023
This is the third, and final, article in our series looking at improving the efficiency of a picking warehouse.
In the previous article, we assessed a variety of layout designs for our warehouse. That analysis answered our first modelling question, "Would a different rack/shelf layout design improve efficiency?", by identifying a layout that is 33% more efficient than the current design.
In this article, we extend the analysis to answer our other two modelling questions. That is, can the efficiency of the picking process be further improved by:
- Positioning items according to order probability?
- Combining orders?
7 August 2023
This is the second article in our series looking at improving the efficiency of a picking warehouse.
In the previous article, we described our Python model for calculating the efficiency of the warehouse layout. Efficiency is defined in terms of the average distance that the pickers travel to fulfil customer orders.
In this article, we'll apply that model to assessing alternative warehouse layout designs, seeking to improve efficiency relative to our current warehouse's design. We present only a selection of the many designs that we assessed.
Our focus isn't on the details of the model code – though the code and data are available to download for you to learn from and experiment with. Instead, we'll focus on describing application of the model to answering our three modelling questions:
- Would a different rack/shelf layout design improve efficiency?
- What is the effect of positioning items according to order probability?
- Is there benefit in combining orders?
This article answers the first question. The next article will answer the other two questions.
21 July 2023
In this article series we explore optimization of a "picking warehouse" – that is, a warehouse where we pick items off the shelves to fulfil a customer order. As a result, we improve the efficiency of our warehouse by a factor of three.
Specifically, we model the efficiency of:
- A variety of shelving layout designs.
- Positioning items on shelves according to order probability.
- Combining orders to achieve economies of scale.
Along the way, we assess many alternative warehouse designs, which requires solving more than a million shortest path problems (using Dijkstra's algorithm via the networkx library) and almost a million Travelling Salesman Problems (using the constraint solver in OR-Tools).
Unlike most of our blog articles, our focus isn't on the details of the model code – though the code and data are available to download. Instead, we focus on describing the steps we took to model the situation.
This first article describes and tests the main modelling setup. The subsequent articles will address our modelling questions.
