In this article we will discuss how to solve linear programming problems with Gurobipy in Python.

Table of Contents

Introduction

Linear programming (LP) is a tool to solve optimization problems. It is widely used to solve optimization problems in many industries.

In this tutorial we will be working with gurobipy library, which is a Gurobi Python interface. Gurobi is one of the most powerful and fastest optimization solvers and the company constantly releases new features. You can learn more about their licenses here.

To continue following this tutorial we will need the following Python library: gurobipy.

If you don’t have it installed, please open “Command Prompt” (on Windows) and install it using the following code:


python -m pip install -i https://pypi.gurobi.com gurobipy

Note: gurobipy includes a limited license to get started with the library and solve some sample optimization problems. If you are planning on solving more complex problems, you will need to get a license.

Linear programming example

Linear programming is much easier to understand once we have an example of such an optimization problem.

Consider a manufacturing company which produces two items: cups and plates. Here is what we know:

  • Once made, a cup sells for $27 and a plate sells for $21.
  • To make each cup it costs $10 in materials and $14 in labour.
  • To make each plate it costs $9 in materials and $10 in labour.
  • To make each cup, it takes 2.2 hours of labour.
  • To make each plate, it takes 1 hour of labour.
  • A firm has unlimited supply of raw materials.
  • Due to the limited number of workers, a company has maximum of 100 labour hours.
  • Demand for cups is unlimited, but demand for plates is 30 units.

The company’s goal is to maximize profits (revenue – cost).

How to solve linear programming problem

Below are the steps we need to solve this linear programming problem:

Step 1: Define the decision variables

In any linear programming problem we need to correctly identify the decision variables. What are they? Decision variables are variables that represent a decision made in the problem.

In our case, a company needs to decide how many cups and plates it will produce (the decision). So we define our decision variables as:

$$ x_1 = \textit{number of cups to produce} $$

$$ x_2 = \textit{number of plates to produce} $$

Step 2: Define the objective function

In any optimization problem we want to either maximize or minimize something. In our case, the company wants to maximize profits, therefore our objective function will be a profit maximization.

Recall that our selling price for each cup is $27 and selling price for each plate is $21. We can write the revenue function as:

$$ \textit{Revenue} = 27x_1 + 21x_2 $$

The next part is to define our cost function. We have two parts to it: raw materials and labour.

Recall that for raw materials it costs $10 per cup and $9 per plate:

$$ \textit{Raw materials} = 10x_1 + 9x_2 $$

And for labour it costs $14 per cup and $10 per plate:

$$ \textit{Labour} = 14x_1 + 10x_2 $$

With the above, we can solve for the profit function as:

$$ \textit{Profit} = (27x_1 + 21x_2 )-(10x_1 + 9x_2)-(14x_1 + 10x_2) = 3x_1 + 2x_2$$

And our objective function becomes:

$$ \textit{max z} = 3x_1 + 2x_2$$

Step 3: Define the constraints

First constraint would be the labour hours. We know that each cup takes 2 labour hours and each plate takes 1 labour hour. There is also a maximum of 100 labour hours available:

$$ \textit{Constraint 1: } 2.2x_1 + x_2 \leq 100$$

Second constraint would be the demand for plates. We know that the demand for cups is unlimited, but demand for plates is 30 units:

$$ \textit{Constraint 2: } x_2 \leq 30$$

The last two constraints are the sign restrictions for decision variables. In our case, number of both cups and plates produced should be greater or equal to zero:

$$ \textit{Constraint 3: } x_1 \geq 0 $$

$$ \textit{Constraint 4: }x_2 \geq 0 $$

Solve linear programming problem using Python

Now we have the optimization problem formulated, we will need to solve it using gurobipy in Python.

We begin with importing the library:


from gurobipy import *

Next, we create a new empty model:


m = Model()

Now we can add the \(x_1\) and \(x_2\) variables to the model:


x1 = m.addVar(name="x1")
x2 = m.addVar(name="x2")

Note: we are adding variables without any specifications, allowing the optimal \(x_1\) and \(x_2\) be any continuous value.

Following the similar steps from the previous part, we add the objective function we created and set it as a maximization problem:


m.setObjective(3*x1 + 2*x2 , GRB.MAXIMIZE)

And add the constraints:


m.addConstr(2.2*x1 + x2  <= 100, "c1")
m.addConstr(x2  <= 30, "c3")
m.addConstr(x1  >= 0, "c4")
m.addConstr(x2  >= 0, "c5")

Finally, run the optimization:


m.optimize()

At this point our linear programming optimization is solved, and we can work on retrieving the results.

We begin with getting the optimal values for \(x_1\) and \(x_2\):


for v in m.getVars():
    print(v.varName, v.x)

And we get:

x1 31.818181
x2 30.0

To maximize profit, the company should produce 20 cups and 60 plates. What is the maximized profit?

We can get it from the optimized model:


print('Maximized profit:',  m.objVal)

And we get:

Maximized profit: 155.454545

In summary, the maximum profit a company can make is $155.45 while producing 31.82 cups and 30 plates.

Complete linear programming solver code in Python


from gurobipy import *

# Create a new model
m = Model()

# Create variables
x1 = m.addVar(name="x1")
x2 = m.addVar(name="x2")

# Set objective function
m.setObjective(3*x1 + 2*x2 , GRB.MAXIMIZE)

#Add constraints
m.addConstr(2.2*x1 + x2  <= 100, "c1")
m.addConstr(x2  <= 30, "c3")
m.addConstr(x1  >= 0, "c4")
m.addConstr(x2  >= 0, "c5")

# Optimize model
m.optimize()

#Print values for decision variables
for v in m.getVars():
    print(v.varName, v.x)

#Print maximized profit value
print('Maximized profit:',  m.objVal)

In reality, can the company produce 31.82 cups? Not really. What we need is some way of generating integers for the \(x_1\) and \(x_2\) decision variables.

Check out my article on how to solve integer programming problems with Python.

Conclusion

In this article we covered how you can solve a linear programming problem using Gurobi Python interface with gurobipy library.

Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Optimization articles.