ABSTRACT

The purpose of this paper is to introduce a new pivot rule of the simplex algorithm. The simplex algorithm first presented by George B. Dantzig, is a widely used method for solving a linear programming problem (LP). One of the important steps of the simplex algorithm is applying an appropriate pivot rule to select the basis-entering variable corresponding to the maximum reduced cost. Unfortunately, this pivot rule not only can lead to a critical cycling (solved by Bland’s rules), but does not improve efficiently the objective function. Our new pivot rule 1) solves the cycling problem in the original Dantzig’s simplex pivot rule, and 2) leads to an optimal improvement of the objective function at each iteration. The new pivot rule can lead to the optimal solution of LP with a lower number of iterations. In a maximization problem, Dantzig’s pivot rule selects a basis-entering variable corresponding to the most positive reduced cost; in some problems, it is well-known that Dantzig’s pivot rule, before reaching the optimal solution, may visit a large number of extreme points. Our goal is to improve the simplex algorithm so that the number of extreme points to visit is reduced; we propose an optimal improvement in the objective value per unit step of the basis-entering variable. In this paper, we propose a pivot rule that can reduce the number of such iterations over the Dantzig’s pivot rule and prevent cycling in the simplex algorithm. The idea is to have the maximum improvement in the objective value function: from the set of basis-entering variables with positive reduced cost, the efficient basis-entering variable corresponds to an optimal improvement of the objective function. Using computational complexity arguments and some examples, we prove that our optimal pivot rule is very effective and solves the cycling problem in LP. We test and compare the efficiency of this new pivot rule with Dantzig’s original pivot rule and the simplex algorithm in MATLAB environment.

Keywords:

Linear Programming, Simplex Algorithm, Pivot Rules, Optimal Pivot Rule

1. Introduction

Linear programming (LP) has been one of the most dynamic areas of applied mathematics in the last sixty years. LP was solved in the late 1960s by Dantzig’s simplex method [1] . But, many variants of the simplex method were eventually proved to have exponential worst-case performance [2] . To solve efficiently a LP problem, we need to consider the pivot rule and the computational complexity that depend on the number of constraints and variables. One of the important steps of the simplex algorithm is of course the pivot rule that is used for selecting the basis-entering variable. An effective rule consists of computing the optimal solution of a LP with a small number of iterations. Dantzig’s simplex method still seems to be the most efficient procedure for a great majority of practical problems, especially for small size problems. But Dantzig’s original pivot rule cannot prevent cycling in linear programming and takes a lot of iterations in some cases [3] . To prevent this weakness, many research studies tried to improve the simplex algorithm, via the pivot rule by reducing the number of iterations and the solution time [4] - [6] . Unfortunately, most papers concerning simplex pivot rules have not been receiving much attention, even among researchers in the field of linear programming. Moreover, a very large part of these researches was presented in terms of oriented matroid programming and frequently not specialized to pivot rules for linear programming. Also, some of the other results were obtained as a side result (extreme case) of some interior point methods. Due to this, a lot of results remained unknown to researchers only working on the simplex method. T. Terlaky and S. Zhang [7] discussed the various pivot rules of the simplex method and its variants that have been developed until 1993, starting from the appearance of Bland’s minimal index rules [8] . Their paper was mainly concerned with finiteness properties of simplex type pivot rules. Also there are rich research results concerning pivot rules for specially structured linear programming problems, like network linear programming, assignment problems, etc. Most recently, K. Chankong et al. [9] proposed a new pivot rule called absolute change pivot rule. The idea is trying to block a basis-leaving variable that makes a little change in the objective function value as much as possible. Some computational results are reported, comparing the number of iterations from this new rule to Dantzig’s original pivot rule.

In this paper, we propose an original pivot rule called optimal pivot rule. The idea is to have an optimal improvement of the value of the objective function for any iteration: from the variables with positive reduced cost, we have a set of basis-entering variables; the efficient basis-entering variable is chosen from this set and corresponds to an optimal improvement of the objective function; this makes the objective function value to increase faster than when a regular Dantzig’s pivot rule is used, and therefore lead to fewer number of iterations. The optimal pivot rule can prevent cycling in the simplex algorithm. We report the computational results by testing and comparing the number of iterations from this new rule to Dantzig’s original pivot rule in MATLAB environment.

The rest of the paper is organized as follows: Section 2 describes the preliminaries of linear programming, simplex algorithm and pivot rule. Section 3 explains the main idea of our optimal pivot rule; we show that the new pivot rule prevents cycling in simplex algorithm. We use simple computational complexity facts to prove that the new optimal pivot rule is efficient. Section 4 deals with the computational results by testing and comparing the speed and the number of iterations from this new pivot rule to classical simplex rule and conclusions drawn.

