Introduction to Integer Linear Programming

Author

Your Name

Published

January 30, 2025

Introduction

This lecture provides an overview of Integer Linear Programming (ILP), a powerful optimization technique used to solve a wide range of real-world problems. We will explore the fundamental concepts of ILP, its relationship to Linear Programming (LP), and the challenges associated with solving ILP problems. The main objectives are to understand how to model optimization problems using ILP, to recognize the differences between LP and ILP, and to appreciate the computational complexity of ILP. Key concepts include variables, objective functions, constraints, and the distinction between polynomial and NP-hard problems.

Operations Research and Mathematical Programming

Operations research provides a rich and powerful theory for solving optimization problems of various natures. Mathematical programming is a specific type of optimization where variables are vectors of numbers, and functions are functions of these vectors. Problems with convex solution sets and convex or concave objective functions are particularly interesting because local optima are also global optima. Linear and quadratic functions, especially linear constraints, are of significant interest.

Integer Linear Programming (ILP)

Integer Linear Programming (ILP or PLI in Italian) is a significant contribution of operations research. It allows us to model and ultimately solve a large number of optimization problems of different natures. ILP is built upon linear programming, which was one of the first problems studied by operations researchers, particularly George Dantzig, who is considered the father of operations research. Dantzig developed the simplex method to solve linear programming problems, which, after 70 years, is still fundamentally the best way to solve them.

The Role of Solvers

For the next few lectures, we will treat the linear and integer linear programming solver as a black box. We will not go into the details of how a solver works but assume that a solver exists. We will provide input to the solver, and it will output the solution. Our task is to learn the language of modeling, to write models that serve as input for the solver.

Modeling Alternatives

When writing a model for a problem, there are always many alternatives. We have virtually infinite choices for variables, objective functions, and constraints. Some models will be better than others, just as there are virtually infinite algorithms to solve the same problem, some more efficient than others.

Definition 1 (Model Components). A model consists of three parts:

Variables: Decisions to be made to determine a solution.
Objective Function: How the cost of a solution is a function of these variables.
Constraints: Conditions that variables must satisfy to represent admissible solutions.

Linear Programming (LP)

Linear programming involves minimizing or maximizing a linear function of $n$ variables, subject to a set of linear constraints.

Definition 2 (Linear Programming). Linear programming is characterized by:

A cost vector $c \in \mathbb{R}^n$.
A constraint coefficient matrix $A \in \mathbb{R}^{m \times n}$.
A vector of constant terms $b \in \mathbb{R}^m$.

The problem can be formulated as: \[\begin{aligned} \text{Maximize or Minimize} \quad & \sum_{j=1}^{n} c_j x_j \\ \text{Subject to} \quad & \sum_{j=1}^{n} a_{ij} x_j \geq, =, \leq b_i, \quad i = 1, \dots, m \\ & x_j \geq 0, \quad j \in J \subseteq \{1, \dots, n\} \end{aligned}\]

Example 1. An example of a linear programming problem is: \[\begin{aligned} \text{Maximize} \quad & 4x_1 + 2x_2 + 3x_3 \\ \text{Subject to} \quad & 3x_1 + 2x_2 - x_3 \geq 5 \\ & 5x_1 - 3x_2 + x_3 \leq 2 \\ & -2x_2 + x_3 \geq 1 \\ & 2x_1 + 2x_2 - 3x_3 = 8 \\ & x_1, x_2, x_3 \geq 0 \end{aligned}\]

Non-negativity Constraints

Non-negativity constraints ($x_j \geq 0$) are often included and are usually written separately because they are common and do not characterize the problem well.

Integer Constraints

In many real-world problems, solutions must be integers. For example, you cannot hire a fraction of a person or build a fraction of a hospital.

Remark. Remark 1. Linear programming does not allow for imposing that variables must be integers. It might happen that the solution has integer components, but it cannot be enforced with linear inequalities.

Computational Complexity

Adding the constraint that variables must be integers makes the problem computationally difficult.

