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)

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.
LanguageEnglish
Pages491–500
Number of pages10
JournalEuropean Journal of Operational Research
Volume211
Issue number3
Early online date24 Feb 2012
DOIs
Publication statusPublished - 16 Sep 2012

Fingerprint

Selection Rules
Pivot
Linear programming
Monotone
Simplex Algorithm
MATLAB
Primal-dual
Cycling
Viability
Numerical Results
Demonstrate

Keywords

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

Cite this

Csizmadia, Zsolt ; Illes, T. ; Nagy , Adrienn. / The s-monotone index selection rules for pivot algorithms of linear programming. In: European Journal of Operational Research. 2012 ; Vol. 211, No. 3. pp. 491–500.
@article{15dd6be6d589460da08e450590f4e6de,
title = "The s-monotone index selection rules for pivot algorithms of linear programming",
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.",
keywords = "s-monotone index , linear programming , pivot algorithms, anti-cycling pivot rules",
author = "Zsolt Csizmadia and T. Illes and Adrienn Nagy",
note = "Operations Research Report ORR-10-2 Department of Operations Research, Eotvos Lorand University of Sciences, Budapest, Hungary, 2010.",
year = "2012",
month = "9",
day = "16",
doi = "10.1016/j.ejor.2012.02.008",
language = "English",
volume = "211",
pages = "491–500",
journal = "European Journal of Operational Research",
issn = "0377-2217",
number = "3",

}

The s-monotone index selection rules for pivot algorithms of linear programming. / Csizmadia, Zsolt; Illes, T.; Nagy , Adrienn.

In: European Journal of Operational Research, Vol. 211, No. 3, 16.09.2012, p. 491–500.

Research output: Contribution to journalArticle

TY - JOUR

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

AU - Csizmadia, Zsolt

AU - Illes, T.

AU - Nagy , Adrienn

N1 - Operations Research Report ORR-10-2 Department of Operations Research, Eotvos Lorand University of Sciences, Budapest, Hungary, 2010.

PY - 2012/9/16

Y1 - 2012/9/16

N2 - 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.

AB - 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.

KW - s-monotone index

KW - linear programming

KW - pivot algorithms

KW - anti-cycling pivot rules

UR - http://www.cs.elte.hu/opres/orr/download/ORR10_02.pdf

U2 - 10.1016/j.ejor.2012.02.008

DO - 10.1016/j.ejor.2012.02.008

M3 - Article

VL - 211

SP - 491

EP - 500

JO - European Journal of Operational Research

T2 - European Journal of Operational Research

JF - European Journal of Operational Research

SN - 0377-2217

IS - 3

ER -