Mixed Integer Programming with PuLP¶

Try me¶

Introduction¶

This tutorial shows how to program and solve Mixed Integer Programming (MIP) problems in Python using the PuLP library.

This tutorial builds upon the tutorial on PuLP we saw in the previous unit:

Requirements¶

To run this tutorial you will need to install PuLP, following the guides in the previous tutorial. For instance, if you are using this tutorial in Colabs, run the following cell to install PuLP:

[ ]:

# Install PuLP
!pip install pulp

Example¶

We will use the Allocating order to machines problem to guide the tutorial. For convenience, this is the mathematical formulation:

indices¶

i: index to identify each machine (resource element) \(i \in \{1,2,3,4,5\}\)
j: index to identify each production order (task element) \(j \in \{1,2,3,4,5\}\)

Coefficients¶

\(C = \begin{bmatrix} c_{11} & c_{12} & \cdots & c_{1n} \\ c_{21} & c_{22} & \cdots & c_{2n} \\ \vdots & \vdots & \ddots & \vdots \\ c_{m1} & c_{m2} & \cdots & c_{mn} \\ \end{bmatrix} = \begin{bmatrix} 16 & 2 & 8 & 3 & 3 \\ 4 & 14 & 10 & 7 & 6 \\ 9 & 7 & 3 & 6 & 8 \\ 5 & 5 & 12 & 10 & 11 \\ 6 & 13 & 11 & 5 & 7 \\ \end{bmatrix}\)

Objective function¶

\(\min z = \sum_i\sum_j{x_{ij}*c_{ij}}\)

Constraints¶

\(\sum_j{x_{ij}} \leq 1 \quad \forall i\)

\(\sum_i{x_{ij}} \leq 1 \quad \forall j\)

Solution in Python¶

The following script models and solves the problem using PuLP:

[2]:

# Import PuLP modeler functions
import pulp

# Create the model
model = pulp.LpProblem(name="Allocating orders to machines", sense=pulp.LpMinimize)

# Define indices
machines = [1, 2, 3, 4, 5]
orders = [1, 2, 3, 4, 5]

# Define decision variables
x = pulp.LpVariable.dicts("x",
                          [(i,j) for i in machines for j in orders],
                          cat=pulp.LpBinary,
                          )

# Define coefficient matrix
C = [[16, 2, 8, 3, 3],
     [4, 14, 10, 7, 6],
     [9, 7, 3, 6, 8],
     [5, 5, 12, 10, 11],
     [6, 13, 11, 5, 7]]

# Define objective function
model += pulp.lpSum([C[i][j]*x[(i+1,j+1)] for i in range(len(machines)) for j in range(len(orders))])

# Define constraints
for i in machines:
    model += pulp.lpSum([x[(i,j)] for j in orders]) == 1

for j in orders:
    model += pulp.lpSum([x[(i,j)] for i in machines]) == 1

# Solve the problem
model.solve()

# Print the status of the solution
print("Status:", pulp.LpStatus[model.status])

# Print the value of the objective function
print("Objective value:", pulp.value(model.objective))

# Print the value of the decision variables
for v in model.variables():
    print(v.name, "=", v.varValue)

Status: Optimal
Objective value: 20.0
x_(1,_1) = 0.0
x_(1,_2) = 0.0
x_(1,_3) = 0.0
x_(1,_4) = 0.0
x_(1,_5) = 1.0
x_(2,_1) = 1.0
x_(2,_2) = 0.0
x_(2,_3) = 0.0
x_(2,_4) = 0.0
x_(2,_5) = 0.0
x_(3,_1) = 0.0
x_(3,_2) = 0.0
x_(3,_3) = 1.0
x_(3,_4) = 0.0
x_(3,_5) = 0.0
x_(4,_1) = 0.0
x_(4,_2) = 1.0
x_(4,_3) = 0.0
x_(4,_4) = 0.0
x_(4,_5) = 0.0
x_(5,_1) = 0.0
x_(5,_2) = 0.0
x_(5,_3) = 0.0
x_(5,_4) = 1.0
x_(5,_5) = 0.0