Linear programming without integer constraints is a polynomial problem. There are efficient algorithms to solve it in polynomial time relative to the instance size.
When integer constraints are added, the problem becomes NP-hard. There are no known polynomial-time algorithms to solve it, and it is likely that none exist if P $\neq$ NP.

Definition 3 (Integer Linear Programming (ILP)). Integer Linear Programming (ILP) is an extension of linear programming where some or all variables are required to be integers.

Theorem 1. ILP is NP-hard.

This theorem states that the Integer Linear Programming problem is NP-hard.

Conclusion

In this lecture, we introduced the concept of Integer Linear Programming (ILP) and its foundation in Linear Programming (LP). We discussed the components of a model, including variables, objective functions, and constraints, and highlighted the importance of writing efficient models. We also touched upon the computational complexity differences between LP, which is solvable in polynomial time, and ILP, which is NP-hard.

Key takeaways include the understanding that ILP is a powerful tool for solving optimization problems where integer solutions are required, but it comes with increased computational challenges compared to LP. The simplex method, developed by George Dantzig, remains a cornerstone in solving LP problems, and understanding LP is crucial for tackling ILP.

Follow-up Questions:

How might we approach modeling a real-world problem using ILP, considering the need for integer solutions?
What are some examples of problems where integer constraints are essential?
Can you think of a situation where a seemingly good model might perform poorly in practice?
How does the non-convexity of the solution space in ILP affect the search for optimal solutions?

For the next lecture, we will delve deeper into how to formulate specific types of constraints and how to improve the efficiency of our models. We will also explore some practical examples of ILP applications.

