The Circuit Direction Search Algorithm for Solving Two-Dimensional Linear Programming Problems

Abstract

The simplex method is the favored method that can solve a linear programming model. One of the important steps of the simplex method to speed up the algorithm is an effective pivot rule to exchange entering and leaving variables. The double-pivot rule that exchanges two entering and two leaving variables in each iteration is one of the interesting pivots. Two pivot variables can be obtained by solving a special two-dimensional linear programming problem. If an effective algorithm to solve a two-dimensional linear programming problem is established, it can speed up the simplex method. Therefore, in this paper, a new algorithm that is an interior search technique, called the circuit direction search algorithm, for solving a two-dimensional linear programming problem is proposed. It uses an appropriate circuit as a direction for updating a solution. Then, an associated dual variable is computed to check the optimality for terminating the algorithm. From the computational results, we found that the proposed algorithm could reduce the average number of iterations and the running time compared with the interior point method, the slope algorithm, and the simplex method.