C:\Users\franc\PycharmProjects\operations-research-notebooks\venv\Lib\site-packages\pulp\pulp.py:1316: UserWarning: Spaces are not permitted in the name. Converted to '_'
  warnings.warn("Spaces are not permitted in the name. Converted to '_'")

Code Explanation¶

The code is very similar to the efficient code we used in the previous tutorial. The only difference is in the way we define the decision variables. Let’s see the differences:

Decision variables¶

We use the same function pulp.LpVariable.dicts to define the decision variables. There are two main differences:

Definition or integer or binary decision variables: We use the parameter cat=pulp.LpBinary to define the decision variables as binary. If we wanted to define them as integer, we would use cat=pulp.LpInteger.
Definition of the indices: We use a list comprehension to define the indices of the decision variables. The list comprehension is a very powerful tool in Python that allows us to define lists in a very compact way. The list comprehension we use is the following:

[(i,j) for i in machines for j in orders]

This list comprehension defines a list of tuples, where each tuple is defined as (i,j), where i takes the values in the list machines and j takes the values in the list orders. This way we define all the possible combinations of i and j in a very compact way.

Thus, the code:

x = pulp.LpVariable.dicts("x",
                          [(i,j) for i in machines for j in orders],
                          cat=pulp.LpBinary,
                          )

Defines a total of 5x5 = 25 decision variables, one for each combination of i and j. The decision variables can be accessed using a tuple. For instance, x[(1,1)] is the decision variable associated with the combination i=1 and j=1.

Reading data from an Excel file¶

In the previous tutorial, we defined the coefficient matrix in the code. However, in real problems, the data is normally stored in a file. In this case, we will use an Excel file to store the data. We will see how to read the data from the Excel file and store it in a DataFrame. Then, we will see how to access the data in the DataFrame to define the coefficient matrix. The following code shows how to load the data from an Excel file named costs.xlsx:

[ ]:

import pandas as pd
import pulp
from IPython.display import display

# import the data from the Excel file
dataset_df = pd.read_excel("costs.xlsx", index_col=[0,1])
c = dataset_df['cost']

# Pivot the data to show it in a more convenient way
dataset_df = dataset_df.reset_index()
dataset_df = dataset_df.pivot(index='machine', columns='order', values='cost')
display(dataset_df)

# Create the model
model = pulp.LpProblem(name="Allocating orders to machines", sense=pulp.LpMinimize)

# Define indices
machines = [1, 2, 3, 4, 5]
orders = [1, 2, 3, 4, 5]

# Define decision variables
x = pulp.LpVariable.dicts("x",
                          [(i,j) for i in machines for j in orders],
                          cat=pulp.LpBinary,
                          )

# Define objective function

model += pulp.lpSum([c[i][j]*x[(i,j)] for i in machines for j in orders])

# Define constraints
for i in machines:
    model += pulp.lpSum([x[(i,j)] for j in orders]) == 1

for j in orders:
    model += pulp.lpSum([x[(i,j)] for i in machines]) == 1

# Solve the problem
model.solve()

# Print the status of the solution
print("Status:", pulp.LpStatus[model.status])


# Create a dataframe to store the solutions
x_df = pd.DataFrame.from_dict(x, orient="index", dtype=object, columns=["variable_object"])

# Extract the values of the decision variables from the solution
x_df["solution_value"] = x_df["variable_object"].apply(lambda item: item.varValue)

# Drop the pulp decision variables
x_df = x_df.drop(columns=["variable_object"])

# Pivot the dataframe to show the solution in a more convenient way
x_df = x_df.reset_index()

x_df['machine'] = x_df['index'].apply(lambda i: i[0])
x_df['order'] = x_df['index'].apply(lambda i: i[1])

# Drop the index column
x_df = x_df.drop(columns=["index"])

# Reorder the columns to show the solution in a more intuitive way
x_df = x_df[["machine", "order", "solution_value"]]

# Pivot the dataframe to show the solution in a more convenient way
x_df = x_df.pivot(index='machine', columns='order', values='solution_value')
display(x_df)

