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

[thumbnail of WP-95-113.pdf]

Download (1MB) | Preview


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.

Item Type: Monograph (IIASA Working Paper)
Research Programs: Methodology of Decision Analysis (MDA)
Depositing User: IIASA Import
Date Deposited: 15 Jan 2016 02:05
Last Modified: 27 Aug 2021 17:15
URI: https://pure.iiasa.ac.at/4483

Actions (login required)

View Item View Item