The Pivot Adaptive Method for Solving Linear Programming Problems

Saliha Belahcene¹, Philippe Marthon², Mohamed Aidene³

¹Mouloud Mammeri University of Tizi-Ouzou, Tizi-Ouzou, Algeria.
²Site ENSEEIHT de l’IRIT, Université Fédérale Toulouse Midi-Pyrénées, Toulouse, France.
³L2CSP Laboratory Design and Control Systems Production, Tizi-Ouzou, Algeria.

DOI: 10.4236/ajor.2018.82008                

Abstract

A new variant of the Adaptive Method (AM) of Gabasov is presented, to minimize the computation time. Unlike the original method and its some variants, we need not to compute the inverse of the basic matrix at each iteration, or to solve the linear systems with the basic matrix. In fact, to compute the new support feasible solution, the simplex pivoting rule is used by introducing a matrix that we will define. This variant is called “the Pivot Adaptive Method” (PAM); it allows presenting the resolution of a given problem under the shape of successive tables as we will see in example. The proofs that are not given by Gabasov will also be presented here, namely the proofs for the theorem of the optimality criterion and for the theorem of existence of an optimal support, and at the end, a brief comparison between our method and the Simplex Method will be given.

Keywords

Optimization, Linear Programming, Simplex Method, Adaptive Method

1. Introduction

As a branch of mathematics, linear programming is the domain that had the most successful in optimization [1] [2] [3] [4] [5] . Since its formulation from 1930 to 1940 and the development of the Simplex method of Dantzig in 1949 [1] [6] , researchers in various fields have been led to formulate and solve linear problems.

Although, the Simplex algorithm is often effective in practice, the fact that it is not a polynomial algorithm, as shown by Klee and Minty [7] , has incited researchers to propose other algorithms and led to the birth of the interior point algorithms.

In 1979, L. Khachiyan proposed the first polynomial algorithm for linear programming [8] ; it is based on the ellipsoid method, studied by Arkadi Nemirovski and David B. Yudin, a preliminary version of which having been introduced by Naum Z. Shor. Unfortunately, this ellipsoid method has a poor efficiency.

In 1984, N. K. Karmakar published an interior point algorithm which has a polynomial convergence [9],and this caused a renewed interest to interior point methods, as well in linear programming that in nonlinear programming [10] [11] [12] [13] [14] .

Gabasov and Kirillova have generalized the Simplex method in 1995 [15] [16] [17] , and developed the Adaptive Method (AM), a primal-dual method, for linear programming with bounded variables. As the Simplex method, the Adaptive Method is a support method, but it can start from any support (base) and any feasible solution and can move to the optimal solution by interior or boundary points; this method was extended, later, to solve general linear and convex problems [18] [19] [20], and also optimal control problems [21] .

In linear programming, several variants of the AM have been proposed. They generally address the problem of initialization of the method and the choice of the direction [22] [23] .

In this work, a new variant of the adaptive method called “Pivot adaptive method” (PAM) is presented. Unlike the original method and its variants, we need not to compute the inverse of the basic matrix at each iteration [16] , or to solve the linear systems with the basic matrix [23] . In fact, to compute the new feasible solution and the new support, we only need compute the decomposition of vectors columns of the matrix of the problem in the current basis. For this computation we use the simplex pivoting rule [4] by introducing a new matrix GAMMA which allows to minimize the computation time. This new variant of adaptive method allows us to present the resolution of a given problem under the shape of successive tables (as is done with the Simplex method) as we will see in example. The proofs for the theorem of the optimality criterion and for the theorem of existence of an optimal support that are not given by Gabasov [16] will be presented here, and without giving too many details a brief comparison between our method and the Simplex method will be given at the end of this article.

The paper is organized as follows. In Section 2, after giving the statement of the problem, some important definitions are given. In Section 3, we describe step by step the “Pivot Adaptive Method” and in parallel the proofs of the corresponding theorems are given. In Section 4, an example will be solved to illustrate the PAM, and more details will be given to explain how present the resolution under the shape of successive tables. In Section 5, we give a brief comparison between the PAM and the Simplex Method by solving the Klee-Minty problem. Section 6, concludes the paper.

2. Statement of the Problem and Definitions

In this article we consider the primal linear programming problem with bounded variables presented in the following standard form:

