Strathprints logo
Strathprints Home | Open Access | Browse | Search | User area | Copyright | Help | Library Home | SUPrimo

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

Csizmadia, Zsolt and Illes, T. 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

[img]
Preview
PDF
ORR10_02.pdf - Draft Version

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.

Item type: Article
ID code: 28229
Notes: Operations Research Report ORR-10-2 Department of Operations Research, Eotvos Lorand University of Sciences, Budapest, Hungary, 2010.
Keywords: s-monotone index , linear programming , pivot algorithms, anti-cycling pivot rules, Management. Industrial Management, Modelling and Simulation, Management Science and Operations Research, Information Systems and Management
Subjects: Social Sciences > Industries. Land use. Labor > Management. Industrial Management
Department: Strathclyde Business School > Management Science
Depositing user: Mrs Caroline Sisi
Date Deposited: 26 Jan 2012 09:15
Last modified: 27 Mar 2015 20:21
URI: http://strathprints.strath.ac.uk/id/eprint/28229

Actions (login required)

View Item View Item