Linear Programming Duality

Summary

We show an upper bound on an LP problem by finding its dual. We also show some theorems about the relationship between the primal and the dual.

Contents

• Example
  • Dual
• Weak Duality Theorem
  • Weak Duality Corollary
  • Weak Duality Corollary 2
• Feasbility Checks
• Unbounded Checks
• Strong Duality Theorem

Example

$\max x_1+6x_2+10x_3$

$s.t. \begin{aligned} x_1 &\le 300 \ x_2 &\le 200 \ x_1+3x_2+2x_3 &\le 1000 \ x_2+3x_3 &\le 500 \end{aligned}$

Optimal at $\left( 200, 200, 100 \right) = 2400$

Can we verify?

We can create an upper bound on the objective function. Then, if we have the same value as the upper-bound, we are optimal.

Dual

The upper-bound is a new LP based on the original

$\min 300y_1 + 200y_2 + 1000y_3 + 500y_4$

$s.t. \begin{aligned} y_1 + y_3 &\ge 1 & [1] \ y_2 + 3y_3 + y_4 &\ge 6 & [2]\ 2y_3 + 3y_4 &\ge 10 & [3] \end{aligned}$

1. Because $x_1$ appears in the first and third rows of the original problem.
2. Because $x_2$ appears in the second, third, and fourth rows.
3. Because $x_3$ appears in the third and fourth rows.

The original form:

$\begin{aligned} \max c^T x \ Ax &\le b \ x &\ge 0 \end{aligned}$

Becomes

$\begin{aligned} \min b^T y \ A^Ty &\ge c \ y &\ge 0 \end{aligned}$

We go from n vars and m constraints, to m vars and n constraints

The dual of the dual is the original

The original is also called the primal

Weak Duality Theorem

Given a feasible x for primal LP and a feasible y for dual LP:

$$c^Tx \le b^Ty$$

Weak Duality Corollary

If we find a feasible x and feasible y where $c^Tx = b^Ty$, then x and y are optimal.

Weak Duality Corollary 2

If primal LP is unbounded, dual LP is infeasible

• If primal is infinite, how can dual be greater than that?

If dual LP is unbounded, primal LP is infeasible

• If dual is negative infinity, how can primal be less than that?

Feasbility Checks

Given:

$\begin{aligned} \max c^Tx \ Ax &\le b \ x &\ge 0 \end{aligned}$

We can add a new variable, z, to trivially satisfy all the constraints. Then we check if z is non-negative

$\begin{aligned} a_1x_1 + \ldots + a_nx_n & \le b \ x_1, \ldots, x_n &\ge 0 \end{aligned}$

Becomes

$\begin{aligned} a_1x_1 + \ldots + a_nx_n +z & \le b \ x_1, \ldots, x_n &\ge 0 \end{aligned}$

If $z \ge 0$, then LP is feasible

$\begin{aligned} \max z \ Ax +z &\le b \ x &\ge 0 \end{aligned}$

Unbounded Checks

Given:

$\begin{aligned} \max c^Tx \ Ax &\le b \ x &\ge 0 \end{aligned}$

If dual LP is infeasible, then primal is unbounded or infeasible. If the primal is feasible and the dual is infeasible, then primal is unbounded.

Strong Duality Theorem

Primal LP is feasible and bounded $\iff$ dual LP is feasible and bounded.

Primal has optimal $x^* \iff$ dual has optimal $y^*$