$\left(P\right)\{\begin{array}{l}\max F\left(x_1,x_2,\cdots ,x_n\right)={\displaystyle \underset{j=1}{\overset{j=n}{\sum }}}{c}_j{x}_j\hfill \\ {\displaystyle \underset{j=1}{\overset{j=n}{\sum }}}{a}_{ij}{x}_j=b_i,i\in I\hfill \\ d_j^{-}\le x_j\le d_j^{+},j\in J.\hfill \end{array}$ (1)

where: $J=\left\{1,\cdots ,n\right\}$ is the index set of the variables $x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n$ , $I=\left\{1,\cdots ,m\right\}$ is the index set of the parameters $b_1\mathrm{,}{b}_2\mathrm{,}\cdots \mathrm{,}{b}_m$ (corresponds to the constraints), put: $J=J_B\cup J_N$ , $J_B\cap J_N=\varnothing$ , $\left|J_B\right|=m$ , and introduce the vectors:

・ $x=x\left(J\right)=\left(x_j,j\in J\right)=\left(x_1,x_2,\cdots ,x_n\right)=\left(\begin{array}{c}{x}_B\\ x_N\end{array}\right)$ , with: $x_B=x\left(J_B\right)=\left(x_j,j\in J_B\right)$ , $x_N=x\left(J_N\right)=\left(x_j,j\in J_N\right)$ .

・ $c=c\left(J\right)=\left(c_j,j\in J\right)=\left(c_1,c_2,\cdots ,c_n\right)=\left(\begin{array}{c}{c}_B\\ c_N\end{array}\right)$ , with: $c_B=c\left(J_B\right)=\left(c_j,j\in J_B\right)$ , $c_N=c\left(J_N\right)=\left(c_j,j\in J_N\right)$ .

・ $b^{\text{T}}=b^{\text{T}}\left(J\right)=\left(b_i\mathrm{,}i\in I\right)=\left(b_1\mathrm{,}{b}_2\mathrm{,}\cdots \mathrm{,}{b}_m\right)$ .

・ $d^{-}=d^{-}\left(J\right)=\left(d_j^{-}\mathrm{,}j\in J\right)=\left(d_1^{-}\mathrm{,}{d}_2^{-}\mathrm{,}\cdots \mathrm{,}{d}_n^{-}\right)\mathrm{<mo>\; ;\; </mo>}\Vert d^{-}\Vert \mathrm{<mo>\; <\; </mo>}+\infty$ .

・ $d^{+}=d^{+}\left(J\right)=\left(d_j^{+},j\in J\right)=\left(d_1^{+},d_2^{+},\cdots ,d_n^{+}\right);\Vert d^{+}\Vert <+\infty$ .

and the $\left(m\times n\right)$ matrix

・ $A=A\left(I,J\right)=\left(a_{ij},i\in I,j\in J\right)=\left(a_1,a_2,\cdots ,a_n\right)=\left(\begin{array}{c}{A}_1^{\text{T}}\\ ⋮\\ A_m^{\text{T}}\end{array}\right)$ , with: $a_j=\left(\begin{array}{c}{a}_{1j}\\ ⋮\\ a_{mj}\end{array}\right)$ ,

$j\in J$ ( $a_j$ : the j^th column of the matrix A), and $A_i^{\text{T}}=\left(a_{i1}\mathrm{,}{a}_{i2}\mathrm{,}\cdots \mathrm{,}{a}_{in}\right)\mathrm{,}i\in I$ ( $A_i^{\text{T}}$ : the i^th row of the matrix A), $A=\left(A_B/A_N\right)$ , $A_B=A\left(I,J_B\right)$ , $A_N=A\left(I,J_N\right)$ .

We assume that $rank\left(A\right)=m<n$ . Then the problem (1) takes the following form:

$\left(P\right)\{\begin{array}{l}maxF\left(x\right)=c^{\text{T}}x\hfill \\ Ax=b\hfill \\ d^{-}\le x\le d^{+}\hfill \end{array}$ (2)

$Ax=b$ are called the general constraints of (P).

Denote the feasible region of (P) as: $H=\left\{x\in R^n,Ax=b,d^{-}\le x\le d^{+}\right\}$ .

2.1. Definition 1

Each vector of the set H is called a feasible solution of (P).

2.2. Definition 2

Any vector $x\in R^n$ that satisfies the general constraints $Ax=b$ of the problem (P) is called a pseudo-feasible solution.

2.3. Definition 3

A feasible solution $x^0$ is called optimal if: $F\left(x^0\right)=c^{\text{T}}{x}^0=\underset{x\in H}{\max }{c}^{\text{T}}x$ .

2.4. Definition 4

For given value $ϵ\ge 0$ , the solution $x^{ϵ}$ is called an ò-optimal (or suboptimal) if: $\left(F\left(x^0\right)-F\left(x^{ϵ}\right)\right)\le ϵ$ , where $x^0$ is an optimal solution for the problem (P).

2.5. Definition 5

The set of m indices $J_B\subset J$ ( $\left|J_B\right|=m$ ) is called a support of (P) if the submatrix $A_B=A\left(I\mathrm{,}{J}_B\right)$ is non-singular ( $det{A}_B\ne 0$ ), then the set $J_N=J\backslash J_B$ of ( $n-m$ ) indices is called non-support, $A_B$ is the matrix support, and $A_N=A\left(I\mathrm{,}{J}_N\right)$ is the matrix non-support.

2.6. Definition 6

The pair $\left\{x\mathrm{,}{J}_B\right\}$ formed by a feasible solution x and the support $J_B$ is called a support feasible solution (SF-solution).

2.7. Definition 7

The SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ is called non-degenerate if: $d_j^{-}<x_j<d_j^{+},\forall j\in J_B$ .

Recall that, unlike the Simplex Method in which the feasible solution x and the basic indices $J_B$ are related intimately, in the adaptive method there are independent.

3. Optimality Criterion

For the smooth running of calculations, in the rest of the article, we assume that the sets $J_B$ and $J_N$ are vectors of indices (i.e.: the order of indices in these sets is important and must be respected).

3.1. Formula of the Objective Value Increment

Let $\left\{x\mathrm{,}{J}_B\right\}$ be the initial SF-solution of the problem (P), and $\bar{x}=\bar{x}\left(J\right)=\left(\begin{array}{c}{\bar{x}}_B\\ {\bar{x}}_N\end{array}\right)$ an arbitrary pseudo-feasible solution of (P). We set $\Delta x=\Delta x_B+\Delta x_N=\bar{x}-x$ , then the increment of the objective function value is given by:

$\Delta F\left(x\right)=F\left(\bar{x}\right)-F\left(x\right)=c^{\text{T}}\bar{x}-c^{\text{T}}x=c^{\text{T}}\Delta x=c_B^{\text{T}}\Delta x_B+c_N^{\text{T}}\Delta x_N$ (3)

and since:

$A\Delta x=A_B\Delta x_B+A_N\Delta x_N=A\bar{x}-Ax=0$ (4)

then

$\Delta x_B=-A_B^{-1}{A}_N\Delta x_N$ (5)

Substituting the vector $\Delta x_B$ in (3) we get:

$\Delta F\left(x\right)=\left(c_N^{\text{T}}-c_B^{\text{T}}{A}_B^{-1}{A}_N\right)\Delta x_N$ (6)

Here, we define the m-vector of multipliers y as follows:

$y^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}$ (7)

In [16] , Gabasov defines the support gradient and noted it D as: ${\Delta }^{\text{T}}=y^{\text{T}}A-c^{\text{T}}$ , but he also recognizes that for every $k\in J_N$ , the k^th support derivative is equal to $-{\Delta }_k=c_k-y^{\text{T}}{a}_k$ , in fact, $-{\Delta }_k$ is the rate of change of the objective function when the k^th non-support components of the feasible solution x is increased and all the other non-support components are fixed, at the same time the support components are changed in such way to satisfy the constraints $Ax=b$ .

Then, in the pivot adaptive method, we define the n-vector of reduced gains (or support gradient) δ as follows:

${\delta }^{\text{T}}=-{\Delta }^{\text{T}}=\left({\delta }_j,j\in J\right)=c^{\text{T}}-y^{\text{T}}A=\left({\delta }_B^{\text{T}},{\delta }_N^{\text{T}}\right),\text{where}:{\delta }_B^{\text{T}}=0,\mathrm{<mi>\; </mi>}{\delta }_N^{\text{T}}=c_N^{\text{T}}-y^{\text{T}}{A}_B$ (8)

To reduce the computation time in the adaptive method of Gabasov [16] , we define the ( $m\times n$ ) matrix G as follows:

$\Gamma =A_B^{-1}A=\left({\Gamma }_B\mathrm{,}{\Gamma }_N\right)\mathrm{,}\text{where:}{\Gamma }_B=I_m\mathrm{,\; <mi>\; </mi>}{\Gamma }_N=A_B^{-1}{A}_N$ (9)

which is the decomposition of the columns of the matrix A on the support $J_B$ .

We have: ${\Gamma }_N=\Gamma \left(I\mathrm{,}{J}_N\right)=\left({\Gamma }_{ij}\mathrm{,}i\in I\mathrm{,}j\in J_N\right)$ , ${\Gamma }_{ij}$ is the product of the i^th row of the matrix $A_B^{-1}$ and the j^th column of the matrix $A_N$ . Then the n-vector of support gradient given in (8) can be computed as follows:

$\begin{array}{l}{\delta }^{\text{T}}=\left({\delta }_j\mathrm{,}j\in J\right)=c^{\text{T}}-c_B^{\text{T}}{A}_B^{-1}A=c^{\text{T}}-c_B^{\text{T}}\Gamma =\left({\delta }_B^{\text{T}}\mathrm{,}{\delta }_N^{\text{T}}\right)\mathrm{,}\\ \text{where:}{\delta }_B^{\text{T}}=\mathrm{0,\; <mi>\; </mi>}{\delta }_N^{\text{T}}=c_N^{\text{T}}-c_B^{\text{T}}{\Gamma }_N\end{array}$ (10)

We see that, to compute the quantity $c_B^{\text{T}}{A}_B^{-1}A$ , we begin to compute $\Gamma =A_B^{-1}A$ and not $y^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}$ ; therefore we need not to compute the inverse of the basic matrix $A_B$ .

From (6) and (10) we obtain

$\Delta F\left(x\right)={\delta }_N^{\text{T}}\Delta x_N={\displaystyle \underset{j\in J_N}{\sum }}{\delta }_j\Delta x_j$ (11)

3.2. Definition 8

For an given support $J_B$ , any vector $\chi =\chi \left(J\right)=\left(\begin{array}{c}{\chi }_B\\ {\chi }_N\end{array}\right)$ of $R^n$ that satisfies

$\{\begin{array}{l}{\chi }_j=d_j^{-}\mathrm{,}\text{if}{\delta }_j<0\hfill \\ {\chi }_j=d_j^{+}\mathrm{,}\text{if}{\delta }_j>0\hfill \\ {\chi }_j=d_j^{-}\text{or}{d}_j^{+}\mathrm{,}\text{if}{\delta }_j=0\hfill \\ {\chi }_B=A_B^{-1}\left(b-A_N{\chi }_N\right)\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_N\right)$ (12)

is called a primal pseudo-feasible solution accompanying the support $J_B$ .

3.3. Proposition 1

A primal pseudo-feasible solution accompanying a given support $J_B$ , χ, verifies just the general constraints of the problem (P), ie $A\chi =b$ . If more, the support components ${\chi }_B$ of the vector χ verifies: $d_B^{-}\le {\chi }_B\le d_B^{+}$ , then χ is feasible and optimal solution for (P).

3.4. Theorem 1 (The Optimality Criterion)

Let $\left\{x\mathrm{,}{J}_B\right\}$ be an SF-solution of the problem (P), and ${\delta }^{\text{T}}$ be the support gradient computed by (10), then the relations

$\{\begin{array}{l}{\delta }_j<0,\text{for}{x}_j=d_j^{-}\hfill \\ {\delta }_j>0,\text{for}{x}_j=d_j^{+}\hfill \\ {\delta }_j=0,\text{for}{d}_j^{-}\le x_j\le d_j^{+}\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_N\right)$ (13)

are sufficient, and in the case of non-degeneracy of the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ also necessary for the optimality of the feasible solution x.

Proof

1) The sufficient condition:

for the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ , suppose that the relation (13) are verified, we must proof that x is optimal, it amounts to show that:

$\forall \bar{x}\in H,\Delta F\left(x\right)=F\left(x\right)-F\left(\bar{x}\right)\ge 0$ (14)

Let $\bar{x}\in H$ , and $\Delta x=x-\bar{x}$ , then:

$\begin{array}{c}\Delta F\left(x\right)=F\left(x\right)-F\left(\bar{x}\right)={\displaystyle \underset{j\in J_N}{\sum }}{\delta }_j\Delta x_j\\ ={\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j\le 0\end{array}}{\sum }}{\delta }_j\left(x_j-{\bar{x}}_j\right)+{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j\ge 0\end{array}}{\sum }}{\delta }_j\left(x_j-{\bar{x}}_j\right)+{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j=0\end{array}}{\sum }}{\delta }_j\left(x_j-{\bar{x}}_j\right)\\ ={\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j\le 0\end{array}}{\sum }}{\delta }_j\left(d_j^{-}-{\bar{x}}_j\right)+{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j\ge 0\end{array}}{\sum }}{\delta }_j\left(d_j^{+}-{\bar{x}}_j\right)\ge 0\end{array}$

then x is optimal.

2) The necessary condition:

