What is an ILP (Integer Linear Program)
Introduction
ILP stands for integer linear program. ILP are special way of stating an optimization problem for an ILP solver to solve. ILP are formulated such that there are a certain number of variables defined, there is an objective function that we want to maximize or minimize and there are linear constrains to the variables.
What does the objective function usually look like?
The objective function, given a set of variables \(x_i\) can be defined as: $$ Maximize \quad a x_1 + b x_2 + c x_3 + d x_4 \quad … $$
Example of valid objective functions
- \(Maximize \quad 2 x_1 + 3 x_2\)
- \(Minimize \quad x + y + z\)
- \(Minimize \quad \frac{2}{3} y_1 + 2^\pi y_2\)
\(Maximize \quad 0\) (might want to do this if you are interested only on finding a case where the constrains are satisfied)
Example of non valid objective functions
\(Maximize \quad x^2 + 3 y\) (variable cannot be raised to a power)
\(Minimize \quad x_1x_2 + x_3\) (variables cannot be multiplied between each other)
\(Minimize \quad sin(y)\) (cannot take any function of the variable)
What does a linear constrain look like?
Linear constrains, given a set of variable \(x_i\) and a constant \(\Kappa\), have the form of: $$ a x_1 + b x_2 + c x_3 + d x_4 \quad … \ge \Kappa $$
Example of valid constrains
- \(2 x_1 + 3 x_2 \ge 10 x_3 + x_4 \)
- \(y \le 6 \)
Example of a linear program (Not ILP yet 😉)
Let’s say you are following a diet. Let’s say, for the day, you are not allowed to eat more than 2000 calories, but you have to eat 75 calories in proteins and 1000 calories in carbohydrates.
| maximum calories | minimum protein | minimum carbohydrates |
|---|---|---|
| 2000 | 75 | 1000 |
Let’s say the available dishes you can eat 🥩, 🌮, 🍔 and 🍝. Each dish, gives this amount of calories, proteins, carbohydrates and an overall satisfaction.
| dish | calories | proteins | carbohydrates | satisfaction |
|---|---|---|---|---|
| 🥩 | 270 | 270 | 0 | 100 |
| 🌮 | 200 | 130 | 70 | 90 |
| 🍔 | 300 | 120 | 180 | 110 |
| 🍝 | 131 | 10 | 120 | 40 |
We want to maximize the overall satisfaction eating, without exceeding the allowed 2000 calories, but still satisfying the amount of proteins and the amount of carbohydrates.
LP (linear program) formulation
want to maximize satisfaction
\(Maximize \quad 100\times🥩 + 90\times🌮 + 110\times🍔 + 40\times🍝\)
the calories must be less than 2000
\(270\times🥩 + 200\times🌮 + 300\times🍔 + 131\times🍝 \le 2000\)
the proteins must be more than 75
\(270\times🥩 + 130\times🌮 + 120\times🍔 + 180\times🍝 \ge 75\)
the carbohydrates must be more than 1000
\(0\times🥩 + 70\times🌮 + 180\times🍔 + 120\times🍝 \ge 1000\)
Might be obvious, but in an LP we have to specify the following
\(🥩 \ge 0 \)
\(🌮 \ge 0 \)
\(🍔 \ge 0 \)
\(🍝 \ge 0 \)
LP solution
Usually, when we formulated the LP problem, we can solve it with an LP solvers. I personally use Guroby, but there are many LP solvers out there that you can try.
Let’s try to feed the problem to a LP solver.
You can try it yourself in this link.
Solving…
It gives us the following solution:
\(🥩=0\)
\(🌮=7.35\)
\(🍔=0\)
\(🍝=4.05\)
\(satisfaction=823.33\)
ILP
You can note from the solution of the LP, that the solution is not an integer. ILP solves that!!! You can specify which variable you want to be an integer.
Let’s rewrite the previous LP and make the variables integers.
\(Maximize \quad 100\times🥩 + 90\times🌮 + 110\times🍔 + 40\times🍝\)
\(270\times🥩 + 200\times🌮 + 300\times🍔 + 131\times🍝 \le 2000\)
\(270\times🥩 + 130\times🌮 + 120\times🍔 + 180\times🍝 \ge 75\)
\(0\times🥩 + 70\times🌮 + 180\times🍔 + 120\times🍝 \ge 1000\)
\(🥩 \ge 0 \)
\(🌮 \ge 0 \)
\(🍔 \ge 0 \)
\(🍝 \ge 0 \)
\(🥩 \in \Zeta\)
\(🌮 \in \Zeta\)
\(🍔 \in \Zeta\)
\(🍝 \in \Zeta\)
Solving…
It gives us the following solution:
\(🥩=0\)
\(🌮=4\)
\(🍔=4\)
\(🍝=0\)
\(satisfaction=800\)
Still don’t get what ILP are used for?
What kind of problem are ILP for?
Generally speaking, a lot of Graph Theory problems can be solved with an ILP formulation.
Some of the example of a Graph Theory problem that can be solved with an ILP formulation are:
- Graph Coloring
- Clique Problem
- The Traveling Sales
And those problem are respectively an abstraction of the following, more practical problems:
- Given a series of classes and the subscription of students to the classes, schedule the classes to minimize the span of time that the classes are given, such that no student will have overlapping classes.
- Given a number of people and knowing which person likes which other person, find the biggest group of people that would like each other.
Given a pub crawl, find the order of the pub to visit, such that the the distance traveled is minimized.
Why not using a backtracking or brute force algorithm?
There are multiple reasons why you would prefer to formulate the problem as a ILP.
Generally, it is easier and more concise to formulate a problem as an ILP instead of needing to develop the backtracking or brute force algorithm.
It is easier to explain why an ILP is formulated the way it is. If bare code had to be explained, it would be harder.
The ILP formulation is always going to be reproducible. If a backtracking or brute force algorithm were to be written, you have to make sure that the programming language and the libraries you use are: fast, concise, cross platform, and will not change usage or internal mechanics in the future.
The ILP uses heuristics and pruning mechanics that would be too hard to be programed in a case by case scenario.
Conclusion
ILP is a very powerful and versatile tool.
I hope you understood how to use them, and how they work. This blog page was mainly done as an introduction to ILP that I can reference in future posts where I might talk about ILP.