2. Preliminaries: Dantzig’s Pivot Rule

In this paper, we consider the linear programming (LP) problem in the standard form:

(1)

where and.

After possibly rearranging the column of A, let where B is an m × m invertible matrix and N is m × (n − m) matrix. Here, B is called the basic matrix and N the associated non basic matrix. Basic and non basic index set are represented by and

respectively. Consider the equation Ax = b, and let be the solution where

and is called a basic solution of the system. The constraints

can be rewrite as

(2)

If, x is called a basic feasible solution of the system. Suppose that a basic feasi-

ble solution of the system (1) is whose objective value z₀ is given by

.

Then

where and. We denote the column of A by and the column of by.

Let z be the objective function value, we get

where represents the reduced cost, with

.

The main result exhibits that the optimal solution is achieved if the index set

is empty. If the index set J is not empty, let

.

If the index set

is empty, then the LP (1) is not bounded, and it has no solution.

Let

.

By Dantzig’s rules, the index of the basis-entering variable is e and the index of basis-leaving variable is s. The pivot operation uses.

The tableau format of the simplex method follows:

Table 1 format reports the value of the objective function, the basis variables, the reduced cost row, which consist of

for non basic variables., the LP is at optimal solution. If increases, then the vector, which is stored in the tableau in row 1 through m under variable, will determine how much can increase. If, then can be increased indefinitely, and the optimal objective value is unbounded. Conversely, if, that is, if has at least one positive component, then the increase in, from a pivot rule on results to an increase of the value of the objective function. The optimal pivot rule determines the non basic variable, and the pivot that compute the optimal increase of the value of the objective function.

In Bland’s Rule, choose the basis-entering variable, such that e is the smallest index with. Also choose the basis-leaving variable index s with the smallest index (in case of ties in the ratio test). This rule solves the cycling problem.

3. Optimal Pivot Rules

A key factor in the performance of the simplex method is the rule used to decide which index j (with) should enter in the basis after each pivot. It is well-known that the time spent in checking, for each j, is, and if we check all possible j’s, the total time is at most. This compares with the time needed to com- plete the rest of the pivot, where k is the number m of pivots performed since we last computed.

However, the selection of a pivot rule not only will affect the performance of each

pivot, but also the total number of pivots needed to reach the optimum (if it exists). For each j (with), the time spent in checking a pivot

is. For all possible j’s, the total time to check a most pivots is. At each step in a simplex algorithm, pivoting requires the most important computing time; it consists to compute. This requires a time, which is greater than the total number of time to check all possible j’s pivots. Reducing the number of pivots (number of iterations in the simplex algorithm) accelerate the speed of the simplex algorithm to compute an optimal solution when exists. One may argue that this optimal pivot rule needs even more computation. The efficiency of the optimal pivot rule results from this simple computational complexity fact.

Let

.

The simplex algorithm with optimal pivot rule follows.

Step 1. Let. Stop the algorithm if:

1), or all, then is anoptimal solution.

2) if and for all, the LP is not bounded. Stop the algorithm.

Step 2. Determine the basis-entering and the basis-leaving variables by using optimal change pivot rule:

For all (with), let such as if

exists.

Let

.

The index of the basis-entering variable is e and the index of basis-leaving variable is s.

Step 3. Perform the pivot operation using the basis-entering and the basis-leaving variable, and go to Step 1.

Definition: A pivot is degenerate if the objective function value does not change from 2 consecutives pivots. A cycle is a sequence of pivots that returns to the dictionary from which the cycle began.

Note: Every pivot in a cycle must be degenerate.

Theorem 1 (termination with optimal pivot rule) If the simplex method uses optimal pivot rule, it terminates in finite time with optimal solution, and more over there is no cycling.

Proof: Suppose the simplex method is implemented with optimal pivot rule and consider two consecutive bases and. Let be the set of variables with positive reduced cost. Any can improve the value of

the objective function. Let and. The im-

provement of the objective function is. If the solution is degenerate, we have for some, in particular if (Dantzig’s rule); what causes cycling.

Now, let.

If and let and the values of the objective function and the corresponding solutions and. We have Þ

. The solutions from two consecutive bases and cannot remain the same and there is no possible cycle.

Conjecture 1. If, necessarily and the current solution can never be improved by the simplex algorithm. Hence the LP does not have a solution.

An illustration of the Optimal Pivot Rule

The proposed pivot rule is shown with two examples.

Example 1. Beale’s cycling problem

Consider the following linear programming problem:

Here, in Table 2,; but.

The optimal pivot rule: and. The ba-

sis-entering variable is and the basis-leaving variable is.

From Table 3, we have only.. The basis-ente-