Suppose that $\left\{x\mathrm{,}{J}_B\right\}$ an SF-solution non-degenerate, i.e.:

$\forall j\in J_B,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}{d}_j^{-}<x_j<d_j^{+}$ (15)

and that x optimal, i.e.:

$\forall \bar{x}\in H,\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\Delta F\left(x\right)=F\left(x\right)-F\left(\bar{x}\right)={\displaystyle \underset{j\in J_N}{\sum }}{\delta }_j\Delta x_j\ge 0.$ (16)

Reasoning by absurdity:

Suppose that the relations (13) are not verified, thus we have, at least, one of the following three cases:

1) $\exists k\in J_N/{\delta }_k\le 0\text{and}{x}_k>d_k^{-}$ .

2) $\exists k\in J_N/{\delta }_k\ge 0\text{and}{x}_k<d_k^{+}$ .

3) $\exists k\in J_N/{\delta }_k=0\text{and}{x}_k=d_j^{-}\text{or}{x}_k=d_j^{+}$ .

Suppose then we have the first case, i.e.

$\exists k\in J_N/{\delta }_k\le 0\text{and}{x}_k>d_k^{-}$ (17)

(the proof uses the same reasoning for the second and the third cases). Construct the n-vector $\bar{x}\left(\theta \right)=\left({\left(\bar{x}\left(\theta \right)\right)}_1\mathrm{,}{\left(\bar{x}\left(\theta \right)\right)}_2\mathrm{,}\cdots \mathrm{,}{\left(\bar{x}\left(\theta \right)\right)}_n\right)$ as follows:

$\{\begin{array}{l}{\left(\bar{x}\left(\theta \right)\right)}_j=x_j,\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\forall j\in J_N\backslash \left\{k\right\}\hfill \\ {\left(\bar{x}\left(\theta \right)\right)}_k=x_k-\theta ,\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\theta \in \left[0,x_k-d_k^{-}\right]\hfill \\ {\left(\bar{x}\left(\theta \right)\right)}_j=x_j+\theta {\Gamma }_{jk},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}\forall j\in J_B\hfill \end{array}$ (18)

where ${\Gamma }_{jk}$ is the product of the j^th row of the matrix $A_B^{-1}$ and the k^th column of the matrix $A_N$ . Let ${\theta }_1=x_k-d_k^{-}>0$ .

we have

$A\bar{x}\left(\theta \right)=A_B{\left(\bar{x}\left(\theta \right)\right)}_B+A_N{\left(\bar{x}\left(\theta \right)\right)}_N=0$ (19)

and

$\forall j\in J_N\mathrm{,\; <mi>\; </mi>}{d}_j^{-}\le {\left(\bar{x}\left(\theta \right)\right)}_j\le d_j^{+}$ (20)

For $j\in J_B,{\left(\bar{x}\left(\theta \right)\right)}_j=x_j+\theta {\Gamma }_{jk}$ , then for have:

$\forall j\in J_B\mathrm{,\; <mi>\; </mi>}{d}_j^{-}\le {\left(\bar{x}\left(\theta \right)\right)}_j\le d_j^{+}$ (21)

a value of θ is chosen such that:

$\forall j\in J_B,\mathrm{<mi>\; </mi>}{d}_j^{-}\le x_j+\theta {\Gamma }_{jk}\le d_j^{+}$ (22)

i.e.

$\{\begin{array}{l}0<\theta \le \frac{d_j^{+}-x_j}{{\Gamma }_{jk}},\text{for}{\Gamma }_{jk}>0\hfill \\ 0<\theta \le \frac{d_j^{-}-x_j}{{\Gamma }_{jk}},\text{for}{\Gamma }_{jk}<0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J_B\right)$ (23)

Put: ${\theta }_2=\underset{\begin{array}{l}{\Gamma }_{jk}>0\\ j\in J_B\end{array}}{\min }\frac{d_j^{+}-x_j}{{\Gamma }_{jk}}$ , ${\theta }_3=\underset{\begin{array}{l}{\Gamma }_{jk}<0\\ j\in J_B\end{array}}{\min }\frac{d_j^{-}-x_j}{{\Gamma }_{jk}}$ .

we have: ${\theta }_2>0$ , ${\theta }_3>0$ , because $\left\{x\mathrm{,}{J}_B\right\}$ is non-degenerate.

Let ${\theta }^{\mathrm{<mo>\; *\; </mo>}}=min\left({\theta }_1\mathrm{,}{\theta }_2\mathrm{,}{\theta }_3\right)$ , then

$\bar{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\in H$ (24)

or

$F\left(x\right)-F\left(\bar{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\right)={\displaystyle \underset{j\in J_N}{\sum }}{\delta }_j\Delta x_j={\delta }_k\Delta x_k={\delta }_k{\theta }^{\mathrm{<mo>\; *\; </mo>}}<0$ (25)

then

$F\left(\bar{x}\left({\theta }^{\mathrm{<mo>\; *\; </mo>}}\right)\right)>F\left(x\right)$ (26)

contradiction with (16).

3.5. Definition 9

The pair $\left\{x^0\mathrm{,}{J}_B^0\right\}$ satisfying the relations (13) will be called an optimal SF-solution of the problem (P).

3.6. The Suboptimality Criterion

Let $x^0$ an optimal solution of (P), and x a feasible solutions of (P).

From (11) we obtained:

$\begin{array}{c}\underset{\bar{x}\in H}{\max }\Delta F\left(x\right)=F\left(x^0\right)-F\left(x\right)\\ =\underset{\bar{x}\in H}{\max }{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\sum }}{\delta }_j\left({\bar{x}}_j-x_j\right)+\underset{\bar{x}\in H}{\max }{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\sum }}{\delta }_j\left({\bar{x}}_j-x_j\right)\\ \le {\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\sum }}{\delta }_j\left(d_j^{+}-x_j\right)+{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\sum }}{\delta }_j\left(d_j^{-}-x_j\right)\end{array}$

Let

$\beta \left(x,J_B\right)={\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j>0\end{array}}{\sum }}{\delta }_j\left(d_j^{+}-x_j\right)+{\displaystyle \underset{\begin{array}{c}j\in J_N\\ {\delta }_j<0\end{array}}{\sum }}{\delta }_j\left(d_j^{-}-x_j\right)$ (27)

$\beta \left(x\mathrm{,}{J}_B\right)$ is called the suboptimality estimate of the SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ since

$\left(F\left(x^0\right)-F\left(x\right)\right)\le \beta \left(x\mathrm{,}{J}_B\right)$ (28)

We have the following theorem of suboptimality.

3.7. Theorem 2 (Sufficient Condition of Suboptimality)

For a feasible solution x to be ò-optimal for given positive number ò, it is sufficient of the existence of a support $J_B$ such that $\beta \left(x\mathrm{,}{J}_B\right)\le ϵ$ .

3.8. Proposition 2

From (12) and (27) we deduce:

$\beta \left(x,J_B\right)={\delta }_N^{\text{T}}\left({\chi }_N-x_N\right)={\delta }^{\text{T}}\left(\chi -x\right)$ (29)

3.9. The Dual Problem

The dual of the primal problem (P) is given by the following linear problem

