The LP Relaxation of an IP

Introduces the LP relaxation of an integer program: how to form it by dropping integrality constraints, how it provides bounds on the IP optimum (upper bound for maximization, lower bound for minimization), and the special case in which the LP optimum is integer-feasible and therefore also solves the IP.

Step 1 of 166%

Tutorial

Forming the LP Relaxation

The LP relaxation of an integer program is the linear program obtained by dropping every integrality constraint on the variables, while leaving the objective function and all other constraints unchanged.

The exact change depends on the type of integer program:

  • Pure IP: Remove the requirement that each xix_i be an integer.
  • Binary IP: Replace each binary restriction xi∈{0,1}x_i \in \{0, 1\} with the continuous box constraint 0≤xi≤1.0 \le x_i \le 1.
  • Mixed IP: Drop integrality only on the variables that were required to be integer; continuous variables are left as is.

For example, the binary IP

max⁡ z=3x1+2x2s.t. x1+x2≤1x1,x2∈{0,1}\begin{align*} \max\ & z = 3x_1 + 2x_2 \\ \text{s.t.}\ & x_1 + x_2 \le 1 \\ & x_1, x_2 \in \{0, 1\} \end{align*}

has LP relaxation

max⁡ z=3x1+2x2s.t. x1+x2≤10≤x1,x2≤1.\begin{align*} \max\ & z = 3x_1 + 2x_2 \\ \text{s.t.}\ & x_1 + x_2 \le 1 \\ & 0 \le x_1, x_2 \le 1. \end{align*}

Every point feasible for the IP is automatically feasible for the LP relaxation, so the LP relaxation has a larger feasible region than the original IP.

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