From LP to Integer Programming: Why Integrality Matters

Introduces integer programming as an extension of linear programming. Defines pure IPs, mixed IPs, and binary IPs; explains the LP relaxation and the pitfalls of rounding; and establishes how the LP relaxation provides a bound on the IP optimum.

Step 1 of 157%

Tutorial

Introduction

A linear program (LP) allows decision variables to take any real values within the feasible region. In many applications, however, only whole-number values are meaningful: a factory cannot ship 2.72.7 trucks, a scheduler cannot hire 4.34.3 workers, and a yes/no decision cannot be made 0.60.6 of the way. An integer program (IP) is a linear program with the additional requirement that some or all decision variables take integer values.

Integer programs are classified by which variables carry the integrality requirement:

  • Pure integer program: every decision variable must be an integer.
  • Mixed integer program (MIP): some variables must be integers, others remain continuous.
  • Binary (0-1) integer program (BIP): every variable is restricted to {0,1}\{0, 1\}.

For instance, the formulation

maximize7x1+4x2subject to2x1+x2≤9x1,x2≥0x1,x2∈Z\begin{align*}\text{maximize}\quad & 7x_1 + 4x_2 \\ \text{subject to}\quad & 2x_1 + x_2 \le 9 \\ & x_1, x_2 \ge 0 \\ & x_1, x_2 \in \mathbb{Z}\end{align*}

is a pure IP. Replacing the last line with x1,x2∈{0,1}x_1, x_2 \in \{0,1\} gives a BIP, and requiring only x1∈Zx_1 \in \mathbb{Z} while leaving x2x_2 continuous gives a MIP.

↑ ↓ navigate · Enter open · Esc close · ⌘K/Ctrl K toggle