在整数线性规划中使用最小/最大值

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 denotes the costs vector, represent the coefficient matrix, and 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 hours a week. Rob earns $ at job and $ at job . Rob wants to maximize his earnings.

Let $y_{a}$ be the number of hours worked on the job and $y_{b}$ the number of hours worked on the job . The number of hours must be positive and rounded. So the objective function 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 gr proteins and gr cholesterol. Tofu contains gr proteins and gr 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 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 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 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.

Persistence

REST

Security

1. Overview

2. Introduction to Integer Linear Programming (ILP)

3. Example of ILP with Maximization

4. Example of ILP with Minimization

5. Maximin ILP

6. Minimax ILP

7. Conclusion