Separable Lagrangian Decomposition for Quasi-Separable Problems

Lagrangian relaxation is a powerful technique that applies when the removal of some appropriately chosen set of “complicating” constraints makes a(n hard) optimization problem “much easier” to solve. The most common reason for this is that the relaxed problem fully decomposes in (a large number of) independent subproblems. However, a different case happens when the removal of the constraints leaves a number of blocks of semi-continuous variables without constraints between them except those involving the single binary variable commanding them. In this case the relaxation can still be easily solvable, but this involves a two-stage approach whereby the separable blocks are solved first, possibly in parallel, and only then one single problem can be solved to find the optimal value of the design variables. We call this a quasi-separable setting. While the relaxation can be efficiently solved, the fact that it boils down to what formally amounts to a single problem prevents from using techniques—disaggregated master problems, possibly with “easy components”—that allow to solve the corresponding Lagrangian dual more efficiently. We develop an ad-hoc reformulation of the standard master problem of (stabilised) cutting-plane approaches that allow to define the Lagrangian function as the explicit sum of different components, thereby better exploiting the actual structure of the problem, at the cost of introducing a smaller number of extra Lagrangian multipliers w.r.t. what would be required by standard approaches. We also highlight the connection between this reformulation of the master problem and the Lagrangian Decomposition technique. We computationally test our approach on one relevant problem with the required structure, i.e., hard Multicommodity Network Design with budget constraints on the design variables, showing that the approach can outperform state-of-the-art traditional ones.