# Safe to an Excel file
with pd.ExcelWriter('solution.xlsx') as writer:
    x_df.to_excel(writer, sheet_name="X")

The following sections explain the code in detail.

Code Explanation¶

Preparing the dataset¶

Normally, the data for our problem is going to be stored in tabular format in file formats like Excel. In this case, we can use the pandas library to read the data from the Excel file and store it in a DataFrame. Then, we can use the DataFrame to access the data in a very convenient way. First, just copy the following table in an Excel file:

machine order   cost
 1   16
 2   2
 3   8
 4   3
 5   3
 1   4
 2   14
 3   10
 4   7
 5   6
 1   9
 2   7
 3   3
 4   6
 5   8
 1   5
 2   5
 3   12
 4   10
 5   11
 1   6
 2   13
 3   11
 4   5
 5   7

Make sure you paste the table in the first sheet of the Excel file as text. It should look like this:

Excel file

Important! If you notice that all the text of a raw is in the same sure, try to Past As text from the Edit menu in Excel.

Name the file costs.xlsx.

Uploading the dataset to your Python environment¶

Now, you need to make sure that the Excel file is in the working directory of your Python environment. If you are using Colabs, you can use the file menu to upload it as shown in this tutorial:

Working with files

Loading the dataset in a DataFrame¶

Now, we can use the pandas library to load the data in a DataFrame:

import pandas as pd
dataset_df = pd.read_excel("costs.xlsx", index_col=[0,1])
c = dataset_df['cost']

The index_col parameter indicates that the first two columns of the Excel file are the indices of the DataFrame.

Accessing the data in the DataFrame¶

Note that we have stored the costs in a variable named c. This is because we will use the DataFrame to access the data in a very convenient way. For instance, if we want to access the cost of machine 1 and order 1, we can use the following code:

print(c[1,1])

This will print the value of the cell in the first row and first column of the DataFrame, corresponding to machine 1 and production order 1.

Pivoting the DataFrame to show the data in a more convenient way¶

To show the data in a more convenient way, we can pivot the DataFrame:

dataset_df = dataset_df.reset_index()
dataset_df = dataset_df.pivot(index='machine', columns='order', values='cost')
display(dataset_df)

This will show the data in a very convenient way, environments like Colabs provide interactive widgets to further work with the data.

Defining the objective function¶

Now, we can modify the objective function slightly to access the data in the DataFrame:

model += pulp.lpSum([c[i][j]*x[(i,j)] for i in machines for j in orders])

Note that since the indices of c are the same as the indices of the decision variables, the code is very compact and close to mathematical notation.

Exporting to Excel¶

Finally, we can put the variables in a dataframe:

# Create a dataframe to store the solutions
x_df = pd.DataFrame.from_dict(x, orient="index", dtype=object, columns=["variable_object"])

# Extract the values of the decision variables from the solution
x_df["solution_value"] = x_df["variable_object"].apply(lambda item: item.varValue)

This code first creates a dataframe with the decision variables and then extracts the values of the decision variables using a lambda function. Pandas will apply the lambda function to each row of the dataframe, passing the decision variable object as a parameter. The lambda function will return the value of the decision variable.

Finally, we can pivot the dataframe and export it to excel using the following code:

with pd.ExcelWriter('solution.xlsx') as writer:
    x_df.to_excel(writer, sheet_name="X")

This code will create an Excel file named solution.xlsx with a sheet named X containing the solution. If our problem has more decision variables, we can create more sheets and store the solutions in different sheets.

Analysis Questions¶

Analyse the solution and explain the assignment of orders to machines that the model has found in your own words.
How would you modify the model to allow for the assignment of more than one order to each machine?
Use an AI assistant to obtain a Python script to solve the problem using PuLP. Compare the script with the one we have developed in this tutorial. What are the main differences?
Ask an AI assistant to provide a greedy algorithm to solve the problem in Python. Try the algorithm. Does the algorithm provide an optimal solution? Why?
Try to solve different instances of the problem, for instance adding more machines or more production orders. What changes are needed in the script. How can you make the script more scalable?