What's the difference between Lagrangian relaxation and Lagrangian decomposition?

Question

What is the difference between Lagrangian relaxation and Lagrangian decomposition? Are they the same thing?

Answer 1

They are not the same thing. Lagrangian decomposition is a special case of Lagrangian relaxation.

(Note: I'm talking specifically about integer programming problems in this answer, though some of this answer applies to continuous optimization as well.)

Lagrangian relaxation involves removing (relaxing) one or more constraints and penalizing violations of those constraints in the objective function using coefficients called multipliers. The constraints are chosen so that the problem without the constraints (the subproblem) is much easier to solve than the original problem. The purpose is to derive a lower bound (for a minimization problem) or an upper bound (for a maximization problem). Often, we use the solution to the subproblem to derive feasible solutions for the original problem, which provide an upper bound (for minimization problems) or a lower bound (for maximization problems). By updating the multipliers (essentially solving a dual problem), we get tighter bounds.

Lagrangian decomposition (introduced by Guignard and Kim (1987)), also known as variable splitting, is a specific form of Lagrangian relaxation in which we "double" some of the variables, add a constraint requiring the original variables to equal their doubles, and then relax that constraint (using Lagrangian relaxation). It produces bounds that are at least as tight as those from Lagrangian relaxation.

---

Let me give an example. Consider the capacitated fixed-charge location problem (CFLP):

$$\begin{alignat}{2} \text{minimize} \quad & \sum_{j\in J}f_jx_j + \sum_{i\in I}\sum_{j\in J} h_ic_{ij}y_{ij} \\ \text{subject to} \quad & \sum_{j\in J} y_{ij} = 1 &\quad& \forall i\in I \\ & \sum_{i\in I} h_iy_{ij} \le v_jx_j && \forall j \in J \\ & x_j \in \{0,1\} && \forall j\in J \\ & y_{ij} \ge 0 && \forall i\in I, j\in J \end{alignat}$$

Here, $I$ and $J$ are the sets of customers and potential facility locations; $h_i$ is the demand of customer $i$; $f_j$ is the fixed cost to open facility $j$; $c_{ij}$ is the cost per unit to supply $i$ from $j$; and $v_j$ is the capacity of facility $j$. The decision variables are $x_j$, which equals 1 if we open facility $j$ and 0 otherwise; and $y_{ij}$, which the fraction of customer $i$'s demand that we serve from facility $j$.

There are various other formulations, some of which are superior in some ways, but this one will do for this example.

One way to attack the problem using Lagrangian relaxation is to relax the first set of constraints to get:

$$\begin{alignat}{2} \text{minimize} \quad & \sum_{j\in J}f_jx_j + \sum_{i\in I}\sum_{j\in J} h_ic_{ij}y_{ij} + && \sum_{i\in I} \lambda_i\left(1 - \sum_{j\in J} y_{ij}\right) \\ \text{subject to} \quad & \sum_{i\in I} h_iy_{ij} \le v_jx_j && \forall j \in J \\ & x_j \in \{0,1\} && \forall j\in J \\ & y_{ij} \ge 0 && \forall i\in I, j\in J \end{alignat}$$

This subproblem can be solved optimally by solving $|J|$ continuous knapsack problems, which are easy.

To use Lagrangian decomposition, introduce new variables $w_{ij}$ that equal $y_{ij}$. We write some of the constraints in the original model using $y$ and some using $w$, split them in the objective function, and require them to equal each other:

$$\begin{alignat}{2} \text{minimize} \quad & \sum_{j\in J}f_jx_j + \beta\sum_{i\in I}\sum_{j\in J} h_ic_{ij}y_{ij} + &&(1-\beta)\sum_{i\in I}\sum_{j\in J} h_ic_{ij}w_{ij} \\ \text{subject to} \quad & \sum_{j\in J} w_{ij} = 1 && \forall i\in I \\ & \sum_{i\in I} h_iy_{ij} \le v_jx_j && \forall j \in J \\ & w_{ij} = y_{ij} && \forall i\in I, j\in J \\ & x_j \in \{0,1\} && \forall j\in J \\ & y_{ij}, w_{ij} \ge 0 && \forall i\in I, j\in J \end{alignat}$$

for a constant $\beta \in [0,1]$. Then we relax only the $w_{ij}=y_{ij}$ constraints. I won't write out the subproblem here. It can be solved easily: It decomposes into two problems, one of which reduces to $|J|$ continuous knapsack problems and a single 0–1 knapsack problem, and the other of which can be solved by inspection. (See Barcelo, Fernandez, and Jörnsten (1991).)

Since the subproblem from straightforward Lagrangian relaxation has the integrality property while the subproblem from Lagrangian decomposition does not, Lagrangian decomposition yields bounds that are at least as tight as those from straightforward Lagrangian relaxation.

---

Reference

Barcelo, J., Fernandez, E. and Jörnsten, K.O. (1991) Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem. European Journal of Operational Research, 53(1), 38–45.

Guignard, M. and Kim, S. (1987) Lagrangean decomposition: a model yielding strong Lagrangean bounds. Mathematical Programming, 39, 215–228.