Lagrangian Relaxation of Integer Programs

John Mitchell

See Nemhauser and Wolsey, section II.3.6, for more information.

We let z_{IP } denote the optimal value of the integer program

| (1) |

The matrices A^{1} ^{m1×n} and A^{2} ^{m2×n}, and all vectors are dimensioned appropriately. For any
λ _{+}^{m1}, we obtain the Lagrangian relaxation

| (2) |

Proposition 1 Problem (2) is a relaxation of problem (1) for any λ ≥ 0, in that any x feasible in (1) is also feasible in (2) with no smaller objective function value.

Proof. If x is feasible in (1) then it is feasible in (2) with objective function value

since λ ≥ 0 and A^{1}x ≤ b^{1}. □

Thus, the optimal value of problem (2) gives an upper bound on the optimal value of (1) for any λ ≥ 0. In the Lagrangian dual problem, this upper bound is minimized:

| (3) |

We immediately obtain the following proposition:

We can use polyhedral theory to characterize the optimal value of the Lagrangian dual (3) more precisely. First, let

| (4) |

so Q is the feasible region for (2) for any λ ≥ 0.

This is Theorem 6.2 on page 327, and the proof can be found in the textbook. In the proof, conv(Q) is represented in terms of its extreme points and rays and then linear programming duality is exploited to derive the result.

The LP relaxation of (1) has value

| (5) |

The three values are compared in the following theorem:

Theorem 2 z_{IP } ≤ z_{LD} ≤ z_{LP }, and all of the inequalities can be strict.

The proof of the inequalities follows directly from Theorem 1. Examples can be constructed to show the inequalities can all be strict.

Theorem 3 z_{LD} = z_{LP } if all the extreme points of {x _{+}^{n} : A^{2}x ≤ b^{2}} are integral.

Proof. In this case, we have

so the result follows from Theorem 1. □

So: don’t want to choose the nice constraints so that the Lagrangian relaxation is too easy to solve,
because then may get no improvement over the LP relaxation. For example, don’t choose the nice
constraints so that the constraint matrix A^{2} is totally unimodular.