A Modular Presolve Procedure for Large Scale Linear Programming

Swietanowski, A. (1995). A Modular Presolve Procedure for Large Scale Linear Programming. IIASA Working Paper. IIASA, Laxenburg, Austria: WP-95-113

Preview

Text WP-95-113.pdf Download (1MB) | Preview

Abstract

In this paper we present a survey of methods used for analysis and simplification of a general single-objective linear program prior to solving it with a simplex type optimizer. We consider the methods known since the early work of Brearley et al. as well as less known or appreciated numerical elimination methods. We then proceed to analyze in detail the usefulness of some of the presolve methods. We attempt to explain what impact each of these methods may have on the activity of a simplex type optimizer.

These theoretical speculations are validated by experiments involving the discussed methods and an advanced implementation of the simplex algorithm: a set of very large linear problems analysed with different subsets of available presolve techniques are solved using the simplex optimizer.

The paper is accompanied by a modular linear optimization package consisting of a stand alone presolver and postsolver as well as a new release of our advanced simplex optimizer with embedded presolve capabilities.

Actions (login required)

View Item