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?**