The s-monotone index selection rules for pivot algorithms of linear programming

Csizmadia, Zsolt and Illés, Tibor and Nagy, Adrienn (2012) The s-monotone index selection rules for pivot algorithms of linear programming. European Journal of Operational Research, 211 (3). 491–500. ISSN 0377-2217 (https://doi.org/10.1016/j.ejor.2012.02.008)

[thumbnail of ORR10_02.pdf]
Preview
 PDF. Filename: ORR10_02.pdf
Accepted Author Manuscript
License: Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 logo
Download (475kB)| Preview

Abstract

In this paper we introduce the concept of s-monotone index selection rule for linear programming problems. We show that several known anti-cycling pivot rules like the minimal index, Last-In–First-Out and the most-often-selected-variable pivot rules are s-monotone index selection rules. Furthermore, we show a possible way to define new s-monotone pivot rules. We prove that several known algorithms like the primal (dual) simplex, MBU-simplex algorithms and criss-cross algorithm with s-monotone pivot rules are finite methods. We implemented primal simplex and primal MBU-simplex algorithms, in MATLAB, using three s-monotone index selection rules, the minimal-index, the Last-In–First-Out (LIFO) and the Most-Often-Selected-Variable (MOSV) index selection rule. Numerical results demonstrate the viability of the above listed s-monotone index selection rules in the framework of pivot algorithms.

ORCID iDs

Csizmadia, Zsolt, Illés, Tibor ORCID logoORCID: https://orcid.org/0000-0002-5396-3148 and Nagy, Adrienn;
CORE (COnnecting REpositories)