Theorem1. Complementary slackness Suppose $x\in M_p\ \ \pi\in M_D$ then $x\in M_p^{opt}\ \ \pi\in M_D^{opt}$ iff $$\forall i,j \quad \big(c_j-(A^\top\pi)_j\big)\cdot x_j=0=\pi_i\big((Ax)_i-b_i\big)$$

proof By the rules of dualisation $$\min f(x)=c^\top x \qquad \max g(\pi)=b^\top\pi$$ $$(Ax)_i=b_i \quad i\in I \qquad \pi_i\lessgtr0$$ $$(Ax)_i\ge b_i \quad i\in \bar I \qquad \pi_i\ge0$$ $$x_j\ge0 \quad j\in J \qquad (A^\top\pi)_j\le c_j$$ $$x_j\lessgtr0 \quad j\in \bar J \qquad (A^\top\pi)_j = c_j$$

So $x_j\cdot\big(c_j-(A^\top\pi)_j\big)\ge0 \quad \pi_i\big((Ax)_i-b_i\big)\ge0$

Set $u_j = x_j\cdot\big(c_j-(A^\top\pi)_j\big) \quad v_i = \pi_i\big((Ax)_i-b_i\big)$

$$u=\sum_j u_j \quad v=\sum_i v_i$$

$$ \begin{align*} u+v&=\sum_j x_j\cdot c_j -\sum_j x_j\cdot(A^\top\pi)_j +\sum_i \pi_i(Ax)_i -\sum_i\pi_i b_i \\ &=c^\top x -\pi^\top Ax +\pi^\top Ax -b^\top\pi \\ &=c^\top x -b^\top\pi \end{align*} $$

So $x\in M_p^{opt},\ \pi\in M_D^{opt} \iff c^\top x =b^\top\pi \iff \forall i,j \ u_j=v_i=0$

To solve $$P:\quad \min f(x)=c^\top x$$ $$s.t.\quad (Ax=b)$$ $$x\ge0$$

We have $$D:\quad \max g(\pi)=b^\top\pi$$ $$A^\top\pi\le c$$

Begin with initial a feasible solution of D $\pi_1$

We can get a set $$J=\{j\mid (A^\top\pi)_j = c_j\}$$

For $x_j$ s.t. $j\notin J$ set $x_j=0$ then the problem $P$ become $$P'\quad \min f(x)=c^\top x$$ $$\sum_{j\in J} a_{ij}x_j =b_i \quad i\in\{1,\dots,m\}$$ $$x_j\ge0 \quad j\in J$$

Set new variable auxiliary $x_i^a$ then the restricted primal problem is $$RP:\quad \min \ell=\sum_{i=1}^m x_i^a$$ $$s.t.\quad \sum_{j\in J} a_{ij}x_j +x_i^a =b_i \quad i\in\{1,\dots,m\}$$ $$x_i^a \ge0 \quad i\in\{1,\dots,m\}$$ $$x_j\ge0 \quad j\in J$$

Since let $x_j=0,j\in J,\ x_i^a=b_i$ is a feasible solution of RP so $M_{RP}\ne\emptyset$ and $\min\sum_i x_i^a \ge0$ so RP $\exists$ optimal solution

And $\min\ell=0$ iff $P'$ has feasible solution

Since $x_i^a\ge0 \quad \ell=0 \implies x_i^a=0 \implies \sum_{j\in J}a_{ij}x_j =b_i \implies$ feasible solution

So if $\min\ell=0$ then $$j\in \bar J$$ $$\sum_{j\in J} a_{ij}x_j =b_i \quad i\in\{1,\dots,m\}$$ $$j\notin J \quad x_j=0$$

then let $\bar x=(x_j)$

$$A\bar x=\left(\sum_{j\in J}a_{ij}x_j\right)=(b_i)=b$$

So $\bar x\in M_p$ and $\pi_1\in M_D$ $\big((A^\top\pi)_j-c_j\big)x_j=0$

Since when $j\in J\ (A^\top\pi)_j=c_j$ when $j\notin J\ x_j=0$

and since $(Ax=b)$ so $\big((Ax)_i-b_i\big)\pi_i=0$

So $\big((A^\top\pi)_j-c_j\big)x_j=0=\big((Ax)_i-b_i\big)\pi_i$

by Theorem1. $\bar x,\ \pi_1$ is the optimal solution of $P$ and $D$

So we want to find the $\min\ell=0$

Set the dual problem of RP : DRP $$DRP:\quad \max b^\top\overline{\pi}$$ $$s.t.\ (A^\top\overline{\pi})_j\le0 \quad j\in J \iff \begin{bmatrix}A^\top\\I\end{bmatrix}\overline{\pi}\le\begin{bmatrix}0\\1\end{bmatrix}$$

Assume we can solve the DRP problem, the optimal solution is $\overline{\pi}$

So by strong dual theorem

$b^\top\overline{\pi}=\ell>0$ (if $\ell=0$ then we get the optimal solution)

then $\pi_2=\pi_1+\theta\overline{\pi}$

$b^\top\pi_2 =b^\top\pi_1+\theta b^\top\overline{\pi} >b^\top\pi_1,\ \theta$ should be positive

And $A^\top\pi_2 =A^\top\pi_1+\theta A^\top\overline{\pi} \le A^\top\pi_1 \le C$ if $A^\top\overline{\pi}\le0$

So $\pi_2$ is still the feasible solution of the problem $D$

if $A^\top\overline{\pi}>0$ we still want $\pi_2$ in the feasible space then we need $$\theta \le \frac{c_j-(A^\top\pi_1)_j}{(A^\top\overline{\pi})_j} \quad \text{if }(A^\top\overline{\pi})_j>0 \ \ j\notin J$$

So $\theta=\min\left\{ \frac{c_j-(A^\top\pi_1)_j}{(A^\top\overline{\pi})_j} \bigg| (A^\top\overline{\pi})_j>0 \right\}$

For the case $\forall j\notin J\ (A^\top\overline{\pi})_j\le0$

then let $\theta\to+\infty$ since $b^\top\overline{\pi}>0$

So $\pi(\theta)=\pi+\theta\overline{\pi}$ still is feasible solution and

$b^\top\pi(\theta)=b^\top\pi+\theta b^\top\overline{\pi}\to +\infty$

by weak dual theorem so $M_p=\emptyset$

So we get the algorithm

For $\min c^\top x$ $$(Ax=b)$$ $$x\ge0$$

find dual problem feasible $\pi_k$

Set $J=\{j\mid (A^\top\pi_k)_j=c_j\}$

Solve RP $\min \ell=\sum_i x_i^a$ $$\sum_{j\in J} a_{ij}x_j +x_i^a =b_i$$ $$x_i^a \ge0$$ $$x_j \ge0$$

Get the optimal solution , if $\min\ell=0$ then that $x_j,j\in J$ is optimal for $P$, if not , find optimal solution of DRP $$\max w=\pi^\top b$$ $$s.t.\ (A^\top\overline{\pi})_j \le0 \quad j\in J$$ $$\overline{\pi}_i\le1 \quad i\in[1\cdots m]$$

if $(A^\top\overline{\pi})_j\le0$ for $\forall j\notin J$ then stop $M_p=\emptyset$

if not set $$\theta=\min\left\{ \frac{c_j-(A^\top\pi_k)_j}{(A^\top\overline{\pi})_j} \bigg|(A^\top\overline{\pi})_j>0 \right\}$$

and $\pi_{k+1}:=\pi_k+\theta\overline{\pi}$

then go back