If you have a few years of experience in Computer Science or research, and you’re interested in sharing that experience with the community, have a look at our **Contribution Guidelines**.

# Using Min/Max Within an Integer Linear Program

Last modified: January 18, 2021

## 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:

Here represents the decision variables, are the costs, denotes coefficients, and denotes the requirements.

This same can also be expressed in matrix form:

Here denotes the costs vector, represent the coefficient matrix, and is the requirements vector and .

## 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 be the number of hours worked on the job and 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:**

## 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 ****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:

Here denotes the number of days Alex eats pasta, and 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 for
- Constants for and
- Constants for

The maximin objective function can be defined as:

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

and so:

For example, **if we want to maximize the minimum of **** integers and the sum of those numbers must be **, we can formulate this problem as a maximin ILP problem:

**This maximin problem can be alternatively expressed by introducing an auxiliary variable ****:**

## 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:

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

and so:

**If we want to minimize the maximum of **** integers and the sum of those numbers must be **, we can formulate this problem as a minimax ILP problem:

**This maximin problem can be alternatively expressed by introducing an auxiliary variable ****:**

## 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.