steps

Input: A, b and $\tilde{c}$ ; and 𝒟 is non-empty and P₀ is inside 𝒟

Output: OptPt & OptVal

0

Construct the Facet Tableau $\left[\tau \right]$ from A, b and $\tilde{c}$

$P=P_0$ ; $g_0=-b$

1

$d_j=P^{\text{T}}{\tau }_j-c_j$ for $j=1,\cdots ,m+n$ }

2

$\sigma =\left\{j|\left|d_j\right|<\delta \right\}$ ; % δ is a small constant

${\sigma }^{*}=\sigma$ ; % ${\sigma }^{*}$ is set of blocking facet

3

while (true)

4

if $\sigma \ne \varphi$ % compute $g,g{\downarrow }_{{\sigma }_j^c}$ and update ${\sigma }^{*}$

$\left[g,g{\downarrow }_{{\sigma }_j^c},{\sigma }^{*}\right]$ = Gradient Select( $g_0,\sigma ,\left[\tau \right],P,c$ )

else $g=g_0$

5

if $\left|{\sigma }^{*}\right|==m$

$OptPt=P;OptVal=P^{\text{T}}b$ ; return (OptPt, OptVal)

else $\sigma ={\sigma }^{*}$

6

$t_j=\frac{c_j{P}^{\text{T}}{\tau }_j}{g^{\text{T}}{\tau }_j}$ ; for $j\in \left\{1,2,\cdots ,m+n\right\}\backslash \sigma$

$j^{*}=\arg {\min }_j\left\{t_j|t_j>0\right\}$ ;

$Q=P+t_{j^{*}}g$ ; $P=Q$

7

$\sigma ={\sigma }^{*}\cup \left\{i|\left|t_i-t_{j^{*}}\right|<ϵ\right\}$ % update blocking facets

8

end