15 July 2025
Following on from our previous article, Efficient jury empanelling: Respecting people's time, in this article we replicate the jury simulation model using the SimPy library.
SimPy is a process-based discrete-event simulation framework in Python. It is widely used for simulation of many and varied systems, especially those with queues, where time can be expressed in discrete steps.
Discrete-event simulation is often applied to the design, analysis, and improvement of complex systems such as factory production lines, transportation networks, and warehouses. A simulation model can help us identify critical components of a system and evaluate alternative designs, leading to improvements in performance and reductions in cost. That's exactly what we want to do.
Here we design and build Model 2, using SimPy to model the jury summoning process, with the goal of reducing the number of people needing to be summoned for jury service.
09 June 2025
Jury service is an important civic duty, providing a way for people to directly participate in upholding the law and contribute to their community. But the jury service process, like much of the justice system, is designed around the needs of the system rather than the needs of the people it serves.
This article is inspired by a recent experience of being summoned for jury service. The process involved almost 100 people who attended the Court to potentially serve on one of three juries for trials scheduled to begin that week. The jury assembly area was crowded, many potential jurors were apprehensive, and there was a lot of waiting.
People make their time available to the Court, foregoing work, time with family, etc. The selection process may take up to five days, potentially plus whatever time selected jurors spend participating in a trial. The Court does provide compensation, in the form of a daily payment and reimbursement of transportation expenses. But the payment is a very modest amount, more of a token than a reasonable payment for the time commitment.
During the long periods of waiting, in between the various formal Court processes, there was plenty of opportunity to ponder the question: "Surely there is a better way that doesn't require so many people?" To answer that question, in this article we describe a simulation model of the jury selection process. The goal is to explore how the needs of the justice system can be met while also respecting the time of people who report for jury service.
3 May 2025
'The Muffin Problem' is a recreational maths puzzle that is simple to state but hard to solve in general. For example:
You have 11 muffins and 6 students. You want to divide the muffins equally between the students, but no student wants a small piece. How should you slice the muffins to maximize the size of the smallest piece?
We're one muffin short of giving each student two whole muffins. An obvious solution is to give each student one whole muffin. Then slice 1/6 from each of the five remaining muffins, giving 5/6 muffin to five students and 5 x 1/6 muffin to the sixth student. Therefore, each student gets 1 + 5/6 muffins. In this solution, the smallest slice is 1/6 muffin. But is that the maximum size we can make the smallest slice?
Spoiler alert: it isn't. Have a go at working out a way to slice the muffins that maximizes the size of the smallest slice while giving each student an equal share of the total. Note that we assume each muffin is circular and they are sliced from the edge to the centre. In this small example, finding a good solution is straightforward. Finding an optimal solution is more difficult. In many cases, proving that a solution is optimal is very difficult.
In this article, we solve The Muffin Problem using a Mixed Integer Linear Program (MILP) for a range of combinations for the number of muffins and the number of students. A MILP is not the most efficient method for solving this problem, but it illustrates a way to approach many types of recreational maths puzzles. Along the way, we explore using fractions in a Python program, speed up the process by solving optimization model instances in parallel, include symmetry-breaking constraints and objective function bounds, and we eat a few muffins – purely for research purposes, of course.
3 April 2025
Most optimization models are linear for a very practical reason – linear models are easier to solve. Situations that involve non-linear relationships are often linearized, or approximated with linear relationships, for the same reason. But not all situations are easily linearized.
In this article, we explore a model for optimizing the layout of centre-pivot irrigation machines in a field. Our goal is to see if replacement of the existing worn-out machines would make purchase of a field a viable investment.
Pivot irrigators are commonly used by crop farmers to supplement natural rainfall. For example, large areas of the mid-west USA are covered with these machines, such as this part of Kansas. The machines are almost always arranged in a simple grid pattern, which is not an efficient design in terms of coverage.
Arranging pivot irrigators in a field is a type of circle packing problem, with a non-linear objective and non-linear constraints. Worse still, the model is non-convex. These characteristics make our optimization problem both difficult and interesting.
To solve our model, we try several free and commercial solvers. All fail to find good solutions, except in trivial cases. So we try another solver, MINLP-BB via NEOS Server, that finds locally optimal solutions with no guarantee of global optimality. But by using a multi-start technique, we improve our chances of finding a good, perhaps optimal, solution. Is that solution good enough to justify making an investment?
7 March 2025
Optimization modelling is often used to improve the efficiency of supply chains. Where there is vertical integration, an organziation can model and optimize each part of the chain that they control. But how can they coordinate efficiently with independent suppliers and contractors?
One approach is to incentivize behaviours via price signals. A byproduct of solving a linear programming model is a set of "dual values" that indicate the marginal value of constrained resources. For example, some wholesale electricity markets use a linear program to find the least-cost suppliers to meet demand given various constraints. The model's dual values are used as prices for buying and selling of electricity and related services. If the prices are calculated depending on geographic location, then they are called Locational Marginal Prices (LMP) – indicating how the value of electricity varies by location.
In this article, we apply Locational Marginal Pricing to the supply of potatoes to fast-food restaurants. The current supply chain has several issues, including high costs, limited supplier capacity, transportation constraints, and a high spoilage rate during transportation. We want to give the independent suppliers and contractors price signals that incentivize more efficient behaviour, thereby reducing costs for our restaurants and improving the efficiency of the system. We describe the optimization model and calculation of the LMPs. We then explore several scenarios for how the suppliers and contractors may respond to the LMP signals.
8 February 2025
Role mining is a technique for finding a minimal set of roles that map users to access permissions.
A typical application of role mining starts with mapping IT access permissions for many users to many folders. The objective is then to create the fewest roles possible that cover the existing access permissions for all users. Variations may allow permissions to be added or removed.
Role mining is a hard problem to solve. The academic literature describes several mathematical programming formulations, which perform OK for very small data sets but don't perform well for larger data sets. Consequently, most of the literature is focussed on using heuristics to find approximate solutions for larger role mining problems.
In this article, we implement a recently published role mining model. The paper's authors claim that their new model formulation is both tractable and practical, allowing real world data sets to be solved in a reasonable amount of time. Like the authors of that paper, we build both constraint programming (CP) and mixed integer linear programming (MILP) models, then compare their relative performance while solving several examples.
7 January 2025
https://en.wikipedia.org/wiki/AryabhataIn this article we solve a non-linear curve fitting problem using the SciPy library. SciPy is especially well-suiting to solving this type of problem, as it includes a variety of functions for fitting and optimizing non-linear functions.
Along the way, we illustrate how to use SciPy's curve_fit and minimize functions for this type of task. In addition, we look at some good practices to apply when solving this type of problem, including:
- Using different criteria for defining the best fit, such as sum of squared differences and largest absolute error.
- Examining use of the
full_outputoption when using thecurve_fitfunction, to get more information about the result. - Examining the
successandmessagevalues of theminimizefunction result to ensure that the solver converges correctly. - Trying a variety of
minimizesolution methods to see which one works best in our specific situation. - Fine-tuning the solution by changing the convergence tolerance.
4 December 2024
In this article we pursue an ambitious goal: Create an entire, non-trivial optimization model using Artificial Intelligence (AI).
Our approach mimics a user who is familiar with the situation, and has some experience with formulating optimization models, but is not familiar with implementing an optimization model in Python code. We want the AI to do all the coding for us.
It's not surprising that others precede us in pursuing this goal. For example:
We provide an overview of a system which uses artificial intelligence and database techniques to help a knowledgeable user formulate large linear programs. The system automates many of the tedious processes associated with large-scale modeling […]
Initially, the system will be most suitable for expert users; eventually we hope that it will become intelligent enough to help managers or students with a minimal exposure to linear programming techniques.
"An intelligent system for formulating linear programs", Murphy & Stohr
What may be surprising is that Murphy & Stohr's article was published in 1985, almost 40 years ago. The AI tool they used, a Prolog rules-based expert system, is very different to the Large Language Model (LLM) AI tools currently in vogue. Murphy & Stohr report some success in using their AI system, though their approach did not become commonly used. Nonetheless, their goal then was much the same as it is for us now.
We report our experience of using Copilot to write a model for us. Rather than presenting a verbatim transcript, which is very long, we focus on what went well and what didn't go well as the model evolves. We also summarize general lessons from the process.
14 November 2024
We replicate a model by Erwin Kalvelagen at Yet Another Math Programming Consultant (YAMPC), Sorting using a MIP model. Erwin explores the run time behaviour of the CPLEX, HiGHS, and Xpress solvers for this feasibility problem, using an objective function that has a constant value of zero.
Professor Paul Rubin explores the same model in Solver parameters matter, using the CPLEX and Xpress solvers, finding that small tweaks to the solver options can have large impacts on relative solver performance.
In this article, we assess the impact of using an alternative objective function in the same model. The idea is to give the HiGHS solver greater traction while working through the solution space, hopefully helping it to solve the model faster. We've found this technique to be useful for some other models – will it help in this situation?
26 October 2024
https://www.researchgate.net/publication/357386257_Imposing_Contiguity_Constraints_in_Political_Districting_ModelsOur previous article implores academic researchers to publish data and code to accompany their papers. We use an example where academic publishing has been done well: with papers about creating voting districts accompanied by data and models available on Github.
On a related topic, Alireza Soroudi has published an article on LinkedIn describing a Gerrymandering using Constraint Programming model. Dr. Soroudi's model has the specific objective of showing how electoral district boundaries can be manipulated to advantage a party, group, or socioeconomic class within the constituency. As Dr. Soroudi says:
Gerrymandering – the crafty art of redrawing electoral districts to tip the scales in favor of a particular party – is as intriguing as it is controversial.
In this article, we take a simple approach to modifying a redistricting model. We add a requirement to our model that could be interpreted as either:
- The laudable goal of grouping together "communities of interest" – a common requirement when designing voting districts; or
- A nefarious attempt to manipulate the electoral outcome by gerrymandering.
Gerrymandering is the opposite of the model's purpose in our previous article. But, as model designers, we need to be aware that we don't always control the purposes to which decision makers apply our models and decision makers don't always understand the implications of small changes to a model.