## 3 Methods  
The relaxation presented here follows the same lines as the one given by [PERSON] and [PERSON] for the QAP [22]. We start by linearizing objective function (IQP) by introducing binary variables \(y_{ikjl}\) defined as \(y_{ikjl}:=x_{ik}\cdot x_{jl}\) and constraints \(y_{ikjl}\leq x_{jl}\) and \(y_{ikjl}\leq x_{ik}\) for all \(i\leq j\) and \(k\
eq l\). We focus here on the case in which all entries in \(W\) are non-negative. Therefore, we do not need to enforce \(y_{ikjl}\geq x_{ik}+x_{jl}-1\), which would be necessary in a general linearization of a product of two binary variables. In Section 5, we will discuss this assumption. Rather than using the aforementioned constraints, we make use of a stronger set of constraints which we obtain by multiplying Constraints (2) and (3) by \(x_{ik}\):  
\[\sum_{ \begin{subarray}{c}l\\ l\
eq k\end{subarray} }y_{ikjl} =\sum_{ \begin{subarray}{c}l\\ l\
eq k\end{subarray} }x_{ik}x_{jl}\leq\sum_{l}x_{ik}x_{jl}\leq x_{ik},\;\;\; \forall i,j,k,\;i<j \tag{5}\] \[\sum_{ \begin{subarray}{c}j\\ j>i\end{subarray} }y_{ikjl} =\sum_{ \begin{subarray}{c}j\\ j>i\end{subarray} }x_{ik}x_{jl}\leq\sum_{j}x_{ik}x_{jl}\leq x_{ik},\;\;\;\forall i,k,l,\;k\
eq l \tag{6}\]  
We proceed by splitting the variable \(y_{ikjl}\) (where \(i<j\) and \(k\
eq l\)). In other words, we extend the objective function such that the counterpart of \(y_{ikjl}\) becomes \(y_{jlik}\). This is accomplished by rewriting the dummy constraint in Equation (6) to \(j\
eq i\). In addition, we split the weights: \(w_{ikjl}=w_{jlik}=(w^{\prime}_{ikjl}/2)\) where \(w^{\prime}_{ikjl}\) denotes the original weight. Furthermore, we require that the counterparts of the split decision variables assume the same value, which results in the following integer linear programming formulation:\[\max_{x,y} \sum_{i,k}c_{ik}x_{ik}+\sum_{ \begin{subarray}{c}i,j\\ i<j\end{subarray} }\sum_{ \begin{subarray}{c}k,l\\ k\
eq l\end{subarray} }w_{ikjl}y_{ikjl}+\sum_{ \begin{subarray}{c}i,j\\ i>j\end{subarray} }\sum_{ \begin{subarray}{c}k,l\\ k\
eq l\end{subarray} }w_{ikjl}y_{ikjl}\] (ILP) s.t. \[\sum_{l}x_{jl}\leq 1 \forall j \tag{7}\] \[\sum_{j}x_{jl}\leq 1 \forall l\] (8) \[\sum_{ \begin{subarray}{c}l\\ l\
eq k\end{subarray} }y_{ikjl}\leq x_{ik} \forall i,j,k,\ i\
eq j\] (9) \[\sum_{ \begin{subarray}{c}j\\ j\
eq i\end{subarray} }y_{ikjl}\leq x_{ik} \forall i,k,l,\ k\
eq l\] (10) \[y_{ikjl}=y_{jlik} \forall i,j,k,l,\ i<j,k\
eq l\] (11) \[y_{ikjl}\in\{0,1\} \forall i,j,k,l,\ i\
eq j,k\
eq l\] (12) \[x_{ik}\in\{0,1\} \forall i,k \tag{13}\]  
We can solve the continuous relaxation of Equation (ILP) via its Lagrangian dual by dualizing the linking constraints Equation (11) with multiplier \(\lambda\):  
\[\min_{\lambda}\quad Z_{\mathrm{LD}}(\lambda)\] (LD)  
where \(Z_{\mathrm{LD}}(\lambda)\) equals  
\[\max_{x,y} \sum_{i,k}c_{ik}x_{ik}+\sum_{ \begin{subarray}{c}i,j\\ i<j\end{subarray} }\sum_{ \begin{subarray}{c}k,l\\ k\
eq l\end{subarray} }(w_{ikjl}+\lambda_{ikjl})y_{ikjl}+\sum_{ \begin{subarray}{ c}i,j\\ i>j\end{subarray} }\sum_{ \begin{subarray}{c}k,l\\ k\
eq l\end{subarray} }(w_{ikjl}-\lambda_{jlik})y_{ikjl}\] s.t. Constraints (7)-(13)  
Now that the linking constraints have been dualized, one can observe that the remaining constraints decompose the variables into \(|V_{1}||V_{2}|\) disjoint groups, where variables across groups are not linked by any constraint, and where each group contains a variable \(x_{ik}\) and variables \(y_{ikjl}\) for \(j\
eq i\) and \(l\
eq k\). Hence, we have  
\[Z_{\mathrm{LD}}(\lambda) = \max_{x} \sum_{i,k}[c_{ik}+v_{ik}(\lambda)]x_{ik}\] (LD \[{}_{\lambda}\] ) s.t. \[\sum_{l}x_{jl}\leq 1 \forall j \tag{14}\] \[\sum_{j}x_{jl}\leq 1 \forall l\] (15) \[x_{ik}\in\{0,1\} \forall i,k \tag{16}\]  
which corresponds to a maximum weight bipartite matching problem on the so-called alignment graph \(G_{m}=(V_{1}\cup V_{2},E_{m})\). In the general case, \(G_{m}\) is a complete bipartite graph, _i.e._\(E_{m}=\{(i,k)\mid i\in V_{1},v_{2}\in V_{2}\}\).