Here’s some of our tutorials on mathematical optimisation

Introduction to optimisation/linear programming in Python

About this tutorial

Optimisation is a critical part of our daily lives, whether we are aware of it or not. Everything from plane flight scheduling to profit maximisation to determining the best driving route to take utilises optimisation. Mathematical optimisation, specifically, gives us tools to determine the actual optimal solution to a situation, as opposed to other ‘solutions’ seen in consulting applications, such as relying on sector or domain expertise. One type of mathematical optimisation, called ‘linear programming’ is particularly useful and serves as a good entry point into the field.

This tutorial is an introduction to mathematical optimisation/linear programming in Python. The tutorial is centred around a realistic consulting scenario of minimising costs, specifically, staffing costs, for a hospital. Linear programming is especially useful for this case, as the government outlines many activity-based funding guidelines and minimum criteria that a hospital must meet. These can be thought of as ‘constraints’ - a feature which governs the use of linear programming.

If you would like the source code in a complete file, please visit the GitHub repository for this tutorial.

Step 1: Load libraries

We are going to use two libraries - PuLP and Plotly (but two different features of Plotly) for this tutorial. PuLP is for linear programming and Plotly is for interactive plotting (as we will graph our optimised cost outputs). If you have not got these libraries installed, here is a great tutorial on installing them using a wonderful application called Anaconda.

import pulp as p
import plotly.graph_objects as go
import plotly.io as pio

Step 2: Establish optimisation environment and define variables

The first step after loading libraries is to tell Python we want to run a linear programming/optimisation problem. Importantly, we need to say whether we are trying to maximise or minimise the function we will define later. Next, we need to define the variables that we will be solving in the function. For this example, we want to know the appropriate number of units for different staffing areas of the hospital. Namely:

  • Medical staff
  • Nursing staff
  • Administrative staff
  • Cleaning staff

Therefore, we are going to specify these variables and initialise them into the problem environment. Additionally, we can set some initial individual variable bounds here. Let's assume there is a policy mandated by the government which requires hospitals to have a minimum of 5,000 units in each staffing area. We can set this as a lower bound here.

hosp_prob = p.LpProblem('Problem', p.LpMinimize)

the_lowBound = 5000

x = p.LpVariable("x", lowBound = the_lowBound)
y = p.LpVariable("y", lowBound = the_lowBound)
z = p.LpVariable("z", lowBound = the_lowBound)
a = p.LpVariable("a", lowBound = the_lowBound)

Step 3: Define constants and Objective Function to be minimised

As you are aware, pay is highly stratified in a hospital, with doctors typically being paid the most, followed by nurses, admin and cleaners. Of course there are many more types of staff, but for this introduction we will use these four. Since they have different pay structures, their cost-per-unit is different. These can be defined as constants to multiply by the number of units.

med_cost = 6175
nurs_cost = 3980
admin_cost = 2935
clean_cost = 2060

Now we are at the crux of linear programming. We have set up all the variables and necessary constants, so we can now define what’s called the ‘Objective Function.’ This is mathematical terminology for the function or equation we want to optimise the output value of. Essentially, the output number of this function will be the minimised staffing costs for the hospital in dollars.

hosp_prob += x*med_cost + y*nurs_cost + z*admin_cost + a*clean_cost

Step 4: Define constraints

Since we have defined our objective function, we can now define the constraints that govern the problem. Without these, our function would just go to the lower bounds for each variable we specified above. We have a set of four constraints which are explained in words below:

  1. Two times cleaning units plus two times admin must be less than or equal to the number of medical units
  2. One-and-a-half times the number of medical units must be less than or equal to the number of nursing units
  3. Two times the number of cleaning units must be less than or equal to the number of admin units
  4. The sum of all units (medical, nursing, admin, cleaning) must be greater than or equal to fifty thousand - assume this is a government requirement
hosp_prob += 2*z + 2*a <= x
hosp_prob += x*1.5 <= y
hosp_prob += 2*z <= a
hosp_prob += x + y + z + a >= 50000

Step 5: Print output and run the algorithm

We have now successfully defined everything we need to! We can now tell Python to solve the problem, print a summary of the variables and constraints, and print the final output at the bottom. The final output provides the optimised values for medical units, nursing units, admin units, cleaning units, and the overall minimised cost.

print(hosp_prob)

status = hosp_prob.solve()
print(p.LpStatus[status])

print(p.value(x), p.value(y), p.value(z), p.value(a),
p.value(hosp_prob.objective))

Step 6: Graph output (optional)

We have successfully produced an optimal solution! While numbers are fantastic, it is often the case that clients benefit more from visualisations than just numbers. The code below produces a simple waterfall chart with each staffing area's total cost (cost times units) portrayed visually as building up to the overall output cost.This helps provide a proportionate sense of scale. Graphing is not the goal of this tutorial so it won’t be explained too much, but a standalone graphing tutorial will follow this one soon.

fig = go.Figure(go.Waterfall(
    name = "20", orientation = "v",
    measure = ['relative', 'relative', 'relative', 'relative', 'total'],
    x = ['Medical Staff', 'Nursing Staff', 'Admin Staff', 'Cleaning Staff', 'Total Cost'],
    textposition = "outside",
    text = [(p.value(x)*med_cost), (p.value(y)*nurs_cost),
    (p.value(z)*admin_cost), (p.value(a)*clean_cost),
    p.value(hosp_prob.objective)],
    y = [(p.value(x)*med_cost), (p.value(y)*nurs_cost),
    (p.value(z)*admin_cost), (p.value(a)*clean_cost),
    p.value(hosp_prob.objective)],
    connector = {"line":{"color":"rgb(63, 63, 63)"}},
))

fig.update_layout(
        title = "Optimised hospital staffing expenditure",
        xaxis_title = "",
        yaxis_title = "Cost",
        showlegend = False
)

fig.show()