steps

Input: A, b and $\tilde{c}$

Output: either V as the optimal point & V^Tb as optimal value or declare the LP problem as infeasible.

0

$V=V_0=\left(0,0,\cdots ,0\right)$ % the coordinate cone;

$r_1=\left(1,0,\cdots ,0\right),r_2=\left(0,1,\cdots ,0\right),\cdots ,r_m=\left(0,0,\cdots ,1\right)$ ;

1

while (true)

2

% For all facets not in C & reject V, find one that rejects V the least.

$\bar{\Delta }=\left\{1:\left(m+n\right)\right\}\backslash \Delta$ ; % $\bar{\Delta }$ are facets not in C

$j^{*}=\arg {\min }_j\left\{e_j|e_j=\left(V^{\text{T}}{\tau }_{\bar{\Delta }\left(j\right)}-c_{\bar{\Delta }\left(j\right)}\right),j\in \bar{\Delta }\right\}$

3

if $e_{j^{*}}\ge 0$ return (V & V^Tb) as optimal vertex & optimal value

else $J^{*}=\bar{\Delta }\left(j^{*}\right)$ ; % j^* is the facet index to enter

4

$t_i=\frac{c_{J^{*}}{V}^{\text{T}}{\tau }_{J^{*}}}{r_i^{\text{T}}{\tau }_{J^{*}}};i=1,\cdots ,m$ ; $i=1,\cdots ,m$ }; $q_i=V+t_i{r}_i$ ;

5

if $\left(t_i<0\forall i=1,\cdots ,m\right)$ return(“LP is infeasible”)

else % For all the real cuts q_i,, find the q_I* that is closest to V

$I^{*}=\arg {\min }_i\left\{q_i^{\text{T}}b|t_i>0\right\}$ % I^* is the facet index to leave

6

% Form new cone C_k+1 by updating V_k+1; edge vectors and facets

$V_{k+1}=q_{I^{*}}$ _; $r_i=\{\begin{array}{ll}{r}_i\hfill & i=I^{*}\hfill \\ sign\left(t_i\right)\left[q_i-V_{k+1}\right]\hfill & i\ne I^{*}\hfill \end{array}$

$\text{Δ}\left(I^{*}\right)=J^{*}$ _;

7

end