ring variable is and the basis-leaving variable is.

After only 3 iterations, we have the optimal solution on Table 4 with no cycling. 7 iterations are required to solve this problem with Bland’s pivot rules.

Example 2. Consider the following LP program

We solve this LP using optimal pivot rule.

Here,; and.

The optimal pivot rule on Table 5:

and.

and.

The basis-entering variable is and the basis-leaving variable is (the basis-ente- ring variable corresponds here to the minimal reduced cost, but with an optimal growth of the value of the objective function).

Using the classical simplex pivot rule, the basis-entering variable is (corresponding to the maximal reduced cost) and the basis-leaving variable is. The increase of the objective function is 2500.

and.

and

(see Table 6).

The basis-entering variable is and the basis-leaving variable is (the basis-ente- ring variable corresponds here to the minimal reduced cost, but with an optimal growth

of the value of the objective function). Then, we have Table 7.

. The basis-entering variable is

and the basis-leaving variable is.

We have an optimal solution on Table 8 after 3 iterations.

Dantzig’s pivot rule computed the optimal solution of this LP with 6 iterations.

4. Computational Experiments

In this section, we present the computational results of modified simplex algorithm with optimal pivot rule. Optimal pivot rule was tested by solving randomly generated linear programming problems of various sizes using the MATLAB codes. We compare the number of iterations of this pivot rule with Dantzig’s pivot rule. The computer system processor is Intel (R) Core (TM) i7 3770S CPU @ 3.1 GHz, 8.00 GB of memory, and 64-bit Window 8.1 Operating System.

4.1. Problem Generation

For LP problems considered here, data are randomly generated using MATLAB generator. We consider the LP problem whose formulation is given by

where and.

We use MATLAB generator to build all data: SPRAND (m, n, density) is a random, m-by-n, sparse matrix with approximate density uniformly distributed nonzero entries. The density used is p%.

The data of b are generated according to RANDN (1, m) which is a vector with random entries. The data of c are generated according to RANDN (n, 1) which is vector with random entries.

and

.

We add an additional ones entries constraint in the matrix A, and

to obtain a bounded problem.

4.2. Comparison

To measure the performance of our new optimal pivot rule, we compare the optimal pivot rule with Dantzig’s original pivot rule, written in a MATLAB environment programming. The optimal pivot rule is also compare to the simplex method included in MATLAB optimset toolbox. The performance measures used for comparison are the number of iterations (pivots) and the CPU time. Note that DPR is simplex algorithm with Dantzig’s pivot rule and OPR is simplex algorithm with optimal pivot rule, SML is simplex in MATLAB.

Table 9 shows the comparison between the average number of iterations and the CPU time from solving LP by the simplex algorithm with DPR, OPR and SML: the average number of iterations and the CPU time from OPR pivot rule is less than the one from DPI and SML. DPR pivot rule achieves less number of iterations when the number of constraints and variable in the problem is higher. Due to limitation of the simplex software in MATLAB platform, SML could not solve the problems with and, with exit message*. But SML and DPR solved LP’s using almost the same number of iterations, but with a higher CPU time for SML.

*MATLAB message: “Exiting: Maximum number of iterations exceeded; increase options. MaxIter”: MATLAB could not solve the problem asking to increase the maximum number of iterations permitted.

5. Summary of Results and Conclusions

We proposed a new pivot rule called the optimal pivot rule. The idea of this rule is to

compute an optimal improvement in the objective value per unit step of the basis-ente- ring variable. From our experiments, the proposed pivot rule is faster and reduces the number of such iteration over the Dantzig’s pivot rule the simplex algorithm. Tableau 9 offers a summary of the average number of iterations of each method. We conclude that the simplex algorithm using the optimal change pivot rule is very fast for solving linear programming problems when the size of the problem is large.

Using simple computational complexity facts, we proved that the new optimal pivot rule in the simplex algorithm is efficient. Moreover, we show that the optimal pivot rule solves the problem of cycling in the simplex algorithm.

6. Recommendations

In a future research, we will implement the optimal pivot rule to solve mathematical optimization problems whose algorithms are derived from simplex pivots like quadratic programming problem. The conjecture 1 stated in this article needs to be proven.

To prevent the warning message “Exiting: Maximum number of iterations exceeded, increase options. MaxIter” from the simplex in MATLAB platform, MATLAB developers should include our optimal pivot rule in the simplex method in that software, so that MATLAB will then be able to solve larger size LPs.

Cite this paper

Etoa, J.B.E. (2016) New Optimal Pivot Rule for the Simplex Algorithm. Advances in Pure Mathematics, 6, 647-658. http://dx.doi.org/10.4236/apm.2016.610054

References