$\left(D\right)\{\begin{array}{l}\min \varphi \left(y,v,w\right)=b^{\text{T}}y-{\left(d^{-}\right)}^{\text{T}}v+{\left(d^{+}\right)}^{\text{T}}w\hfill \\ A^{\text{T}}y-v+w=c\hfill \\ y\in R^m,\mathrm{<mi>\; </mi>}v\ge 0,\mathrm{<mi>\; </mi>}w\ge 0.\hfill \end{array}$ (30)

where $A^{\text{T}}=\left(\begin{array}{c}{a}_1^{\text{T}}\\ ⋮\\ a_n^{\text{T}}\end{array}\right)$ , with $\forall j\in J$ , $a_j^{\text{T}}$ is the transpose of the j^th column $a_j$ of the matrix A. The problem D has n general constraints, and $\left(m+2n\right)$ variables.

Like (P), the problem (D) has an optimal solution ${\lambda }^0=\left(y^0\mathrm{,}{v}^0\mathrm{,}{w}^0\right)$ , and $F\left(x^0\right)=\varphi \left({\lambda }^0\right)$ , where $x^0$ is the optimal solution of (P).

3.10. Definition 10

Any $\left(m+2n\right)$ -vector $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ satisfying all the constraints of the problem D is called a dual feasible solution.

3.11. Definition 11

Let $J_B$ be a support of the problem (P), and δ the corresponding support gradient defined in (10), the $\left(m+2n\right)$ -vector $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ which satisfies:

$\{\begin{array}{l}{y}^{\text{T}}=c_B^{\text{T}}{A}_B^{-1}\hfill \\ v_j=-{\delta }_j,\mathrm{<mi>\; </mi>}{w}_j=0\text{if}{\delta }_j\le 0\hfill \\ v_j=0,\mathrm{<mi>\; </mi>}{w}_j={\delta }_j\text{if}{\delta }_j>0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J\right)$ (31)

is called the dual feasible solution accompanying the support $J_B$ .

3.12. Proposition 3

・ A dual feasible solution $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ accompanying a given support $J_B$ , is dual feasible, i.e.: $A^{\text{T}}y-v+w=c,\mathrm{<mi>\; </mi>}v\ge 0,\mathrm{<mi>\; </mi>}w\ge 0,\mathrm{<mi>\; </mi>}y\in R^m$ .

・ For any support $J_B$ we have

$c^{\text{T}}\chi =\varphi \left(\lambda \right)$ (32)

where λ and χ are respectively the dual feasible solution and an primal pseudo-feasible solution accompanying the support $J_B$ .

3.13. Definition 12

Let y be dual feasible solution: $A^{\text{T}}y-v+w=c\mathrm{,\; <mi>\; </mi>}v\ge \mathrm{0,\; <mi>\; </mi>}w\ge 0$ . The $\left(m+2n\right)$ -vector ${\lambda }^{\mathrm{<mo>\; *\; </mo>}}=\left(y\mathrm{,}{v}^{\mathrm{<mo>\; *\; </mo>}}\mathrm{,}{w}^{\mathrm{<mo>\; *\; </mo>}}\right)$ such that:

$\{\begin{array}{l}{v}_j^{\mathrm{<mo>\; *\; </mo>}}=\mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>}{w}_j^{\mathrm{<mo>\; *\; </mo>}}=\left(c_j-a_j^{\text{T}}y\right)\text{if}\left(c_j-a_j^{\text{T}}y\right)\ge 0\hfill \\ v_j^{\mathrm{<mo>\; *\; </mo>}}=-\left(c_j-a_j^{\text{T}}y\right)\mathrm{,\; <mi>\; </mi>}{w}_j^{\mathrm{<mo>\; *\; </mo>}}=0\text{if}\left(c_j-a_j^{\text{T}}y\right)\le 0\hfill \end{array}\mathrm{<mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\left(j\in J\right)$ (33)

is called a coordinated dual feasible point to the m-vector y.

3.14. Proposition 4

The coordinated dual feasible point ${\lambda }^{*}=\left(y,v^{*},w^{*}\right)$ to y is dual feasible, i.e.: $A^{\text{T}}y-v^{\mathrm{<mo>\; *\; </mo>}}+w^{\mathrm{<mo>\; *\; </mo>}}=c$ , $v^{\mathrm{<mo>\; *\; </mo>}}\ge 0$ , $w^{\mathrm{<mo>\; *\; </mo>}}\ge 0$ .

3.15. Decomposition of the Suboptimality Estimate of an SF-Solution $\left\{x\mathrm{,}{J}_B\right\}$

Let $\left\{x\mathrm{,}{J}_B\right\}$ be a SF-solution of the problem (P), $\beta \left(x\mathrm{,}{J}_B\right)$ be its suboptimality estimate calculated by (27), $\lambda =\left(y\mathrm{,}v\mathrm{,}w\right)$ be the dual feasible solution accompanying the support $J_B$ , χ the primal pseudo-feasible solution accompanying the support $J_B$ , $x^0$ be the optimal solution for the problem (P), ${\lambda }^0$ be the optimal solution for the dual problem (D).

From (9), (10), (29), (32), and proposition 1 we have:

$\begin{array}{c}\beta \left(x,J_B\right)={\delta }_N^{\text{T}}\left({\chi }_N-x_N\right)={\delta }^{\text{T}}\left(\chi -x\right)=\left(c^{\text{T}}-c_B^{\text{T}}\Gamma \right)\left(\chi -x\right)\\ =c^{\text{T}}\chi -c^{\text{T}}x-c_B^{\text{T}}{A}_B^{-1}A\chi +c_B^{\text{T}}{A}_B^{-1}Ax=c^{\text{T}}\chi -c^{\text{T}}x\\ =\varphi \left(\lambda \right)-F\left(x\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)+F\left(x^0\right)-F\left(x\right)\end{array}$ .

then

$\beta \left(x\mathrm{,}{J}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(x\right)+\mathrm{<mi>\; </mi>}\beta \left(J_B\right)$ (34)

where: $\beta \left(J_B\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)$ is the degree of non-optimality of the support $J_B$ , and $\beta \left(x\right)=F\left(x^0\right)-F\left(x\right)$ is the degree of non-optimality of the feasible solution x.

3.16. Proposition 5

・ The feasible solution x will be optimal if $\beta \left(x\right)=0$ , and the support $J_B$ will be optimal if $\beta \left(J_B\right)=0$ , but the pair $\left\{x\mathrm{,}{J}_B\right\}$ will be an optimal SF-solution if $\beta \left(x\right)=\mathrm{<mi>\; </mi>}\beta \left(J_B\right)=0$ , so the optimality of the feasible solution x can be not identified if it is examined with an unfit support, because in this case there will be $\beta \left(J_B\right)\ne 0$ , and $\beta \left(x\mathrm{,}{J}_B\right)\ne 0$ .

・ As $\beta \left(J_B\right)=\varphi \left(\lambda \right)-\varphi \left({\lambda }^0\right)$ , then the support $J_B$ will be optimal if its accompanying dual feasible solution λ is optimal solution for the dual problem D.

3.17. Theorem 3 (Existence of an Optimal Support)

For each problem (P), there is always an optimal support.

Proof

As (P) has an optimal solution, its dual (D) given by (30) has also an optimal solution, let $\bar{\lambda }=\left(\bar{y}\mathrm{,}\bar{v}\mathrm{,}\bar{w}\right)$ this solution, and define the sets:

$I^{+}=\left\{j\in J\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}\bar{y}\right)\ge 0\right\}$ , $I^{-}=\left\{j\in J\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}\bar{y}\right)\le 0\right\}$ ,

and

$\bar{C}=\left\{y\in R^m\mathrm{<mo>\; /\; </mo>}\left(c_j-a_j^{\text{T}}y\right)\ge \mathrm{0,}\forall i\in I^{+}\text{and}\left(c_j-a_j^{\text{T}}y\right)\le \mathrm{0,}\forall i\in I^{-}\right\}$ ,

we have $\bar{y}\in \bar{C}$ .

Let $y\in \bar{C}$ , and define the following linear problem:

$\left(\bar{D}\right)\{\begin{array}{l}min\psi \left(y\right)=b^{\text{T}}y+{\displaystyle \underset{j\in J^{+}}{\sum }}{d}_j^{+}\left(c_j-a_j^{\text{T}}y\right)+{\displaystyle \underset{j\in J^{-}}{\sum }}{d}_j^{-}\left(c_j-a_j^{\text{T}}y\right)\hfill \\ y\in \bar{C}\subset R^m\hfill \end{array}$ (35)

We have $\psi \left(y\right)=\varphi \left(y\mathrm{,}v\mathrm{,}w\right)$ , where $\left(y\mathrm{,}v\mathrm{,}w\right)$ is the coordinated dual feasible point to the vector y, and $\bar{y}$ is an optimal feasible solution of the problem ( $\bar{D}$ ).

On the other hand, there exists a “vertex” $y^{\mathrm{<mo>\; *\; </mo>}}$ of the set $\bar{C}$ that is an optimal feasible solution for ( $\bar{D}$ ), and this vertex is the intersection of at least m hyperplane $a_j^{\text{T}}{y}^{*}=c_j,j\in \left(I^{+}\cup I^{-}\right)$ .

Put $J_B=\left\{i\in \left(I^{+}\cup I^{-}\right)\mathrm{<mo>\; /\; </mo>}{a}_j^{\text{T}}{y}^{\mathrm{<mo>\; *\; </mo>}}=c_j\right\}$ where $\left|J_B\right|=m$ .

Then: $A^{\text{T}}\left(I\mathrm{,}{J}_B\right)y^{\mathrm{<mo>\; *\; </mo>}}=c_B$ , and so: $y^{\mathrm{<mo>\; *\; </mo>}}=c_B^{\text{T}}{A}_B^{-1}$ , further the coordinated dual feasible point to $y^{\mathrm{<mo>\; *\; </mo>}}$ is the dual feasible solution accompanying the support $J_B$ , and its optimal feasible solution for the problem (D), then, according to the proposition (4), we conclude that $J_B$ is an optimal support for (P).

4. The Description of the Pivot Adaptive Method “PAM”

As the Simplex Method, to solve the problem (P), the adaptive method (and therefore also the pivot adaptive method) has two phases: the initialization phase, and the second phase, we will detail each one in the following.

1) The initialization phase:

In this phase an initial support feasible solution SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ will be determined, and thus the matrix G defined in (9).

We assume that $b_i\ge \mathrm{0,}\forall i\in I$ , and $d_j^{-}=0,\forall j\in J$ .

Remark 1

Notice that each problem (P) can be reduced to this case,i.e.:
$b_i\ge \mathrm{0,}\forall i\in I$ ,and $d_j^{-}=\mathrm{0,}\forall j\in J$ ,in fact:

