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.
22 June 2023
In this article we develop an optimization model in the Julia programming language, using the JuMP mathematical optimization package.
The focus is on introducing Julia/JuMP, by replicating the Production Mix model that formed the basis of our article series looking at several Python optimization libraries.
Our objectives are to:
- Write a linear programming model using Julia/JuMP.
- Compare the model with an equivalent model written using Python/Pyomo.
Although Julia/JuMP is not yet widely used outside universities, we expect that it will become an important tool for optimization modelling over the next few years.
26 May 2023
We often need to explore variations of a model. We might need to change model parameters, add/remove constraints, or change the objective function. These variations help us understand how different formulations or parameters affect the optimal solution.
In this article we explore two aspects of working with multiple variations of an optimization model:
- Modularization. We refactor an existing model into modules, consisting of functions located in separate files.
- Adding models. We extend the existing model by adding variations that make efficient use of the modular structure.
Along the way, we look at shallow vs deep copying in Python. This is a topic that often causes subtle bugs, so it is important to understand when working with variations of a model.
Our starting point is an existing model, created by Alireza Soroudi as part of his wonderful Optimization in open-source newsletter on LinkedIn. The specific model is Optimal advisor-advisee matching, used with the kind permission of Dr. Soroudi.
28 April 2023
Price breaks, or volume discounts, are common when buying products in bulk. That is, the marginal cost of additional products falls as volume increases. In a linear program, price breaks are tricky to model because the break points are non-linear discontinuities.
In a spreadsheet, a natural way to model price breaks is to use functions like IF, VLOOKUP, CHOOSE, MIN, and/or MAX. However, those functions are discontinuous, so we can't use the Simplex linear method in Solver. We also can't use the OpenSolver solvers at all when our model includes those functions. We could use Solver's GRG non-linear or Evolutionary methods, but they are not always reliable.
Fortunately, there is a way to express price breaks linearly, by using some binary variables, as described in our article MIP formulations and linearizations.
In this article, we describe an example of how to represent price breaks in a linear programming model, built in Excel using Solver or OpenSolver.
3 April 2023
In the previous article, we built a staff scheduling optimization model in Excel, using OpenSolver. That model enumerates all possible shift patterns and then decides how many of each shift pattern to use so that we meet the various constraints at least cost.
Our focus in this article is on replicating the Excel model by translating it into Python, using the Pyomo library. That involves formalizing the mathematical formulation, creating appropriate data structures, and representing the formulation in Pyomo syntax. Both models use the CBC solver, so the differences between the models aren't in the solving process, but rather in the build process.
Excel can be a great tool for some types of optimization modelling, either for prototyping or as a production tool. Python offers a wider range of optimization options, and it is usually better for models that have varying data sizes or need to operate at a large scale. The advantages and disadvantages of modelling in Excel and Python are discussed in more detail in our article Optimization in Excel vs Python.
27 March 2023
A common application of optimization modelling is the scheduling of staff to meet demand. Scheduling problems can be difficult to solve, as there are often very specific requirements that need to be met, including staff availability, working hours, break times, etc.
One approach for formulating scheduling problems is to enumerate all possible shift patterns and then decide how many of each shift pattern to use so that we meet the various constraints at least cost.
Enumeration of all possible shift patterns is often not as difficult as it may sound. We used a similar technique in the model Green manufacturing via cutting patterns. In that situation, there were potentially thousands of possible patterns, requiring an automated process to generate them all. In the staff scheduling situation there is usually a much smaller number of possible patterns, so manual enumeration is often possible.
This article implements a staff scheduling model in Excel and solves it using the CBC solver via OpenSolver. The next article implements the same model in Python, solves it using the CBC solver via Pyomo, then compares the Excel and Python model versions.
