# Lagrangean Relaxation of quadratic assignment problem to yield $n$ knapsack problems?

Consider the assignment problem:

$$Z = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik}$$ s.t. $$\sum_i x_{ij} = 1 \quad\forall j$$ $$a \leq \sum_j x_{ij} \leq b \quad\forall i$$ $$x_{ij} \in \{0,1\}\quad\forall i,j$$

So, in scheduling terminology, $x_{ij}$ is $1$ if job $j$ is assigned to machine $i$, or $0$ otherwise, for $i = 1,\ldots,n$, $j = 1,\ldots,m$, and $k = 1,\ldots,m$.

The first constraint says that each job must be assigned to exactly one machine, and the second constraint says that the number of jobs assigned to each machine must fall on the interval $[a,b]$.

In the objective, there is no cost for assigning job $j$ to machine $i$, however there is a cost $c_{jk}$ of assigning job $j$ to machine $i$ and job $k$ to machine $i$. I suppose you could consider this cost the level of incompatibility between the two jobs - perhaps some sort of changeover cost. This problem is NP-Hard.

Now, suppose the first set of constraints are dualized:

$$Z_\lambda = \min \sum_i\sum_j\sum_k c_{jk}\cdot x_{ij}\cdot x_{ik} + \sum_j[\lambda_j(\sum_ix_{ij} - 1) ]$$ s.t. $$a \leq \sum_j x_{ij} \leq b \quad\forall i$$ $$x_{ij} \in \{0,1\}\quad\forall i,j$$

Now, the constraints which couple each machine together have been dualized and the problem breaks apart into one subproblem for each machine.

I don't have a lot of experience with this sort of Lagrangean Relaxation-based decomposition. I believe, in theory, it should just be a case of solving each of the subproblems as a separate, self-contained problem, and update the lagrangian multipliers $\lambda$ at each iteration. I'm using the subgradient method converge on the optimal $\lambda$.

The problem I'm having is that there is no difference at all in the definition of the subproblems from one machine to another, and the lagrangian multipliers are shared between all subproblems. That means, if I have $n$ machines, then I have $n$ completely identical subproblems which, when I solve, I obtain an identical solution from each of them. Sure, I can update my $\lambda$ vector based on my primal infeasible solution, but the model definitions in the subsequent iterations remain identical.

Clearly I'm doing something wrong, but I'm not sure what, exactly. The paper I have here "Lagrangean Relaxation - Monique Guignard (2003)", as well as others I've discussed this with assert that dualizing the coupling constraints for this sort of model should produce $n$ subproblems.

First, always try and avoid non-linearity in your formulation. Usually logical conditions like "if both jobs $j$ and $k$ are assigned to machine $i$" can be expressed linearly by introducing more variables.

$$z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0$$ You can confirm that $z_{ijk}$ is 1 only if both $x_{ik},x_{ij}$ are 1. The problem then is

$$Z = \min \sum_{ijk}c_{jk}z_{ijk}\\ \sum_{i}x_{ij} =1\\ a \leq \sum_j x_{ij} \leq b\\ z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0$$

Decomposing leads to $$Z^\lambda = \min \sum_{ijk}c_{jk}z_{ijk}+\sum_j\lambda_j\left(\sum_{i}x_{ij} -1\right)\\ a \leq \sum_j x_{ij} \leq b\\ z_{ijk} \geq -1+x_{ij} + x_{ik}\\ z_{ijk} \leq 3-x_{ij} - x_{ik}\\ z_{ijk} \geq 0$$ The constraint that is relaxed is the assignment constraint that all jobs must be assigned only one machine, so your relaxed solution would have more than one machine assigned per job. In your solution of the dual problem when you update $\lambda$ the penalty due to the dualization will increase to a point where this penalty will be very expensive and the program will start setting some of the $x_{ij}$s to 0, so go ahead with solving the dual problem.

There is however, another problem with complete symmetry in the machines $i$, specially if your problem is large, there are a lot of possible solutions. This is because any optimal assignment can be permuted to arrive at another solution. And you may be unnecessarily searching across essentially equal assignments. The way around this is to add symmetry breaking constraints of the form given in [1].

[1] Sherali, Hanif D., and J. Cole Smith. "Improving discrete model representations via symmetry considerations." Management Science 47.10 (2001): 1396-1407.

• By the way, my original formulation was totally linear and not quadratic. I had the same sort of $z_{ijk}$ variable as you suggest. I found that the performance of this approach was significantly worse than the quadratic formulation. For my problem size (n = 7, m = 65, a = 7, b = 10), it would take almost 24 hours to solve the linear version using B&B, whereas with the quadratic formulation it only took about 3 hours. – Ozzah May 7 '14 at 23:40
• Also, thank you very much for the symmetry breaking reference. I was aware of the problems regarding solution symmetry but was unaware how to overcome them for this particular problem. I had avoided at least $n-1$ identical solutions by enforcing job $1$ to be on machine $1$. Since job-machine pairings are irrelevant, this doesn't alter the final solution at all. I could enforce more job-machine pairs to further reduce symmetry, but that would no longer guarantee a truly optimal solution as I would be making assumptions. – Ozzah May 7 '14 at 23:42
• I notice your formulation and Lagrangean relaxation has the same problem as my formulation. If I construct a separate subproblem for each machine, they are all necessarily identical. If I solve the subproblem for machine $i$, I will get the exact same solution for machine $i+1$. Should I be solving each machine separately or all at once? I assume solving them all at once in one model will still not overcome the problem where each individual machine's solution will be identical to the others. – Ozzah May 8 '14 at 0:00
• Yes, your solution for each machine will be identical. This is only a lower bound though,I assume you will have some accompanying heuristic solution to make the solution feasible, you will have to start spreading jobs across machines differently when you do that. – skr May 9 '14 at 0:13
• Ok, I understand. The solution for each individual machine will unavoidably be identical and the solution will not be primal feasible (obviously), however the lower bound should be tighter than the lower bound from the standard linear relaxation. In other words, I can't use this method to solve the problem, I would need to have this method embedded inside B&B or some other procedure. – Ozzah May 9 '14 at 1:21