a) if $\exists i^0\in I/b_{i^0}<0$ then both term of the corresponding constraint is multiplied by (−1).

b) if $\exists k\in J\mathrm{<mo>\; /\; </mo>}{d}_k^{-}\ne 0$ , then we do the change of variable: ${\left(x^{\prime }\right)}_k=x_k-d_k^{-}$ , then:

$0\le {\left(x^{\prime }\right)}_k\le d_k^{+}-d_k^{-}$ (36)

and the general constraints $Ax=b$ of (P) will be write as:

$a_1{x}_1+a_1{x}_1+\cdots +a_{k-1}{x}_{k-1}+a_k\left({x^{\prime }}_k+d_k^{-}\right)+a_{k+1}{x}_{k+1}+\cdots +a_n{x}_n=b$ (37)

where $\forall j\in J$ , $a_j$ is the j^th column of the matrix A, from this relation we obtain:

$a_1{x}_1+a_1{x}_1+\cdots +a_{k-1}{x}_{k-1}+a_k{x^{\prime }}_k+a_{k+1}{x}_{k+1}+\cdots +a_n{x}_n=b-a_k{d}_k^{-}$ (38)

in (36), if $\left(b-a_k{d}_k^{-}\right)<0$ we multiple the two terms by (−1).

Then to determine an initial SF-solution to the problem (P), define the artificial problem of (P) as follows:

$\left(\tilde{P}\right)\{\begin{array}{l}\max F\left(\tilde{x}\right)=-{\displaystyle \underset{j=1}{\overset{j=m}{\sum }}}{\tilde{x}}_j\hfill \\ Ax+\tilde{x}=b\hfill \\ d^{-}\le x\le d^{+},0\le \tilde{x}\le b\hfill \end{array}$ (39)

where $b_i\ge \mathrm{0,}\forall i\in I$ , and $\tilde{x}=\tilde{x}\left(J\right)=\left({\tilde{x}}_i\mathrm{,}i\in I\right)=\left({\tilde{x}}_1\mathrm{,}{\tilde{x}}_2\mathrm{,}\cdots \mathrm{,}{\tilde{x}}_m\right)$ are the m artificial variables added to the problem (P).

We resolve the artificial problem $\tilde{P}$ with the “pivot adaptive method” starting with the obvious initial feasible solution: $\left(x,\tilde{x}\right),x=0_{R^n},\tilde{x}=b$ , and the canonical support (determined by the indices of the artificial variables), and we take the matrix $\Gamma =A$ .

If H is not empty, at the optimum of $\tilde{P}$ $\tilde{x}=0$ , $Ax=b$ , and $d^{-}\le x\le d^{+}$ , so x is a feasible solution of (P), and the optimal SF-solution of the problem $\tilde{P}$ can be taken as the initial SF-solution for the problem P.

2) The second phase:

Assume that an initial SF-solution $\left\{x\mathrm{,}{J}_B\right\}$ of the problem (P) is found in the initialization phase, and let G the correspondent matrix computed by (9), $ϵ\ge 0$ an arbitrary number, the problem will be solved with the pivot adaptive method that we describe in the following.

At the iterations of the pivot adaptive method the transfer $\left\{x\mathrm{,}{J}_B\right\}\to \left\{\bar{x}\mathrm{,}{\bar{J}}_B\right\}$ from one SF-solution to a new one is carried out in such a way that:

$\beta \left(\bar{x}\mathrm{,}{\bar{J}}_B\right)\le \mathrm{<mi>\; </mi>}\beta \left(x\mathrm{,}{J}_B\right)$ (40)

the transfer will be realized as two procedures making up the iteration:

i) The procedure of the feasible solution change $x\to \bar{x}$ :

During this procedure we decrease the degree of non-optimality of the feasible solution: $\beta \left(\bar{x}\right)\le \mathrm{<mi>\; </mi>}\beta \left(x\right)$ , and then improve the primal criterion $F\left(\bar{x}\right)\ge F\left(x\right)$ :

i.1) compute the support gradient δ by (10), and the suboptimality estimate by (27).

i.2) If $\beta \left(x\mathrm{,}{J}_B\right)\le \epsilon$ , then stop the resolution with: x is an ò-optimal feasible solution for (P) (P).

i.3) If $\beta \left(x,J_B\right)>\epsilon$ , we compute the non-support components ${\chi }_N$ of the primal pseudo-feasible solution accompanying the support $J_B$ by (12), and the search direction $l=\left(l_B,l_N\right)$ with:

$\{\begin{array}{l}{l}_N={\chi }_N-x_N\hfill \\ l_B=-{\Gamma }_N{l}_N\hfill \end{array}$ (41)

i.4) Find the primal step length ${\theta }^0$ with:

${\theta }^0=min\left\{\mathrm{1,}{\theta }_{j_0}\right\}\mathrm{,}\text{where}\mathrm{<mo>\; :\; </mo>}{\theta }_{j_0}=\underset{j\in J_B}{min}{\theta }_j\mathrm{,}{\theta }_j=(\begin{array}{l}\frac{d_j^{+}-x_j}{l_j}\mathrm{,}\text{if}{l}_j>\mathrm{0\; <mo>\; ;\; </mo>}\hfill \\ \frac{d_j^{-}-x_j}{l_j}\mathrm{,}\text{if}{l}_j<\mathrm{0\; <mo>\; ;\; </mo>}\hfill \\ \infty \mathrm{<mo>\; ;\; </mo>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{l}_j=0.\hfill \end{array}\left(j\in J_B\right)$ (42)

Let $j_{00}$ such that: $J_B\left(j_{00}\right)=j_0$ which is the position of $j_0$ in the vector of indices $J_B$ .

i.5) Compute the new feasible solution: $\bar{x}=x+{\theta }^{0}l$ , and $F\left(\bar{x}\right)=F\left(x\right)+{\theta }^0\beta \left(x\mathrm{,}{J}_B\right)$ .

i.6) If ${\theta }^0=1$ , then stop the resolution with: $\left\{\bar{x}\mathrm{,}{J}_B\right\}$ is the optimal SF-solution of (P).

i.7) If ${\theta }^0<1$ , then compute:

$\beta \left(\bar{x}\mathrm{,}{J}_B\right)=\left(1-{\theta }^0\right)\beta \left(x\mathrm{,}{J}_B\right)$ (43)

i.8) If $\beta \left(\bar{x}\mathrm{,}{J}_B\right)\le ϵ$ , then stop the resolution with: $\left\{\bar{x}\mathrm{,}{J}_B\right\}$ is the ò-optimal SF-solution of (P).

i.9) if $\beta \left(\bar{x},J_B\right)>ϵ$ , then go to ii) to change the support $J_B$ to ${\bar{J}}_B$ .

ii) The procedure of the support change $J_B\to {\bar{J}}_B$ :

During this procedure we decrease the degree of non-optimality of the support: $\beta \left({\bar{J}}_B\right)\le \mathrm{<mi>\; </mi>}\beta \left(J_B\right)$,and then improve the dual criterion $\varphi \left(\bar{\lambda }\right)\ge \varphi \left(\lambda \right)$ , where $\bar{\lambda }$ is the dual feasible solution accompanying the support ${\bar{J}}_B$ , and $\lambda$ is the dual feasible solution accompanying the support $J_B$ .

In this procedure there are two rules to change support: rule of “the short step”, and rule of “the long step”, the two rules will be presented.

ii.1) to the $j_0$ found in (i.4), compute ${\chi }_{j_0}=x_{j_0}+l_{j_0}$ , and ${\alpha }_0={\chi }_{j_0}-{\bar{x}}_{j_0}$ .

ii.2) compute the dual direction t with:

$\{\begin{array}{l}{t}_{j_0}=-sign\left({\alpha }_0\right);\\ t_j=0,\mathrm{<mi>\; </mi>}j\in J_B\backslash \left\{j_0\right\};\\ t_N^{\text{T}}=t_B^{\text{T}}{\Gamma }_N.\end{array}$ (44)

ii.3) compute:

${\sigma }_j=\{\begin{array}{l}\frac{{\delta }_j}{t_j}\mathrm{,}\text{if}{\delta }_j{t}_j>\mathrm{0\; <mo>\; ;\; </mo>}\\ \mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{\delta }_j=0,t_j<0,{\xi }_j=d_j^{-}\mathrm{<mo>\; ;\; </mo>}\\ \mathrm{0,\; <mi>\; </mi>\; <mi>\; </mi>\; <mi>\; </mi>}\text{if}{\delta }_j=0,t_j>0,{\xi }_j=d_j^{+}\mathrm{<mo>\; ;\; </mo>}\\ \infty \mathrm{,\; <mi>\; </mi>\; <mi>\; </mi>}\text{inothercases}\mathrm{.}\end{array}\left(j\in J_N\right)$ (45)

and arrange the obtained values in increasing order as:

${\sigma }_{j_1}\le {\sigma }_{j_2}\le \cdots \le {\sigma }_{j_p},\mathrm{<mi>\; </mi>}{j}_k\in J_N,\mathrm{<mi>\; </mi>}{\sigma }_{j_k}\ne \infty ,\mathrm{<mi>\; </mi>}k\in \left\{1,\cdots ,p\right\}.$ (46)

As was said before, the change of support can be done with two different rules, to use the “short step rule” go to a), and to use the “long step rule” go to b).

