Mixed Integer Linear Programming: Introduction | by István Módos

By Jessie Hobb On Jan 28, 2023

How to solve complex constrained optimisation problems having discrete variables

Designing and implementing algorithms for complex problems is hard. Fun, but hard. What if I told that you can solve certain optimisation problems using only their mathematical specification? Join me on the journey to the wonderful world of Mixed Integer Linear Programming, which has its applications in nurse rostering, kidney exchange programs, production scheduling, robotic cells energy optimisation, automated Sudoku solving, and many, many more! A common property of these problems is that they have discrete solution space. Usually, a solution space is also bounded by constraints so that only a subset of values represent valid solutions. Therefore, widely known AI optimisation algorithms (e.g. gradient descent) are not suitable for such problems.

Solution space for mixed integer linear program with its linear relaxation and optimal solution. The lines correspond to constraints, which encode the solution space. The filled blue dots represent feasible solutions, while the filled green one is the optimal solution.

In this series of posts, we will cover both practical modeling of discrete optimisation problems in Python and the behind-the-scenes theoretical machinery. The series is intended for practitioner programmers without deep background in computer science and for Machine Learning folks for whom Mixed Integer Linear Programming may be an alternative tool to their familiar data-driven methods. To be able to understand the content, PhD in rocket science is not necessary, although basic knowledge about math (matrix algebra) and programming in Python is assumed.

In this first introductory post, we will encounter a classical optimisation problem that we solve using Mixed Integer Linear Programming in Python.

Imagine that you are a manager of a company. The company has accumulated a hefty budget and you would like to invest it into various assets to maximise future profits. There are different kinds of assets, such as machinery or vehicles, each having a fixed cost and an estimated future profit if the asset is bought. The question you may ask is: which assets should you buy today to maximize the estimated future profit, so that you do not exceed the budget (assuming that you cannot buy a part of an asset)?

As a smart programmer, you figure out a straightforward, greedy algorithm: sort the assets decreasingly according to their estimated future profit per unit cost (i.e., divide the profit of each asset by its fixed cost) and buy the assets along this ordered list until you run out of budget. Easy, although there is no guarantee that the assets selected in this way are the ones that maximize the total future profit. How much are you losing? Naturally, you might be wondering what is the optimal selection of assets you can buy so that no other group would yield a higher profit.

So you decide to implement a more sophisticated heuristic algorithm, for example, based on genetic algorithms. After days of writing and debugging code, you come up with an algorithm having decent performance and the solutions obtained by it will have higher profit than those constructed from the greedy algorithm. But what happens if the problem requirements change, for example, some assets cannot be bought together? You would have to go back to coding and debugging. And the cycle repeats…

Development effort versus solution quality (e.g., profit): it takes a little effort to get from very bad solution to so-so one, but improving a high-quality solution takes more effort.

Mixed Integer Linear Programming addresses this problem. Instead of programming an algorithm, you describe your problem in a compatible mathematical language. Once the problem is mathematically formalized, you pass it to an off-the-shelf Mixed Integer Linear Programming solver library to obtain the solution. And since these solvers are written by very smart people with a heavy mathematical background, it is quite possible that you will get a better solution than what would you get from your hand-crafted algorithm. And if the problem requirements change, you just modify the problem description and then re-run the same solver. Sounds too good to be true, right? So lets look into it.

Mixed Integer Linear Programming (MILP for short) is called linear for a reason. And that is: the mathematical description of a problem is nothing else than a bunch of linear inequalities and linear expressions. For example, linear inequality

with variables x₁, x₂ and fixed parameters a₁, a₂, b₁ are one of such beasts that appear in MILP formulations. On the other hand,

is not a valid formulation within MILP, since there is quadratic term x₁x₂.

So we know that MILP consists of linear inequalities that somehow encode the problem at hand: we call these inequalities constraints. Given the fixed parameters, the MILP solver will try to plug values into variables so that the constraints are satisfied. The variable values that satisfy the constraints are collectively called a feasible solution. However, MILP goes far beyond finding any solution that satisfies the constraints. We may seek a feasible solution that optimizes an objective, which is a linear function of the variables: optimization is finding a best feasible solution in term of the objective value.

