Picture of a black hole

Strathclyde Open Access research that creates ripples...

The Strathprints institutional repository is a digital archive of University of Strathclyde's Open Access research outputs. Strathprints provides access to thousands of research papers by University of Strathclyde researchers, including by Strathclyde physicists involved in observing gravitational waves and black hole mergers as part of the Laser Interferometer Gravitational-Wave Observatory (LIGO) - but also other internationally significant research from the Department of Physics. Discover why Strathclyde's physics research is making ripples...

Strathprints also exposes world leading research from the Faculties of Science, Engineering, Humanities & Social Sciences, and from the Strathclyde Business School.

Discover more...

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 - Preprint

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.