## 3 Methods
### Solving Strategies
#### 3.1.2 Dual Descent  
In this section we derive a dual descent method which is an extension of the one presented in [22]. The dual descent method takes as a starting point the dual of \(Z_{\mathrm{LD}}(\lambda)\):  
\[Z_{\mathrm{LD}}(\lambda) = \min_{\alpha,\beta}\quad\sum_{i}\alpha_{i}+\sum_{k}\beta_{k}\] (21) s.t. \[\alpha_{i}+\beta_{k}\geq c_{ik}+v_{ik}(\lambda) \forall i,k \tag{22}\] \[\alpha_{i}\geq 0 \forall i\] (23) \[\beta_{k}\geq 0 \forall k \tag{24}\]  
where the dual of \(v_{ik}(\lambda)\) is  
\[v_{ik}(\lambda) = \min_{\mu,\
u}\quad\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}\] (25) s.t. \[\mu_{j}^{ik}+\
u_{l}^{ik}\geq w_{ikjl}+\lambda_{ikjl} \forall j,l,\ j>i,l\
eq k \tag{26}\] \[\mu_{j}^{ik}+\
u_{l}^{ik}\geq w_{ikjl}-\lambda_{jlik} \forall j,l,\ j<i,l\
eq k\] (27) \[\mu_{j}^{ik}\geq 0 \forall j\] (28) \[\
u_{l}^{ik}\geq 0 \forall l \tag{29}\]  
Suppose that for a given \(\lambda^{t}\) we have computed dual variables \((\alpha,\beta)\) solving Problem (21) with objective value \(Z_{\mathrm{LD}}(\lambda^{t})\), as well as dual variables \((\mu^{ik},\
u^{ik})\) yielding values \(v_{ik}(\lambda)\) to Problems (25). The goal now is to find \(\lambda^{t+1}\) such that the resulting bound is better or just as good, i.e. \(Z_{\mathrm{LD}}(\lambda^{t+1})\leq Z_{\mathrm{LD}}(\lambda^{t})\). We prevent the bound from increasing, by ensuring that the dual variables \((\alpha,\beta)\) remain feasible for Problem (21). This we can achieve by considering the slacks: \(\pi_{ik}(\lambda)=\alpha_{i}+\beta_{k}-c_{ik}-v_{ik}(\lambda)\). Thus, for \((\alpha,\beta)\) to remain feasible, we can only allow every \(v_{ik}(\lambda^{t})\) to increase by as much as \(\pi_{ik}(\lambda^{t})\). We can achieve such an increase by considering Linear Programs (25) and their slacks defined as  
\[\gamma_{ikjl}(\lambda)= \begin{cases}\mu_{j}^{ik}+\
u_{l}^{ik}-w_{ikjl}+\lambda_ {ikjl},&\text{if $j>i$,}\\ \mu_{j}^{ik}+\
u_{l}^{ik}-w_{ikjl}-\lambda_{jlik},&\text{if $j<i$,}\end{cases}  \forall j,l,\ j\
eq i,l\
eq k \tag{30}\]  
and update the multipliers in the following way. **Lemma 1**. : _The adjustment scheme below yields solutions to Linear Programs (25) with objective values \(v_{ik}(\lambda^{t+1})\) at most \(\pi_{ik}(\lambda^{t})+v_{ik}(\lambda^{t})\) for all \(i,k\)._  
\[ \begin{split}\lambda_{ikjl}^{t+1}=\lambda_{ikjl}^{t}& +\varphi_{ikjl}\left[\gamma_{ikjl}(\lambda^{t})+\tau_{ik}\left( \frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{ik}(\lambda^{t})\right] \\ &-\varphi_{jlik}\left[\gamma_{jlik}(\lambda^{t})+\tau_{jl}\left( \frac{1}{2(n_{1}-1)}+\frac{1}{2(n_{2}-1)}\right)\pi_{jl}(\lambda^{t})\right] \end{split}  \tag{31}\]  
_for all \(j,l,\,i<j,k\
eq l\), where \(n_{1}=|V_{1}|\), \(n_{2}=|V_{2}|\), and \(0\leq\varphi_{ikjl},\tau_{jl}\leq 1\) are parameters._  
Proof. : We prove the lemma by showing that for any \(i,k\) there exists a feasible solution \((\mu^{\prime ik},\
u^{\prime ik})\) to Problem (25) whose objective value \(v_{ik}(\lambda^{t+1})\) is at most \(\pi_{ik}(\lambda^{t})+v_{ik}(\lambda^{t})\). Let \((\mu^{ik},\
u^{ik})\) be the solution to Problem (25) given multipliers \(\lambda^{t}\). We claim that setting  
\[ \begin{split}\mu_{j}^{\prime ik}&=\mu_{j}^{ik}+ \frac{\pi_{ik}(\lambda^{t})}{2(n_{1}-1)}\qquad\forall j,\ j\
eq i\\ \
u_{l}^{\prime ik}&=\
u_{j}^{ik}+\frac{\pi_{ik}( \lambda^{t})}{2(n_{2}-1)}\qquad\forall l,\ l\
eq k\end{split} \]  
results in a feasible solution to Problem (25) given multipliers \(\lambda^{t+1}\). We start by showing that Constraints (26) and (27) are satisfied. Equation (31) implies the following bounds on \(\lambda^{t+1}\):  
\[