The variables in MILP can be either rational, integer, or binary (which are in fact integers but constrained either to 0 or 1); that is why there is mixed in the name. If all the variables in a formulation are rational, we get Linear Programming, which has nice computational properties (but more on that in an another post).

To put this into perspective of our budgeting problem, lets formalize it. First, think about the fixed parameters. Assume that there are 𝑛≥1 different assets that can be chosen. Each asset i∈{0,1,2,…,𝑛-1} have fixed cost 𝑐ᵢ and estimated future profit pᵢ. Finally, we are also given the budget 𝐵 which can be spent on the assets.

Now, think about the solution. An asset 𝑖 can be bought or not and it should be the job of the MILP solver to decide whether asset 𝑖 is bought. So we will have a binary variable 𝑥ᵢ for each asset 𝑖, which will be 1 if asset 𝑖 is bought and 0 if it is not. The interpretation of the variable values in the model is determined by us and this interpretation then dictates how the rest of the problem formalization should look like.

What are the constraints in our problem? We have only one and that is, the total cost of the bought assets in the solution cannot exceed the budget. We can write this using inequality

The interpretation of this constraint is the following: if asset 𝑖 is not bought, then its cost 𝑐ᵢ will not be included in the total cost (the left hand side of the inequality), since 𝑐ᵢ𝑥ᵢ=𝑐ᵢ0=0. On the other hand, if asset 𝑖 is bought, then its cost is included in the total cost.

Finally, we specify our objective, which is the maximization of the estimated total profit obtained from the bought assets

And there you have it, your first MILP formulation!

Once you have your MILP formulation, you can pass it to an existing MILP solver to obtain a solution. Nowadays, there a few commercial and even open-source MILP solvers and I will cover their differences in some future post. For now I will use Python package Python-MIP, which bundles the CBC open source solver. You can install it from PyPi with the following command (there are pre-built packages for Windows, MacOS and Linux)

pip3 install mip --user

Note for Mac M1 users: you might need to do some extra steps.

After that, fire your favorite code editor and start writing!

MILP solution
Solver status: OptimizationStatus.OPTIMAL
Bought assets: [3, 4]
Total cost of the bought assets: 10
Estimated future profit: 180

Here we created a problem instance with 5 assets to choose from. After solving the MILP model, we obtained an optimal solution with estimated future profit of 180. In comparison, the greedy algorithm would give us a smaller profit of 160.

Greedy algorithm solution
Bought assets: [0]
Total cost of the bought assets: 8
Estimated future profit: 160

It might seem that 180–160=20 is a small profit difference, but consider that the profit is in millions of dollars, then it starts to be interesting, doesn’t it? Also notice that asset 𝑖=0 with the highest profit to cost ratio was not selected in the MILP solution (there is a better combination of assets leading to higher profit).

By the way, how would we incorporate the additional requirement that two assets 𝑖,𝑗 cannot be bought together? By including additional constraint

m += x[i]+x[j] <= 1

in the model. You can check that this constraint is violated only in the case when both 𝑖,𝑗 are bought together, because then the left hand side is 2, which is obviously larger than 1. And thats it, only a single line of code and you were able to accommodate an additional requirement on the problem. Phew.

In this first introductory post we briefly talked about what is Mixed Integer Linear Programming (MILP) and why it is useful. It allows us to solve optimization problems without having to write algorithms. Instead, we write the problem description in a mathematical formulation, which is then solved by one of many available MILP solvers. In comparison to Machine Learning methods, solving MILP is not data-driven, as it leverages theoretical foundations of combinatorial optimization. We explored a simple optimization problem of buying assets and modeled it in Python (BTW: the problem is actually called Knapsack Problem!).

In the next post, I would like to define more formally what MILP is, how its solution space looks like and what is the computational complexity (MILP is a powerful tool, but it has its limits).

All images unless otherwise noted are by the author.