The variable splitting scheme in the context of Lagrangian relaxation

Question

I am interested to know solving the generalized assignment problem (GAP) using the variable splitting scheme, specifically, in the context of Lagrangian relaxation. The problem is stated as follows: (named GAP2)

\begin{align} \text { Minimize Z = } \alpha \sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} x_{i j} + \beta \sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} y_{i j}\\ S.t: \sum_{j=1}^{n} r_{i j} x_{i j} \leq a_{i}, \quad i \in M \quad \text{(1)}\\ \sum_{i=1}^{m} y_{i j}=1, \quad j \in N \quad \text{(2)}\\ x_{i j}=y_{i j}, \quad i \in M, j \in N \quad \text{(3)}\\ x_{i j}, y_{i j} =0 \text { or } 1, \quad i \in M, j \in N \quad \text{(4)}\\ \end{align}

where, $\alpha, \beta$ are constant and $\alpha+\beta=1$. By dualizing the third constraint the remaining problem can be decomposed into two sub-problems. One is based on the $x_{ij}$ and the other is based on the $y_{ij}$. The dualized problem is already as follows:

\begin{array}{} \text { Minimize Z = } \alpha \sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} x_{i j} + \beta \sum_{i=1}^{m} \sum_{j=1}^{n} c_{i j} y_{i j} + \sum_{i=1}^{m} \sum_{j=1}^{n} \mu_{i j} (x_{i j} - y_{i j})\\ \quad S.t:(1), (2), (4); \end{array}

The first sub-problem is $\{ min\sum_{i=1}^{m} \sum_{j=1}^{n} (\alpha c_{i j} + \mu_{i j})x_{i j}|S.t: (1),(4)\}$, and the second also would be $\{ min\sum_{i=1}^{m} \sum_{j=1}^{n} (\beta c_{i j} - \mu_{i j})x_{i j}|S.t: (2),(4)\}$.

These two sub-problems can still be solved efficiently by using a single knapsack problem and a heuristic approach respectively. Also, there are some polynomial-time approximation algorithms to solve the original problem (GAP) as well, like MTHG proposed by $\text{Martello & Toth(1981)}$.

I have tried to solve some of the variants of this problem in an LR approach by using subgradient optimization. In many cases, the original problem (GAP) can be solved very efficient to produce the lower bound even without applying any repairing mechanism to invoke a feasible solution, whereas the GAP2, in the best attempt, is a worse case LB and far quite from the solution of the GAP!!?

The main question is rising in mind is what would be a benefit of using this decomposition scheme to solve this problem?

Answer 1

The only occurrences of this decomposition that I am aware of are from:

• Jörnsten K, Näsberg M (1986) A new Lagrangian relaxation approach to the generalized assignment problem. European Journal of Operational Research 27:313–323. https://doi.org/10.1016/0377-2217(86)90328-0
• Cattrysse DG, Van Wassenhove LN (1992) A survey of algorithms for the generalized assignment problem. European Journal of Operational Research 60:260–272. https://doi.org/10.1016/0377-2217(92)90077-M

In the latter, the authors wrote:

The proposed bound is compared with traditional Lagrangean relaxations and it is concluded (based on a rather small set of 10 test problems with 4 agents and 25 jobs) that it is stronger than the one obtained by relaxing either constraints (3) or (2) in the original problem formulation (GAP).

So, its not very convincing. And considering that to the best of my knowledge, it has not appeared again later, I would conclude that it has not been particularly useful afterwards.

Answer 2

I am familiar with variable splitting (also known as Lagrangian decomposition) being applied to facility location problems. We used it in our paper:

• Snyder and Daskin, Stochastic $p$-robust location problems, IIE Transactions 38, 971-985, 2006. https://www.tandfonline.com/doi/abs/10.1080/07408170500469113

It is also used by

• Barcelo, et al., Computational results from a new Lagrangean relaxation algorithm for the capacitated plant location problem, EJOR 53, 38-45, 1991. https://www.sciencedirect.com/science/article/abs/pii/0377221791900919

One advantage of variable splitting is that its bound is provably at least as tight as the bound from "regular" Lagrangian relaxation, and is strictly better if neither subproblem has the integrality property (see Guignard and Kim, Lagrangean decomposition: a model yielding strong Lagrangean bounds, Mathematical Programming 39, 215–228, 1987).

Sometimes it also yields subproblems that are easier to solve than regular LR does. In our paper it yields subproblems that are separable (and therefore easy to solve) whereas the more straightforward LR approach yields a non-separable subproblem.