Lagrangian Relaxation of Integer Programs
John Mitchell

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

We let zIP denote the optimal value of the integer program

z    :=   max         cTx
 IP                   1        1
         subject to  A2x  ≤   b2      (complicating constraints)
                     A x  ≤   b       (nice constraints)
                       x   ∈  ℤn+

The matrices A1 ∈ ℝm1×n and A2 ∈ ℝm2×n, and all vectors are dimensioned appropriately. For any λ ∈ ℝ+m1, we obtain the Lagrangian relaxation

zLR (λ) :=  max         cTx +  λT (b1 - A1x )
            subject to  A2x   ≤  b2
                           x  ∈  ℤ +

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

 T       T  1    1      T
c x  + λ  (b - A  x) ≥ c  x

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:

zLD :=  min         zLR (λ )
        subject to  λ  ≥   0.

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

Q  :=  {x ∈ ℤn  : A2x ≤  b2},

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

z    =  max {cTx  : A1x ≤ b1, x ∈ conv (Q )},

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

zLP :=  max          cT x
        subject to  A1x   ≤   b1
                      2        2
                    A  x  ≤   bn
                       x  ∈   ℝ+

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

                   n    2     2
conv (Q ) = {x ∈ ℝ + : A x ≤ b },

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.