CO—αβ algorithm
Co-αβ algorithm
For the balance transportation problem $\sum_{i}a_{i}=\sum_{j}b_{j}$
$$P:\quad \min \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$$ $$s.t.\quad \sum_{j=1}^{n} x_{ij}=a_i \quad i\in \{1\cdots m\}$$ $$\sum_{i=1}^{m} x_{ij}=b_j \quad j\in \{1\cdots n\}$$ $$x_{ij}\ge 0$$
the dual problem is
$$DP:\quad \max \sum_{i=1}^{m} a_i\alpha_i +\sum_{j=1}^{n} b_j\beta_j$$ $$\alpha_i+\beta_j \le c_{ij} \quad i\in \{1\cdots m\}\quad j\in \{1\cdots n\}$$
Set the initial solution of the dual problem as
$$\alpha_i=0 \quad i\in \{1,\cdots m\}$$ $$\beta_j=\min\limits_{i} c_{ij} \quad j\in \{1,\cdots n\}$$
By the rule of prime dual algorithm we set the set
$$IJ=\{(i,j)\in I\times J \mid \alpha_i+\beta_j = c_{ij}\}$$
And we set the restricted primal
$$RP:\quad \min \mathcal{l}=\sum_{i=1}^{m+n} x_i^a$$
$$s.t.\quad \sum_{\substack{j:(i,j)\in IJ}} x_{ij}+x_i^a =a_i \quad i\in \{1\cdots m\}$$
$$\sum_{\substack{i:(i,j)\in IJ}} x_{ij}+x_{m+j}^a =b_j \quad j\in \{1\cdots n\}$$
$$x_i^a \ge0 \quad i\in \{1\cdots m+n\}$$ $$x_{ij}\ge0$$
Same as prime dual algorithm. If the RP $\min \mathcal{l}=0$, then we get the optimal solution, else, we want to do iteration and let the objective function of DP bigger. We change the RP into a max-flow problem to help us solve it.
$$\sum_{i=1}^{m}\sum_{\substack{j:(i,j)\in IJ}} x_{ij}+\sum_{j=1}^{n}\sum_{\substack{i:(i,j)\in IJ}} x_{ij}+\sum_{i=1}^{m}x_i^a+\sum_{j=1}^{n}x_{m+j}^a=\sum_{i}a_i+\sum_{j}b_j$$
$$\mathcal{l}=\sum_{i=1}^{m+n}x_i^a=\sum_{i}a_i+\sum_{j}b_j -2\sum_{IJ}x_{ij}$$
Since $\sum a_i,\sum b_j$ is constant, so equivalent to $\max \mathcal{l}=\sum_{IJ}x_{ij}$
The equal problem is
$$RP'\quad \max \mathcal{l}=\sum_{IJ}x_{ij}$$
$$s.t.\quad \sum_{\substack{j:(i,j)\in IJ}} x_{ij} \le a_i \quad i\in \{1,\cdots,m\}$$
$$\sum_{\substack{i:(i,j)\in IJ}} x_{ij} \le b_j \quad j\in \{1,\cdots,n\}$$
$$x_{ij}\ge0 \quad (i,j)\in IJ$$
Let $x_{ij}=f(i,j) \quad \forall(i,j)\in IJ$ and the network like
$$f(s,i)=\sum_{\substack{j:(i,j)\in IJ}} x_{ij} \quad i\in I,\qquad f(j,t)=\sum_{\substack{i:(i,j)\in IJ}} x_{ij} \quad j\in J$$
The network has a source $s$ and a sink $t$: for every $i\in I$ an arc $s\to A_i$ of capacity $a_i$, for every $(i,j)\in IJ$ an arc $A_i\to B_j$ of capacity $+\infty$, for every $j\in J$ an arc $B_j\to t$ of capacity $b_j$:
$$s\xrightarrow{\ a_i\ }A_i\xrightarrow{\ \infty\ }B_j\xrightarrow{\ b_j\ }t \qquad ((i,j)\in IJ)$$
$$\begin{array}{ccccccc} s & \xrightarrow{\ a_1\ } & A_1 & \xrightarrow{\ \infty\ } & B_1 & \xrightarrow{\ b_1\ } & t\\ & & \vdots & & \vdots & & \\ s & \xrightarrow{\ a_m\ } & A_m & \xrightarrow{\ \infty\ } & B_n & \xrightarrow{\ b_n\ } & t \end{array}$$
Note the middle arcs run over all $(i,j)\in IJ$, not only over $i=j$.
The RP’ and the max-flow problem in this network are equivalent
proof:
$$\mathcal{l}=\sum_{IJ}x_{ij}=\sum_{IJ}f(i,j)=\sum_{i\in I}\left(\sum_{\substack{j:(i,j)\in IJ}}f(i,j)\right)=\sum_{i\in I}f(s,i)=v(f)$$
so the objective function are same
now prove if $x_{ij}$ is feasible solution in RP’ then it is feasible in the network
If $i\in I$ then $f(s,i)=\sum_{\substack{j:(i,j)\in IJ}}x_{ij}\le a_i$, if $j\in J$ then $f(j,t)=\sum_{\substack{i:(i,j)\in IJ}}x_{ij}\le b_j$
So the capacity constraints are satisfied and we have
$$\forall i\in I \quad f(s,i)=\sum_{\substack{j:(i,j)\in IJ}}x_{ij}=\sum_{\substack{j:(i,j)\in IJ}}f(i,j)$$
$$\forall j\in J \quad f(j,t)=\sum_{\substack{i:(i,j)\in IJ}}x_{ij}=\sum_{\substack{i:(i,j)\in IJ}}f(i,j)$$
So the conservation law are satisfied . So it is a feasible solution in the max-flow problem
now prove a feasible solution in the max-flow problem is a feasible solution in RP’
$$\sum_{\substack{j:(i,j)\in IJ}}x_{ij}=\sum_{\substack{j:(i,j)\in IJ}}f(i,j)=f(s,i)\le a_i \quad \forall i\in I$$
$$\sum_{\substack{i:(i,j)\in IJ}}x_{ij}=\sum_{\substack{i:(i,j)\in IJ}}f(i,j)=f(j,t)\le b_j \quad \forall j\in J$$
So two problem are equivalent
Also $\mathcal{l}=0$ means
$$\mathcal{l}=\sum_{i}a_i+\sum_{j}b_j -2v(f)=0 \iff v(f)=\sum_{i\in I}a_i$$
So we can use Ford and Fulkerson algorithm to solve the max flow problem and get optimal solution $f(i,j)$ then
$1^\circ$ If the optimal solution s.t. $f(s,i)=a_i$ for $\forall i\in I$ then the optimal solution $x=x_{ij}$ has been found
$$x_{ij}= \begin{cases} f(i,j) & \text{if }(i,j)\in IJ\\ 0 & \text{else} \end{cases}$$
$2^\circ$ else we need the dual restricted problem primal set optimal solution $(\bar{\alpha},\bar{\beta})$ and use it to update $(\alpha,\beta)$
To find $(\bar{\alpha},\bar{\beta})$, define
$$I^*=\{i\in I \mid i \text{ is labelled in last iteration}\}$$
$$J^*=\{j\in J \mid j \text{ is labelled in last iteration}\}$$
By the rules of Ford-Fulkerson algorithm,
$$i\in I^* \Rightarrow j\in J^* \quad \forall(i,j)\in IJ$$
If $(i,j)\in IJ$, $i\notin I^*$, $j\in J^*$ then $f(i,j)=0$
then
$$\bar{\alpha}_i= \begin{cases} 1 & :i\in I^*\\ -1 & :i\notin I^* \end{cases}$$ $$\bar{\beta}_j= \begin{cases} -1 & j\in J^*\\ 1 & j\notin J^* \end{cases}$$
is the optimal solution of DRP
proof:
$$DRP:\quad \max \sum_{i=1}^{m} a_i\alpha_i +\sum_{j=1}^{n} b_j\beta_j =W(\alpha_i,\beta_j)$$
$$s.t.\quad \alpha_i+\beta_j \le0 \quad (i,j)\in IJ$$
$$\alpha_i \le1 \quad i\in I$$
$$\beta_j \le1 \quad j\in J$$
Since if $i\in I^* \Rightarrow j\in J^*$ so $\alpha_i+\beta_j \le0 \quad (i,j)\in IJ$
$\Rightarrow (\bar{\alpha},\bar{\beta})$ is feasible solution for DRP
$$W(\bar{\alpha},\bar{\beta})=\sum_{i\in I^*}a_i -\sum_{i\notin I^*}a_i -\sum_{j\in J^*}b_j +\sum_{j\notin J^*}b_j$$
Below, $\sum_{I^*}$ means $\sum_{i\in I^*}$ and $\sum_{\overline{I^*}}$ means $\sum_{i\notin I^*}$, and similarly for $J^*$:
$$ \begin{align*} \mathcal{l}&=\sum_{i}a_i+\sum_{j}b_j -2\sum_{IJ}x_{ij}\\ &=\sum_{i}a_i+\sum_{j}b_j -2\sum_{IJ}f(i,j)\\ &=\sum_{i}a_i+\sum_{j}b_j -2\left(\sum_{I^*}\sum_{J^*}f(i,j)+\sum_{I^*}\sum_{\overline{J^*}}f(i,j)+\sum_{\overline{I^*}}\sum_{J^*}f(i,j)+\sum_{\overline{I^*}}\sum_{\overline{J^*}}f(i,j)\right)\\ &=\sum_{i}a_i+\sum_{j}b_j -2\left(\sum_{I^*}\sum_{J^*}f(i,j)+\sum_{\overline{I^*}}\sum_{\overline{J^*}}f(i,j)\right)\\ &=\sum_{i}a_i+\sum_{j}b_j -2\left(\sum_{J^*}b_j+\sum_{\overline{I^*}}a_i\right)\\ &=\sum_{I^*}a_i+\sum_{\overline{I^*}}a_i+\sum_{J^*}b_j+\sum_{\overline{J^*}}b_j -2\sum_{J^*}b_j -2\sum_{\overline{I^*}}a_i\\ &=\sum_{\overline{I^*}}a_i -\sum_{I^*}a_i +\sum_{\overline{J^*}}b_j -\sum_{J^*}b_j \end{align*} $$
So $\mathcal{l}=W(\bar{\alpha},\bar{\beta})$, so $(\bar{\alpha},\bar{\beta})$ is optimal solution
Then we need update $\alpha_i,\beta_j$
$$ \begin{align*} \theta&=\min\left\{\frac{c_{ij}-\alpha_i-\beta_j}{2}\mid \overline{\alpha}_i+\overline{\beta}_j>0\right\}\\ &=\min\left\{\frac{c_{ij}-\alpha_i-\beta_j}{2}\mid i\in I^*,\ j\notin J^*\right\} \end{align*} $$
So
$$\alpha_i=\alpha_i+\theta \bar{\alpha}_i= \begin{cases} \alpha_i+\theta & i\in I^*\\ \alpha_i-\theta & i\notin I^* \end{cases}$$
$$\beta_j=\beta_j+\theta \bar{\beta}_j= \begin{cases} \beta_j-\theta & j\in J^*\\ \beta_j+\theta & j\notin J^* \end{cases}$$