5
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Why do you solve the second subproblem heuristically? It looks like a GUB problem, one just need to loop through the variables and select the one with the best value $\endgroup$
    – fontanf
    Apr 18, 2022 at 21:48
  • $\begingroup$ @fontanf, yes. As I wanted to test, I try with a simple heuristic. Actually, it can be solved in the way you mentioned. Thanks. $\endgroup$
    – A.Omidi
    Apr 19, 2022 at 4:14

2 Answers 2

4
$\begingroup$

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

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.

$\endgroup$
1
  • $\begingroup$ Many thanks for your useful answer and the mentioned references. I agree with you for which it is not very effective to use this kind of scheme as a Lagrangian relaxation. I would think, maybe, it is being useful in the DW decomposition method, but I am not sure as I do not test it. Thanks once again. $\endgroup$
    – A.Omidi
    Apr 18, 2022 at 17:23
4
$\begingroup$

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

It is also used by

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.

$\endgroup$
1
  • $\begingroup$ Many thanks for your detailed explanation and references. I will check them and back to you if I have any issues. $\endgroup$
    – A.Omidi
    Apr 19, 2022 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.