tailieunhanh - Pivoting rules for the revised simplex algorithm

In this paper, we perform a computational study in which the pricing operation is computed with eight different pivoting rules: (i) Bland’s Rule, (ii) Dantzig’s Rule, (iii) Greatest Increment Method, (iv) Least Recently Considered Method, (v) Partial Pricing Rule, (vi) Queue Rule, (vii) Stack Rule, and (viii) Steepest Edge Rule; and incorporate them with the revised simplex algorithm. | Yugoslav Journal of Operations Research 24 (2014), Number 3, 321-332 DOI: PIVOTING RULES FOR THE REVISED SIMPLEX ALGORITHM Nikolaos PLOSKAS Department of Applied Informatics, School of Information Sciences, University of Macedonia, Thessaloniki, Greece ploskas@ Nikolaos SAMARAS Department of Applied Informatics, School of Information Sciences, University of Macedonia,Thessaloniki, Greece samaras@ Received: February 2014 / Accepted: May 2014 Abstract. Pricing is a significant step in the simplex algorithm where an improving nonbasic variable is selected in order to enter the basis. This step is crucial and can dictate the total execution time. In this paper, we perform a computational study in which the pricing operation is computed with eight different pivoting rules: (i) Bland’s Rule, (ii) Dantzig’s Rule, (iii) Greatest Increment Method, (iv) Least Recently Considered Method, (v) Partial Pricing Rule, (vi) Queue Rule, (vii) Stack Rule, and (viii) Steepest Edge Rule; and incorporate them with the revised simplex algorithm. All pivoting rules have been implemented in MATLAB. The test sets used in the computational study are a set of randomly generated optimal sparse and dense LPs and a set of benchmark LPs (Netliboptimal, Kennington, Netlib-infeasible). Keywords: Linear Programming, Revised Simplex Method, Pricing, Pivoting Rules. MSC: 90C05, 65K05. 1. INTRODUCTION Linear Programming (LP) P is the process of minimizing or maximizing a linear objective function z = ni=1 ci · xi subject to a number of linear equality and inequality constraints. Several algorithms have been proposed for solving linear programming problems (LPs). The most well-known method for solving LPs is 322 N. Ploskas, N. Samaras / Pivoting Rules for the Revised Simplex Algorithm the simplex algorithm developed by George B. Dantzig [6]; other well-studied algorithms include the Interior Point Methods and the Exterior Point Simplex Algorithm (EPSA). The main