Presolving in linear programming

By Erling D. Andersen, Knud D. Andersen. 1995

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Mathematical Optimization

Citations in the corpus

Integer-Programming Software Systems (2005, methodology): “We refer the reader to [3, 28, 31, 53] for detailed explanation of preprocessing techniques.”
The Mosek Interior Point Optimizer for Linear Programming: An Implementation of the Homogeneous Algorithm (2000, background): “It is now common to include an extensive preprocessing facility in an LP solver, where the purpose of the preprocessing is to remove obviously redundant constraints and fixed variables, see [5].”
Progress in presolving for mixed integer programming (2015, methodology): “[15] and Williams [28] discussed bound tightening, row elimination, and variable fixings in mathematical programming systems, while Andersen and Andersen [6] published presolving techniques in the context of linear programming.”
A Rewriting System for Convex Optimization Problems (2017, methodology): “Andersen and Andersen (1995) cast presolves as reductions, listing many examples for linear programs together with methods for retrieving their solutions.”
On implementing a primal-dual interior-point method for conic quadratic optimization (2003, methodology): “Before the problem is optimized it is preprocessed to remove obvious redundancies using most of the techniques presented in [4].”
On handling indicator constraints in mixed integer programming (2016, methodology): “A specialized version of this procedure applies to affine functions, and is commonly used in MIP solvers, see [1].”
Lower bound limit analysis of cohesive‐frictional materials using second‐order cone programming (2006, background): “Tests conducted by Andersen and Andersen [56] have indicated that the removal of dependent rows during presolve can provide substantial net savings in solution time, as well as better stability during the main optimization phase.”
The SCIP Optimization Suite 3.2 (2016, unknown): “, [ ̄̀j , ūj ] ⊆ [`j , uj ], variable xj is said to be implied free [7].”
Linear and Nonlinear Optimization (2008, background): “As an initial basis use the extreme points (0, 0), (0, 5), and (9, 5).”
Mixed-integer nonlinear optimization*† (2013, methodology): “It is part of nonlinear optimization solvers (Messine, 2004) as well as of MILP solvers (Andersen and Andersen, 1995; Savelsbergh, 1994).”