a) Change of the support with the “short step rule”:

a.1) From (46) put:

${\sigma }^0={\sigma }_{j_1}={\sigma }_{j^{*}}=\underset{j\in J_N}{\min }{\sigma }_j.$ (47)

Let $j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}$ such that: $J_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ which is the position of $j^{\mathrm{<mo>\; *\; </mo>}}$ in the vector of indices $J_N$ .

Put: ${\bar{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\bar{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ , then ${\bar{J}}_B\left(j_{00}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ , ${\bar{J}}_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j_0$ .

a.2) Compute:

$\begin{array}{c}\bar{\delta }=\delta -{\sigma }^{0}t,\mathrm{<mi>\; </mi>}\\ \beta \left(\bar{x},{\bar{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x},J_B\right)+{\sigma }^0{\alpha }_0\end{array}$ (48)

go to ii.4).

b) Change of the support with the “long step rule”:

b.1) for every $j_k\mathrm{,}k\in \left\{\mathrm{1,}\cdots \mathrm{,}p\right\}$ of (47) compute

$\Delta {\alpha }_{j_k}=\left|{\Gamma }_{j_{00}{j}_k}\right|\left(d_{j_k}^{+}-d_{j_k}^{-}\right)$ (49)

b.2) as $j^{\mathrm{<mo>\; *\; </mo>}}$ we choose $j_q$ such that

${\alpha }_{j_{q-1}}=\left[{\alpha }_0+{\displaystyle \underset{k=1}{\overset{k=q-1}{\sum }}}\Delta {\alpha }_{j_k}\right]<0,\mathrm{<mi>\; </mi>}{\alpha }_{j_q}=\left[{\alpha }_0+{\displaystyle \underset{k=1}{\overset{k=q}{\sum }}}\Delta {\alpha }_{j_k}\right]\ge 0$ (50)

Let $j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}$ such that: $J_N\left(j_{\mathrm{<mo>\; *\; </mo>\; <mo>\; *\; </mo>}}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ which is the position of $j_0$ in the vector of indices $J_B$ .

b.3) put: ${\sigma }^0={\sigma }_{j^{*}}$ , and ${\bar{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\bar{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ , then ${\bar{J}}_B\left(j_{00}\right)=j^{\mathrm{<mo>\; *\; </mo>}}$ , ${\bar{J}}_N\left(j_{**}\right)=j_0$ .

b.4) Compute:

・ $\bar{\delta }=\delta -{\sigma }^{0}t$ .

・ $\beta \left(\bar{x},{\bar{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x},J_B\right)+{\displaystyle \underset{k=1}{\overset{k=q}{\sum }}}{\alpha }_{j_{k-1}}\left({\sigma }_{j_k}-{\sigma }_{j_{k-1}}\right)$ where: ${\alpha }_{j_0}={\alpha }_0$ , ${\sigma }_{j_0}=0$ .

Go to ii.4). ii.4) compute $\bar{\Gamma }$ as follows:

$\{\begin{array}{l}{\bar{\Gamma }}_{j_{00}j}=\frac{{\Gamma }_{j_{00}j}}{{\Gamma }_{j_{00}{j}^{*}}},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}j\in J;\\ {\bar{\Gamma }}_{ij}={\Gamma }_{ij}-{\Gamma }_{i{j}^{*}}{\bar{\Gamma }}_{j_{00}j},\mathrm{<mi>\; </mi>\; <mi>\; </mi>}i\in I\backslash \left\{j_{00}\right\},j\in J.\end{array}$ (51)

${\Gamma }_{j_{00}{j}^{\mathrm{<mo>\; *\; </mo>}}}$ is “the pivot”. Go to ii.5).

ii.5) Set: $x=\bar{x}$ , $J_B={\bar{J}}_B$ , $\beta \left(x\mathrm{,}{J}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x}\mathrm{,}{\bar{J}}_B\right)$ , $\delta =\bar{\delta }$ , and $\Gamma =\bar{\Gamma }$ . Go to i.2).

5. The Pivot Adaptive Method

Let $\left\{x\mathrm{,}{J}_B\right\}$ be an initial SF-solution for the problem (P), G the matrix computed by (9), and $ϵ\ge 0$ are given.

The “Pivot Adaptive Method” (rule of the “short step” and rule of “the long step” are presented) is summarized in the following steps:

Algorithm 1 (The Pivot Adaptive Method)

1) compute the support gradient ${\delta }^{\text{T}}$ by (10), and $\beta \left(x\mathrm{,}{J}_B\right)$ by (27).

2) if $\beta \left(x\mathrm{,}{J}_B\right)\le ϵ$ , then STOP with: x is an ò-optimal feasible solution for (P).

3) if $\beta \left(x\mathrm{,}{J}_B\right)>ϵ$ , then compute the non-support components ${\chi }_N$ of the primal pseudo-feasible solution accompanying the support $J_B$ by (12), and the search direction l with (41).

4) find the primal step length ${\theta }^0$ with (42). Let $j_{00}$ such that: $J_B\left(j_{00}\right)=j_0$ which is the position of $j_0$ in the vector of indices $J_B$ .

5) Compute the new feasible solution: $\bar{x}=x+{\theta }^{0}l$ , and $F\left(\bar{x}\right)=F\left(x\right)+{\theta }^0\beta \left(x\mathrm{,}{J}_B\right)$ .

6) if ${\theta }^0=1$ , then STOP with: $\left\{\bar{x}\mathrm{,}{J}_B\right\}$ is the optimal SF-solution for (P).

7) if ${\theta }^0<1$ , then compute $\beta \left(\bar{x}\mathrm{,}{J}_B\right)=\left(1-{\theta }^0\right)\beta \left(x\mathrm{,}{J}_B\right)$ .

8) if $\beta \left(\bar{x}\mathrm{,}{J}_B\right)\le ϵ$ , then STOP with: $\left\{\bar{x}\mathrm{,}{J}_B\right\}$ is the ò-optimal SF-solution for (P).

9) if $\beta \left(\bar{x}\mathrm{,}{J}_B\right)>ϵ$ , then change the support $J_B$ to ${\bar{J}}_B$ .

10) compute ${\chi }_{j_0}=x_{j_0}+l_{j_0}$ , and: ${\alpha }_0={\chi }_{j_0}-{\bar{x}}_{j_0}$ .

11) compute the dual direction t with (44).

12) compute ${\sigma }_j$ , for $j\in J_N$ with (45), and arrange the obtained values in increasing order.

13) do the change of support by one of the rules:

a) Change of the support with the “short step rule” as follows:

a.1) compute ${\sigma }^0$ with (47), and set: ${\bar{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\bar{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ .

a.2) compute $\beta \left(\bar{x}\mathrm{,}{\bar{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x}\mathrm{,}{J}_B\right)+{\sigma }^0{\alpha }_0$ . Go to (14).

b) Change of the support with the “long step rule” as follows:

b.1) for every $j_k\mathrm{,}k\in \left\{\mathrm{1,}\cdots \mathrm{,}p\right\}$ of (46) compute $\Delta {\alpha }_{j_k}=\left|{\Gamma }_{j_{00}{j}_k}\right|\left(d_{j_k}^{+}-d_{j_k}^{-}\right)$ .

b.2) as $j^{\mathrm{<mo>\; *\; </mo>}}$ we choose $j_q$ such that (50) is verified.

b.3) set: ${\sigma }^0={\sigma }_{j^{*}}$ , and ${\bar{J}}_B=\left(J_B\backslash \left\{j_0\right\}\right)\cup \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}$ , ${\bar{J}}_N=\left(J_N\backslash \left\{j^{\mathrm{<mo>\; *\; </mo>}}\right\}\right)\cup \left\{j_0\right\}$ .

b.4) compute $\beta \left(\bar{x},{\bar{J}}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x},J_B\right)+{\displaystyle \underset{k=1}{\overset{k=q}{\sum }}}{\alpha }_{j_{k-1}}\left({\sigma }_{j_k}-{\sigma }_{j_{k-1}}\right)$ where: ${\alpha }_{j_0}={\alpha }_0$ , ${\sigma }_{j_0}=0$ . Go to (14).

14) compute $\bar{\Gamma }$ with (51) and $\bar{\delta }=\delta -{\sigma }^{0}t$ .

15) set: $x=\bar{x}$ , $J_B={\bar{J}}_B$ , $\beta \left(x\mathrm{,}{J}_B\right)=\mathrm{<mi>\; </mi>}\beta \left(\bar{x}\mathrm{,}{\bar{J}}_B\right)$ , $\delta =\bar{\delta }$ , and $\Gamma =\bar{\Gamma }$ . Go to (2).

