Presolve Methods

Nikolaos Ploskas and Nikolaos Samaras
Additional contact information
Nikolaos Ploskas: University of Macedonia
Nikolaos Samaras: University of Macedonia

Chapter Chapter 4 in Linear Programming Using MATLAB®, 2017, pp 135-217 from Springer

Abstract: Abstract Presolve methods are important in solving LPs, as they reduce the size of the problem and discover whether an LP is unbounded or infeasible. Presolve methods are used prior to the application of an LP algorithm in order to: (i) eliminate redundant constraints, (ii) fix variables, (iii) transform bounds of single structural variables, and (iv) reduce the number of variables and constraints by eliminations. This chapter presents eleven presolve methods used prior to the execution of an LP algorithm: (i) eliminate zero rows, (ii) eliminate zero columns, (iii) eliminate singleton equality constraints, (iv) eliminate kton equality constraints, (v) eliminate singleton inequality constraints, (vi) eliminate dual singleton inequality constraints, (vii) eliminate implied free singleton columns, (viii) eliminate redundant columns, (ix) eliminate implied bounds on rows, (x) eliminate redundant rows, and (xi) make coefficient matrix structurally full rank. Each method is presented with: (i) its mathematical formulation, (ii) a thorough numerical example, and (iii) its implementation in MATLAB. In addition, we discuss how to transform a solution back in terms of the original variables and constraints of the problem (postsolve). Finally, a computational study on benchmark LPs is performed. The aim of the computational study is twofold: (i) compare the execution time and the reduction to the problem size of the aforementioned presolve methods, and (ii) investigate the impact of preprocessing prior to the application of LP algorithms. The execution time and the number of iterations with and without preprocessing are presented.

Date: 2017
References: Add references at CitEc
Citations:

There are no downloads for this item, see the EconPapers FAQ for hints about obtaining it.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:spochp:978-3-319-65919-0_4

Ordering information: This item can be ordered from
http://www.springer.com/9783319659190

DOI: 10.1007/978-3-319-65919-0_4

Access Statistics for this chapter

More chapters in Springer Optimization and Its Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().