Lagrangian Relaxation of Integer Programs
John Mitchell

We let zIP denote the optimal value of the integer program

 (1)

The matrices A1 m1×n and A2 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 A1x b1.

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:

Proposition 1 The optimum value of (3) is no smaller than the optimum value of (1).

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.

Theorem 1 The optimum value zLD of the Lagrangian dual (3) is given by

a linear program.

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 zIP zLD zLP , 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 zLD = zLP if all the extreme points of {x +n : A2x b2} 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 A2 is totally unimodular.