6. Example

In this section, a linear problem will be resolved with the Pivot Adaptive Method using the “short step rule”, and in parallel we will explain how to realize these calculations under the shape of successive tables as is given in Figure 1.

Consider the following linear problem with bounded variables:

$\left(P\right)\{\begin{array}{l}maxF\left(x\right)=c^{\text{T}}x\hfill \\ Ax=b\hfill \\ d^{-}\le x\le d^{+}\mathrm{.}\hfill \end{array}$ (52)

where: $c^{\text{T}}=\left(\mathrm{65,115,0,0,0}\right)$ , $x={\left(x_1\mathrm{,}{x}_2\mathrm{,}{x}_3\mathrm{,}{x}_4\mathrm{,}{x}_5\right)}^{\text{T}}$ , $A=\left(\begin{array}{ccccc}5/2& 15/2& 1& 0& 0\\ 1/8& 1/8& 0& 1& 0\\ 35/2& 10& 0& 0& 1\end{array}\right)$ , $b={\left(\mathrm{240,5,595}\right)}^{\text{T}}$ , $d^{-}=0_{R^5}$ , $d^{+}={\left(\mathrm{34,34,240,5,595}\right)}^{\text{T}}$ .

Put $J=\left\{1,2,3,4,5\right\}$ , $ϵ={10}^{-3}$ .

First phase (Initialization):

Let $\left\{x^1\mathrm{,}{J}_B^1\right\}$ be the initial SF-solution of the problem (P) where; $x^1={\left(\mathrm{11,27,10,}1/4\mathrm{,}265/2\right)}^{\text{T}}$ , $J_B^1=\left\{3,4,5\right\}$ , so: $J_N^1=\left\{1,2\right\}$ , $A_B^1=\left(a_3,a_4,a_5\right)=I_3$ , $A_N^1=\left(a_1\mathrm{,}{a}_2\right)$ then The matrix G is given by: $\Gamma =\left({\Gamma }_B,{\Gamma }_N\right)$ where: ${\left({\Gamma }_1\right)}_B=I_3$ , ${\left({\Gamma }_1\right)}_N=\left(\begin{array}{cc}5/2& 15/2\\ 1/8& 1/8\\ 35/2& 10\end{array}\right)$ .

Note that for the initial support we have chosen the canonical support, and for the initial feasible solution we took an interior point of the feasible region of the problem (P).

u In the preamble part of the tables (Figure 1)which has four rows we put sequentially: $c^{\text{T}}$, ${\left(d^{-}\right)}^{\text{T}}$, ${\left(d^{+}\right)}^{\text{T}}$ , $x^1$ . The tables have 8 columns.

Second phase:

Starting with the SF-solution $\left\{x^1\mathrm{,}{J}_B^1\right\}$ , and the matrix G to resolve the problem (P) with the PAM using the short step rule.

u In the first table of PAM (Figure 1) (represents the first iteration) there are 8 rows, in the first 3 rows we have the matrix G (indicating the vector formed $A_B^1$ in the first column of the tables), and in the rest rows we have sequentially: δ, l, θ, x², σ.

The support gradient ${\delta }_1^{\text{T}}=\left({\left({\delta }_1^{\text{T}}\right)}_B\mathrm{,}{\left({\delta }_1^{\text{T}}\right)}_N\right)$ where: ${\left({\delta }_1^{\text{T}}\right)}_B=0_{R^3}$ , ${\left({\delta }_1^{\text{T}}\right)}_N=\left(\mathrm{65,115}\right)$ , and $\beta \left(x^1,J_B^1\right)=2300>ϵ$ .

1) Iteration 1:

・ Change solution: we have: ${\left({\chi }_1\right)}_N=\left(\mathrm{34,34}\right)$ , and ${\left(l_1\right)}_N=\left(\mathrm{23,7}\right)$ , ${\left(l_1\right)}_B=\left(-\mathrm{110,}-15/4\mathrm{,}-945/2\right)$ , ${\theta }^0={\theta }_4=1/15$ , $\left(J_B^1\right)\left(2\right)=4$ (4 is the second component of the vector of index $J_B^1$ ).

u The case of ${\theta }^0$ is marked by yellow in tables (Figure 1), it correspond at the second vector of $J_B^1$ which is $a_4$ (which will come out of the basis.

Then, ${\theta }^0<1$ , the new feasible solution $x^2=\left(188/15\mathrm{,}412/15\mathrm{,}40/15\mathrm{,0,101}\right)$ , and $\beta \left(x^2,J_B^1\right)=6440/3>ϵ$ .

・ Change support (with the short step rule):

${\chi }_4=-7/2$ , and: ${\alpha }_0=-7/2$ , the dual direction $t^{\text{T}}=\left(1/8\mathrm{,}1/8\mathrm{,0,1,0}\right)$ , ${\sigma }^0={\sigma }_1=520$ , then $\left(J_N^1\right)\left(1\right)=1$ (1 is the first component of the vector of index $J_N^1$ ).

u The case of ${\sigma }^0$ is marked by green in tables (Figure 1), his row correspond to vector $a_1$ which will go into the basis.

So $J_B^2=\left(J_B^1\backslash \left\{4\right\}\right)\cup \left\{1\right\}\mathrm{<mo>\; =\; </mo>}\left\{\mathrm{3,1,5}\right\}$ , $J_N^2=\left(J_N^1\backslash \left\{1\right\}\right)\cup \left\{4\right\}=\left\{\mathrm{4,2}\right\}$ .

Figure 1. Tables of the pivot adaptive method.

u For have the 2^nd table (Figure 1), we applied the pivoting rule where the pivot is marked by red. The new support gradient ${\delta }_2^{\text{T}}={\delta }_1^{\text{T}}-{\sigma }^{0}t=\left({\left({\delta }_2^{\text{T}}\right)}_B\mathrm{,}{\left({\delta }_2^{\text{T}}\right)}_N\right)$ where: ${\left({\delta }_2^{\text{T}}\right)}_B=0_{R^3}$ , ${\left({\delta }_2^{\text{T}}\right)}_N=\left(-\mathrm{520,50}\right)$ , and $\beta \left(x^2,J_B^2\right)=\beta \left(x^2,J_B^1\right)+{\sigma }^0{\alpha }_0=980/3$ .

As $\beta \left(x^2\mathrm{,}{J}_B^2\right)>ϵ$ , we go to another iteration, we compute then: ${\Gamma }_2=\left({\left({\Gamma }_2\right)}_B\mathrm{,}{\left({\Gamma }_2\right)}_N\right)$ where:

${\left({\Gamma }_2\right)}_B=I_3$ , ${\left({\Gamma }_1\right)}_N=\left(\begin{array}{cc}-20& 5\\ 8& 1\\ -140& -15/2\end{array}\right)$ .

2) Iteration 2:

・ Change solution: we have: ${\chi }_N=\left(\mathrm{0,34}\right)$ , and ${\left(l_2\right)}_N=\left(\mathrm{0,}98/15\right)$ , ${\left(l_2\right)}_B=\left(-98/3\mathrm{,}-98/15\mathrm{,49}\right)$ , ${\theta }^0={\theta }_3=4/49$ , $\left(J_B^2\right)\left(1\right)=3$ (3 is the first component of the vector of indice $J_B^2$ ).

Then, ${\theta }^0<1$ , the new feasible solution $x^3=\left(\mathrm{12,28,0,0,105}\right)$ , and $\beta \left(x^2\mathrm{,}{J}_B^1\right)=300>ϵ$ .

・ Change support (with the short step rule): ${\chi }_3=-30$ , and: ${\alpha }_0=-30$ , the dual direction $t^{\text{T}}=\left(\mathrm{0,5,1,}-\mathrm{20,0}\right)$ , ${\sigma }^0={\sigma }_2=10$ , then $\left(J_N^2\right)\left(2\right)=2$ (2 is the second component of the vector of index $J_N^2$ ).

So $J_B^3=\left(J_B^2\backslash \left\{3\right\}\right)\cup \left\{2\right\}=\left\{\mathrm{2,1,5}\right\}$ , $J_N^3=\left(J_N^2\backslash \left\{2\right\}\right)\cup \left\{3\right\}=\left\{\mathrm{4,3}\right\}$ .

The new support gradient ${\delta }_3^{\text{T}}={\delta }_2^{\text{T}}-{\sigma }^{0}t=\left({\left({\delta }_3^{\text{T}}\right)}_B\mathrm{,}{\left({\delta }_3^{\text{T}}\right)}_N\right)$ where: ${\left({\delta }_3^{\text{T}}\right)}_B=0_{R^3}$ , ${\left({\delta }_3^{\text{T}}\right)}_N=\left(\mathrm{10,320}\right)$ , and $\beta \left(x^3\mathrm{,}{J}_B^3\right)=\beta \left(x^3\mathrm{,}{J}_B^2\right)+{\sigma }^0{\alpha }_0=0$ .

