1. Overview

In this tutorial, we’ll discuss Integer Linear Programming (ILP) in detail. We’ll also present the variations of ILP with examples.

2. Introduction to Integer Linear Programming (ILP)

Integer linear programming is a method of optimizing a linear cost function, and it should satisfy a variety of restrictions on linear equality and linear inequality. It’s an extension of linear programming, with an additional constraint, stating that all variables should be integers. Let’s define an ILP problem mathematically:

    [\mbox{maximize/minimize } c_{1}y_{1} + c_{2}y_{2} + ... + c_{n}y_{n}]

    [\mbox{Subject to: \\}]

    [b_{11}y_{1} + b_{12}y_{2} + ... + b_{1n}y_{n} \leq d_{1}]

    [b_{21}y_{1} + b_{22}y_{2} + ... + b_{2n}y_{n} \leq d_{2}]

    [:]

    [b_{m1}y_{1} + b_{m2}y_{2} + ... + b_{mn}y_{n} \leq d_{m}]

    [y_{i} \geq 0 \mbox{ for all } i= 1,2,...,n \mbox{ and } \forall  y_{i} \in {\displaystyle \mathbb {Z} }]

Here y_{i} represents the decision variables, c_{i} are the costs, b_{ij} denotes coefficients, and d_{i} denotes the requirements.

This same can also be expressed in matrix form:

    [\mbox{maximize/minimized } C^{T} Y]

    [\mbox{Subject to: \\}]

    [BY \leq D]

    [Y \geq 0]

Here C denotes the costs vector, B represent the coefficient matrix, and D is the requirements vector and Y \in {\displaystyle \mathbb{Z}}.

3. Example of ILP with Maximization

Let’s consider the case where Rob has two jobs, but he can’t work more than 16 hours a week. Rob earns 40$ at job A and 60$ at job B. Rob wants to maximize his earnings.

Let y_{a} be the number of hours worked on the job A and y_{b} the number of hours worked on the job B. The number of hours must be positive and rounded. So the objective function E would be the total earnings, and the maximum number of hours he can work is a constraint, along with the value of the hours.

Let’s formulate this as an ILP problem:

    [\mbox{maximize } E = 40y_{a} + 60y_{b}]

    [\mbox{Subject to: \\}]

    [y_{a} + y_{b} \leq 16]

    [y_{a}, y_{b} \in \mathbb{Z^{+}}]

4. Example of ILP with Minimization

Alex is on a low cholesterol diet. He needs to choose the number of days he eats tofu and pasta so that he minimizes his cholesterol intakes while having at least \mathbf{150}gr of proteins. Let’s consider pasta contains 8gr proteins and 60gr cholesterol. Tofu contains 16gr proteins and 50gr cholesterol. We can formulate this as an ILP problem:

    [\mbox{minimize } I = 60y_{p} + 50y_{t}]

    [\mbox{Subject to: \\}]

    [8y_{p} + 16y_{t} \geq 150]

    [y_{p}, y_{t} \in \mathbb{Z^{+}}]

Here y_{p} denotes the number of days Alex eats pasta, and y_{t} represents the number of days Alex eats tofu.

5. Maximin ILP

If the problem to be solved requires to maximize the minimum value of a number of decision variables, we can use maximin ILP. To represent the maximin objective mathematically we need to define variables and constants:

  • Decision variables y_{j} for j \in \{1,...,n\}
  • Constants b_{ij} for i \in \{1,...,m\} and j\in \{1,...,n\}
  • Constants d_i for i\in\{1, . . . ,m\}

The maximin objective function can be defined as:

    [\mbox{ maximize } min\{ \sum_{j=1}^{n} b_{1j} y_j + d_1 , \sum_{j=1}^{n} b_{2j} y_j + d_2 , ... , \sum_{j=1}^{n} b_{mj} y_j + d_m \}]

This model can be converted to a simple maximization ILP by adding auxiliary decision variable z so that:

    [z = min\{ \sum_{j=1}^{n} b_{1j} y_j + d_1 , \sum_{j=1}^{n} b_{2j} y_j + d_2 , ... , \sum_{j=1}^{n} b_{mj} y_j + d_m \}]

and so:

    [\mbox{maximize } z]

    [\mbox{Subject to:}]

    [z \leq \sum_{j=1}^{n} b_{ij} y_j + d_i \mbox{ for all i = 1,..,m}]

For example, if we want to maximize the minimum of \mathbf{3} integers and the sum of those numbers must be \mathbf{100}, we can formulate this problem as a maximin ILP problem:

    [\mbox{ maximize } min\{ y_{1}, y_{2}, y_{3}\}]

    [\mbox{Subject to: } y_{1} + y_{2} + y_{3} = 100]

This maximin problem can be alternatively expressed by introducing an auxiliary variable \mathbf{z}:

    [\mbox{maximize } z]

    [\mbox{Subject to:}]

    [y_{1} + y_{2} + y_{3} = 100]

    [z \leq y_{1}]

    [z \leq y_{2}]

    [z \leq y_{3}]

6. Minimax ILP

If the problem to be solved requires to minimize the maximum value of a number of decision variables, we can use minimax ILP. The minimax objective function can be defined as:

    [\mbox{ minimize } max\{ \sum_{j=1}^{n} b_{1j} y_j + d_1 , \sum_{j=1}^{n} b_{2j} y_j + d_2 , ... , \sum_{j=1}^{n} b_{mj} y_j + d_m \}]

Which is subject to some constraints. This model can be converted to a simple maximization by adding an auxiliary decision variable z so that:

    [z = max\{ \sum_{j=1}^{n} b_{1j} y_j + d_1 , \sum_{j=1}^{n} b_{2j} y_j + d_2 , ... , \sum_{j=1}^{n} b_{mj} y_j + d_m \}]

and so:

    [\mbox{minimize } z]

    [\mbox{Subject to:}]

    [z \geq \sum_{j=1}^{n} b_{ij} y_j + d_i \mbox{ for all i = 1,..,m}]

If we want to minimize the maximum of \mathbf{4} integers and the sum of those numbers must be \mathbf{120}, we can formulate this problem as a minimax ILP problem:

    [\mbox{ minimize } max\{ y_{1}, y_{2}, y_{3}, y_{4} \}]

    [\mbox{Subject to: } y_{1} + y_{2} + y_{3} + y_{4} = 120]

This maximin problem can be alternatively expressed by introducing an auxiliary variable \mathbf{z}:

    [\mbox{minimize } z]

    [\mbox{Subject to:}]

    [y_{1} + y_{2} + y_{3} + y_{4} = 120]

    [z \geq y_{1}]

    [z \geq y_{2}]

    [z \geq y_{3}]

    [z \geq y_{4}]

7. Conclusion

In this tutorial, we defined integer linear programming (ILP). We explained variations of ILP, including maximization, minimization, minimax, and maximin with practical examples.