The Lagrangian Duality Gap and Integer Problems

For integer programming problems, the Lagrangian dual typically produces a strictly weaker bound than the primal optimum, creating a positive duality gap. This lesson introduces the absolute and relative duality gap, explains why integer problems generally have a gap, and compares the Lagrangian bound to the LP relaxation via the integrality property.

Step 1 of 157%

Tutorial

Introduction to the Duality Gap

For a primal integer program of the form

z^* = \min_{x \in X}\{c^T x : Ax \le b\},

the Lagrangian dual is

z_{LD} = \max_{\lambda \ge 0} g(\lambda), \quad g(\lambda) = \min_{x \in X}\{c^T x + \lambda^T (b - Ax)\}.

Weak duality guarantees that

z_{LD} \le z^*.

The Lagrangian duality gap is the (always nonnegative) difference

\Delta = z^* - z_{LD} \ge 0.

The relative duality gap normalizes by the primal optimum:

\delta = \dfrac{z^* - z_{LD}}{|z^*|}.

For convex continuous problems satisfying a constraint qualification (e.g., linear programs), strong duality holds and $\Delta = 0$ . For integer programs this is no longer guaranteed and the gap is typically strictly positive.

For example, if an integer program has $z^* = 100$ and Lagrangian dual value $z_{LD} = 92$ , then

\Delta = 100 - 92 = 8, \qquad \delta = \dfrac{8}{100} = 8\%.