Then $\left\{x^3\mathrm{,}{J}_B^3\right\}$ is the optimal SF-solution of the problem (P), and $F\left(x^3\right)=4000$ .

7. Brief Numerical Comparison between the PAM and the Simplex Method

To realize a numerical comparison between the Simplex algorithm implemented in the function “linprog” under the MATLAB programming language version 7.14, 0.739 (R2012a) and our algorithm (PAM), an implementation for the later with the short step rule, has been developed.

The comparison is carried on the resolution of the Klee-Minty problem which has the following form [7] :

$\left(P_3\right)\{\begin{array}{l}\max 2^{n-1}{x}_1+2^{n-2}{x}_2+\dots +2x_{n-1}+x_n\hfill \\ x_1\le 5\hfill \\ 4x_1+x_2\le 25\hfill \\ 8x_1+4x_2+x_3\le 125\hfill \\ ⋮\hfill \\ 2^n{x}_1+2^{n-1}{x}_2+\cdots +4x_{n-1}+x_n\le 5^n\hfill \\ x\ge 0\hfill \end{array}$ (53)

where $x=\left(x_1\mathrm{,}{x}_2\mathrm{,}\cdots \mathrm{,}{x}_n\right)$ . (P₃) has n variables, n constraints and 2ⁿ vertices.

For a fixed n, to write (P₃) in the form of the problem (P) given in (1), we added to each of the n constraints of (P₃) a spread variable, and we found, for each of the 2n variables of the result problem, a lower born and an upper born. Then the problem (P₃) can be done as a linear problem with bounded variables as follows:

$\left(P_4\right)\{\begin{array}{l}\max 2^{n-1}{x}_1+2^{n-2}{x}_2+\cdots +2x_{n-1}+x_n\hfill \\ x_1+x_{n+1}=5\hfill \\ 4x_1+x_2+x_{n+2}=25\hfill \\ 8x_1+4x_2+x_3+x_{n+3}=125\hfill \\ ⋮\hfill \\ 2^n{x}_1+2^{n-1}{x}_2+\cdots +4x_{n-1}+x_n+x_{2n}=5^n\hfill \\ 0\le x_1\le 5;\mathrm{<mi>\; </mi>\; 0}\le x_2\le 25;\cdots ;0\le x_n\le 5^n;\hfill \\ 0\le x_{n+1}\le 5;\mathrm{<mi>\; </mi>\; 0}\le x_{n+2}\le 25;\cdots ;0\le x_{2n}\le 5^n.\hfill \end{array}$ (54)

The Simplex algorithm chosen here takes as a starting solution the original, then in our implementation of the (PAM) we impose the same initial feasible solution. For the initial support we had taken the canonical one $J_B=\left\{n+1,n+2,\cdots ,2n\right\}$ , then $\Gamma =A$ .

We have considered problems with matrix A of size $n\times n$ , where $n\in \left\{\mathrm{3,5,7,10,12,15,17,20,23,25,27,30,33,35,37,40,42,45,47,50}\right\}$ , for each size, we obtained the number of iterations, and the time of resolution, where the time is given into milliseconds.

This results are reported in Figure 2, and in Figure 3, where “Simplex(it)”, “PAM(it)”, “Simplex(tm)”, “PAM(tm)” represent respectively the number of iterations of the Simplex algorithm, the number of iterations of the Pivot Adaptive Method, the time of the Simplex algorithm, the time of the Pivot Adaptive Method. The time is given into milliseconds.

Figure 2. Number of iterations and time for Linprog-Simplex and PAM for Klee-Minty problem.

Figure 3. Time comparison between Linprog-Simplex and PAM for the Klee-Minty problem.

We remark that the (PAM) is better than the Simplex algorithm in computation time, and in necessary number of iterations to solve the problems. Recall that the optimal solution of the problem (P₃) is given by $x=\left(\mathrm{0,0,}\cdots {\mathrm{,5}}^n\right)$ .

8. Conclusions

The main contribution of this article is a new variant of the Adaptive Method that we have called “Pivot Adaptive Method” (PAM). In this variant, we use the simplex pivoting rule in order to avoid computing the inverse of the basic matrix in each iteration. As was recognized in this work, the algorithm saves our time compared to the original algorithm (AM), and allows us to present the resolution of a given problem under the shape of successive tables as seen in an example.

We have implemented our algorithm (PAM) ((PAM) with the short step rule, and (PAM) with the long step rule) using MATLAB, and we have done a brief comparison with the primal simplex algorithm (using linprog-simplex in MATLAB) for solving the Klee-Minty problem. Indeed, the (PAM) is more efficient in number of iterations, and in computation time.

In a subsequent work, we shall do a more thorough comparison between the Simplex algorithm of Dantzig and the (PAM), and we shall extend the (PAM) to the problems with a large scale using the constraint selection technique.

Conflicts of Interest

The authors declare no conflicts of interest.

References

[1]	Dantzig, G.B. (1951) Minimization of a Linear Function of Variables Subject to Linear Inequalities. John Wiley, New York.
[2]	Minoux, M. (1983) Programmation mathématique, Théorie et al gorithmes, Tome 1, Dunod.
[3]	Culioli, J.C. (1994) Introduction à l’optimisation, Elipse.
[4]	Dantzig, G.B. (1963) Linear Programming and Extensions. Princeton University Press, Princeton. https://doi.org/10.1515/9781400884179
[5]	Gabasov, R. and Kirillova, F.M. (1977, 1978, 1980) Method of Linear Programming. Vol. 1, 2 and 3, BGU Press, Minsk. (In Russian)
[6]	Bland, R.G. (1977) New Finite Pivoting Rules for the Simplex Method. Mathematics of Operations Research, 2, 103-107.
[7]	Klee, V. and Minty, G.J. (1972) How Good Is the Simplex Algorithm? In: Shisha III, O., Ed., Inequalities, Academic Press, New York, 159-175.
[8]	Khachiyan, L.G. (1979) A Polynomial Algorithm in Linear Programming. Soviet Mathematics Doklady, 20, 191-194.
[9]	Karmarkar, N.K. (1984) A New Polynomial-Time Algorithm for Linear Programming. Combinatorica, 4, 373-395.
[10]	Kojima, M., Megiddo, N., Noma, T. and Yoshise, A. (1989) A Unified Approach to Interior Point Algorithms for Linear Programming. In: Megiddo, N., Ed., Progress in Mathematical Programming: Interior Point and Related Methods, Springer Verlag, New York, 29-47.
[11]	Ye, Y. (1997) Interior Point Algorithms, Theory and Analysis. John Wiley and Sons, Chichester.
[12]	Vanderbei, R.J. and Shanno, D.F. (1999) An Interior-Point Algorithm for Nonconvex Nonlinear Programming. Computational Optimization and Applications, 13, 231-252.
[13]	Peng, J., Roos, C. and Terlaky, T. (2001) A New and Efficient Large-Update Interior-Point Method for Linear Optimization. Journal of Computational Technologies, 6, 61A-80.
[14]	Cafieri, S., Dapuzzo, M., Marino, M., Mucherino, A. and Toraldo, G. (2006) Interior Point Solver for Large-Scale Quadratic Programming Problems with Bound Constraints. Journal of Optimization Theory and Applications, 129, 55-75.
[15]	Gabasov, R.F. (1994) Adaptive Method for Solving Linear Programming Problems. University of Bruxelles, Bruxelles.
[16]	Gabasov, R.F. (1994) Adaptive Method for Solving Linear Programming Problems. University of Karlsruhe, Institute of Statistics and Mathematics, Karlsruhe.
[17]	Gabasov, R., Kirillova, F.M. and Prischepova, S.V. (1995) Optimal Feedback Control. Springer-Verlag, London.
[18]	Gabasov, R., Kirillova, F.M. and Kostyukova, O.I. (1979) A Method of Solving General Linear Programming Problems. Doklady AN BSSR, 23, 197-200. (In Russian)
[19]	Kostina, E. (2002) The Long Step Rule in the Bounded-Variable Dual Simplex Method: Numerical Experiments. Mathematical Methods of Operation Research, 55, 413-429.
[20]	Radjef, S. and Bibi, M.O. (2011) An Effective Generalization of the Direct Support Method. Mathematical Problems in Engineering, 2011, Article ID: 374390.
[21]	Balashevich, N.V., Gabasov, R. and Kirillova, F.M. (2000) Numerical Methods of Program and Positional Optimization of the Linear Control Systems. Zhurnal Vychislitel’noi Matematiki i Matematicheskoi Fiziki, 40, 838-859.
[22]	Bentobache, M. and Bibi, M.O. (2012) A Two-Phase Support Method for Solving Linear Programs: Numerical Experiments. Mathematical Problems in Engineering, 2012, Article ID: 482193.
[23]	Bibi, M.O. and Bentobache, M. (2015) A Hybrid Direction Algorithm for Solving Linear Programs. International Journal of Computer Mathematics, 92, 201-216.