--- title: "Introduction to Integer Linear Programming" author: "Your Name" date: "2025-01-30" format: html: toc: true # Table of Contents toc-depth: 2 code-tools: true theme: cosmo # Or "journal" for Distill-like minimalism --- # Introduction This lecture provides an overview of **Integer Linear Programming (ILP)**, a powerful optimization technique used to solve a wide range of real-world problems. We will explore the fundamental concepts of ILP, its relationship to **Linear Programming (LP)**, and the challenges associated with solving ILP problems. The main objectives are to understand how to model optimization problems using ILP, to recognize the differences between LP and ILP, and to appreciate the computational complexity of ILP. Key concepts include **variables**, **objective functions**, **constraints**, and the distinction between **polynomial** and **NP-hard** problems. # Operations Research and Mathematical Programming Operations research provides a rich and powerful theory for solving optimization problems of various natures. **Mathematical programming** is a specific type of optimization where variables are vectors of numbers, and functions are functions of these vectors. Problems with **convex solution sets** and **convex** or **concave objective functions** are particularly interesting because **local optima are also global optima**. Linear and quadratic functions, especially linear constraints, are of significant interest. # Integer Linear Programming (ILP) **Integer Linear Programming (ILP or PLI in Italian)** is a significant contribution of operations research. It allows us to model and ultimately solve a large number of optimization problems of different natures. ILP is built upon **linear programming**, which was one of the first problems studied by operations researchers, particularly **George Dantzig**, who is considered the father of operations research. Dantzig developed the **simplex method** to solve linear programming problems, which, after 70 years, is still fundamentally the best way to solve them. ## The Role of Solvers For the next few lectures, we will treat the linear and integer linear programming solver as a **black box**. We will not go into the details of how a solver works but assume that a solver exists. We will provide input to the solver, and it will output the solution. Our task is to learn the language of modeling, to write models that serve as input for the solver. ## Modeling Alternatives When writing a model for a problem, there are always many alternatives. We have virtually infinite choices for **variables**, **objective functions**, and **constraints**. Some models will be better than others, just as there are virtually infinite algorithms to solve the same problem, some more efficient than others. :::: tcolorbox ::: definition **Definition 1** (Model Components). *A model consists of three parts:* 1. ***Variables**: Decisions to be made to determine a solution.* 2. ***Objective Function**: How the cost of a solution is a function of these variables.* 3. ***Constraints**: Conditions that variables must satisfy to represent admissible solutions.* ::: :::: # Linear Programming (LP) Linear programming involves minimizing or maximizing a linear function of $n$ variables, subject to a set of linear constraints. :::: tcolorbox ::: definition **Definition 2** (Linear Programming). *Linear programming is characterized by:* - *A cost vector $c \in \mathbb{R}^n$.* - *A constraint coefficient matrix $A \in \mathbb{R}^{m \times n}$.* - *A vector of constant terms $b \in \mathbb{R}^m$.* *The problem can be formulated as: $$\begin{aligned} \text{Maximize or Minimize} \quad & \sum_{j=1}^{n} c_j x_j \\ \text{Subject to} \quad & \sum_{j=1}^{n} a_{ij} x_j \geq, =, \leq b_i, \quad i = 1, \dots, m \\ & x_j \geq 0, \quad j \in J \subseteq \{1, \dots, n\} \end{aligned}$$* ::: :::: :::: tcolorbox ::: example **Example 1**. *An example of a linear programming problem is: $$\begin{aligned} \text{Maximize} \quad & 4x_1 + 2x_2 + 3x_3 \\ \text{Subject to} \quad & 3x_1 + 2x_2 - x_3 \geq 5 \\ & 5x_1 - 3x_2 + x_3 \leq 2 \\ & -2x_2 + x_3 \geq 1 \\ & 2x_1 + 2x_2 - 3x_3 = 8 \\ & x_1, x_2, x_3 \geq 0 \end{aligned}$$* ::: :::: ## Non-negativity Constraints Non-negativity constraints ($x_j \geq 0$) are often included and are usually written separately because they are common and do not characterize the problem well. # Integer Constraints In many real-world problems, solutions must be integers. For example, you cannot hire a fraction of a person or build a fraction of a hospital. :::: tcolorbox ::: remark **Remark 1**. *Linear programming does not allow for imposing that variables must be integers. It might happen that the solution has integer components, but it cannot be enforced with linear inequalities.* ::: :::: ## Computational Complexity Adding the constraint that variables must be integers makes the problem computationally difficult. - Linear programming without integer constraints is a **polynomial problem**. There are efficient algorithms to solve it in polynomial time relative to the instance size. - When integer constraints are added, the problem becomes **NP-hard**. There are no known polynomial-time algorithms to solve it, and it is likely that none exist if P $\neq$ NP. :::: tcolorbox ::: definition **Definition 3** (Integer Linear Programming (ILP)). *Integer Linear Programming (ILP) is an extension of linear programming where some or all variables are required to be integers.* ::: :::: :::: tcolorbox ::: theorem **Theorem 1**. *ILP is NP-hard.* ::: This theorem states that the Integer Linear Programming problem is NP-hard. :::: # Conclusion In this lecture, we introduced the concept of **Integer Linear Programming (ILP)** and its foundation in **Linear Programming (LP)**. We discussed the components of a model, including **variables**, **objective functions**, and **constraints**, and highlighted the importance of writing efficient models. We also touched upon the computational complexity differences between LP, which is solvable in polynomial time, and ILP, which is NP-hard. Key takeaways include the understanding that ILP is a powerful tool for solving optimization problems where integer solutions are required, but it comes with increased computational challenges compared to LP. The **simplex method**, developed by **George Dantzig**, remains a cornerstone in solving LP problems, and understanding LP is crucial for tackling ILP. **Follow-up Questions:** 1. How might we approach modeling a real-world problem using ILP, considering the need for integer solutions? 2. What are some examples of problems where integer constraints are essential? 3. Can you think of a situation where a seemingly good model might perform poorly in practice? 4. How does the non-convexity of the solution space in ILP affect the search for optimal solutions? For the next lecture, we will delve deeper into how to formulate specific types of constraints and how to improve the efficiency of our models. We will also explore some practical examples of ILP applications.