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

Zsolt Csizmadia, T. Illes, Adrienn Nagy

Research output: Contribution to journalArticle

6 Citations (Scopus)
56 Downloads (Pure)

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.
Original languageEnglish
Pages (from-to)491–500
Number of pages10
JournalEuropean Journal of Operational Research
Volume211
Issue number3
Early online date24 Feb 2012
DOIs
Publication statusPublished - 16 Sep 2012

Keywords

  • s-monotone index
  • linear programming
  • pivot algorithms
  • anti-cycling pivot rules

Fingerprint Dive into the research topics of 'The s-monotone index selection rules for pivot algorithms of linear programming'. Together they form a unique fingerprint.

  • Cite this