## 3 Methods
### Solving Strategies
#### 3.1.2 Dual Descent
\begin{split}\lambda_{ikjl}^{t}&-\gamma_{jlik}( \lambda^{t})-\left(\frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{jl}( \lambda^{t})\leq\lambda_{ikjl}^{t+1}\quad\forall j,l,\ j<i,l\
eq k\\ \lambda_{ikjl}^{t+1}&\leq\lambda_{ikjl}^{t}+\gamma_ {ikjl}(\lambda^{t})+\left(\frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_ {ik}(\lambda^{t})\quad\forall j,l,\ j<i,l\
eq k\end{split} \]  
Therefore, we have that the following inequalities imply Constraints (26) and (27) for all \(j,l\), \(j>i\), \(l\
eq k\):  
\[ \begin{split}\mu_{j}^{\prime ik}+\
u_{l}^{\prime ik}& \geq w_{ikjl}+\lambda_{ikjl}^{t}+\gamma_{ikjl}(\lambda^{t})+\left( \frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\end{split} \]  
and for all \(j,l\), \(j<i\), \(l\
eq k\)  
\[ \begin{split}\mu_{j}^{\prime ik}+\
u_{l}^{\prime ik}& \geq w_{ikjl}-\lambda_{jlik}^{t}+\gamma_{ikjl}(\lambda^{t})+\left( \frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\end{split} \]Constraints (26) and (27) are indeed implied, as, for all \(j,l\), \(j>i\), \(l\
eq k\),  
\[\mu_{j}^{\prime ik}+\
u_{l}^{\prime ik} =\mu_{j}^{ik}+\
u_{l}^{ik}+\left(\frac{1}{2(n_{1}-1)}+\frac{1}{2(n_ {2}-1)}\right)\pi_{ik}(\lambda^{t})\] \[\geq w_{ikjl}+\lambda_{ikjl}^{t}+\gamma_{ikjl}(\lambda^{t})+ \left(\frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\]  
and for all \(j,l\), \(j<i\), \(l\
eq k\)  
\[\mu_{j}^{\prime ik}+\
u_{l}^{\prime ik} =\mu_{j}^{ik}+\
u_{l}^{ik}+\left(\frac{1}{2(n_{1}-1)}+\frac{1}{2( n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\] \[\geq w_{ikjl}-\lambda_{jlik}^{t}+\gamma_{ikjl}(\lambda^{t})+ \left(\frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\]  
Since \(\mu_{j}^{ik},\
u_{l}^{ik}\geq 0\) (\(\forall j,l,\ j\
eq i,l\
eq k\)) and by definition \(\pi_{ik}(\lambda^{t})\geq 0\), Constraints (28) and (29) are satisfied as well. The objective value of \((\mu^{\prime ik},\
u^{\prime ik})\) is given by  
\[\sum_{ \begin{subarray}{c}j\\ j\
eq i\end{subarray} }\mu_{j}^{\prime ik}+\sum_{ \begin{subarray}{c}l\\ l\
eq k\end{subarray} }\
u_{l}^{\prime ik}=\sum_{ \begin{subarray}{c}j\\ j\
eq i\end{subarray} }\mu_{j}^{ik}+\sum_{ \begin{subarray}{c}l\\ l\
eq k\end{subarray} }\
u_{l}^{ik}+\pi_{ik}(\lambda^{t})=v_{ik}(\lambda^{t})+ \pi_{ik}(\lambda^{t})\]  
Since the dual Problems (25) are minimization problems and there exist, for all \(i,k\), feasible solutions with objective values \(v_{ik}(\lambda^{t})+\pi_{ik}(\lambda^{t})\), we can conclude that the objective values of the solutions are bounded by this quantity. Hence, the lemma follows: \(\qed\)  
We use \(\varphi=0.5\), \(\tau=1\), and perform the dual descent method \(L\) successive times (see Algorithm 2). ```
1\(\varphi\gets 0.5\); \([\mathrm{LB}^{*},\mathrm{UB}^{*}]\leftarrow[Z_{\mathrm{lb}}(\lambda),Z_{ \mathrm{LD}}(\lambda)]\)
2 for\(n\gets 1\)to\(L\)do
3 foreach\(i,k,j,l\), \(i<j,k\
eq l\)do
4\(\lambda_{ikjl}\leftarrow\lambda_{ikjl}+\varphi(\gamma_{ikjl}+\frac{\pi_{ik}( \lambda)}{2(n_{1}-1)}+\frac{\pi_{ik}(\lambda)}{2(n_{2}-1)}))-\varphi(\gamma_{ jlik}+\frac{\pi_{jl}(\lambda)}{2(n_{1}-1)}+\frac{\pi_{jl}(\lambda)}{2(n_{2}-1)}))\)
5\(\mathrm{LB}^{*}\leftarrow\max[\mathrm{LB}^{*},Z_{\mathrm{lb}}(\lambda)]\)
6\(\mathrm{UB}^{*}\gets Z_{\mathrm{LD}}(\lambda)\) return\([\mathrm{LB}^{*},\mathrm{UB}^{*}]\)
```  
**Algorithm 2**DualDescent\((\lambda,L)\)