Abstract
Most modern linear programming solvers analyze the LP problem before submitting it to optimization. Some examples are the solvers WHIZARD (Tomlin and Welch, 1983), OB1 (Lustig et al., 1994), OSL (Forrest and Tomlin, 1992), Sciconic (1990) and CPLEX (Bixby, 1994). The purpose of the presolve phase is to reduce the problem size and to discover whether the problem is unbounded or infeasible.
In this paper we present a comprehensive survey of presolve methods. Moreover, we discuss the restoration procedure in detail, i.e., the procedure that undoes the presolve.
Computational results on the NETLIB problems (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.
Similar content being viewed by others
References
I. Adler, N. Karmarkar, M.G.C. Resende and G. Veiga, “Data structures and programming techniques for the implementation of Karmarkar's algorithm,”ORSA Journal on Computing 1 (2) (1989) 84–106.
I. Adler, M.G.C. Resende, G. Veiga and N. Karmarkar, “An implementation of Karmarkar's algorithm for linear programming,”Mathematical Programming 44 (3) (1989) 297–335.
R. Anbil, R. Tanga and E.L. Johnson, “A global approach to crew-pairing optimization,”IBM Systems Journal 31 (1) (1992) 71–78.
E.D. Andersen, “Finding all linearly dependent rows in large-scale linear programming,”Optimization Methods and Software, to appear.
R.E. Bixby, “Implementing the simplex method: The initial basis,”ORSA Journal on Computing 4 (3) (1992) 267–284.
R.E. Bixby, “Progress in linear programming,”ORSA Journal on Computing 6 (1) (1994) 15–22.
R.E. Bixby, J.W. Gregory, I.J. Lustig, R.E. Marsten and D.F. Shanno, “Very large-scale linear programming: A case study in combining interior point and simplex methods,”Operations Research 40 (5) (1992) 885–897.
G.H. Bradley, G.G. Brown and G.W. Graves, “Structural redundancy in large-scale optimization models,” in: M.H. Karwan et al., eds.,Redundancy in Mathematical Programming (Springer, Berlin, 1983) pp. 145–169.
A.L. Brearley, G. Mitra and H.P. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm,”Mathematical Programming 8 (1) (1975) 54–83.
W.J. Carolan, J.E. Hill, J.L. Kennington, S. Niemi and S.J. Wichman, “An empirical evaluation of the KORBX algorithms for military airlift applications,”Operations Research 38 (2) (1990) 240–248.
S.F. Chang and S.T. McCormick, “A hierachical algorithm for making sparse matrices sparser,”Mathematical Programming 56 (1) (1992) 1–30.
J.J.H. Forrest and J.A. Tomlin, “Implementing the simplex method for optimization subroutine library,”IBM Systems Journal 31 (1) (1992) 11–25.
D.M. Gay, “Electronic mail distribution of linear programming test problems,”COAL Newsletter 13 (1985) 10–12.
M. Kojima, N. Megiddo and S. Mizuno, “A primal—dual infeasible-interior-point algorithm for linear programming,”Mathematical Programming 61 (3) (1993) 263–280.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “Computational experience with a primal—dual interior point method for linear programming,”Linear Algebra and its Applications 152 (1991) 191–222.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “The interaction of algorithms and architectures for interior point methods,” in: P.M. Pardalos, ed.,Advances in Optimization and Parallel Computing (North-Holland, Amsterdam, 1992) pp. 190–205.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “On implementing Mehrotra's predictor—corrector interior-point method for linear programming,”SIAM Journal on Optimization 2 (3) (1992) 435–449.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “Computational experience with a globally convergent primal—dual predictor—corrector algorithm for linear programming,”Mathematical Programming 66 (1) (1994) 123–135.
I.J. Lustig, R.E. Marsten and D.F. Shanno, “Interior point methods for linear programming: Computational state of the art,”ORSA Journal on Computing 6 (1) (1994) 1–15.
S. Mehrotra, “On the implementation of a primal—dual interior point method,”SIAM Journal on Optimization 2 (4) (1992) 575–601.
J.A. Tomlin and J.S. Welch, “Formal optimization of some reduced linear programming problems,”Mathematical Programming 27 (2) (1983) 232–240.
J.A. Tomlin and J.S. Welch, “A pathological case in the reduction of linear programs,”Operations Research Letters 2 (1983) 53–57.
J.A. Tomlin and J.S. Welch, “Finding duplicate rows in a linear program,”Operations Research Letters 5 (1986) 7–11.
H.P. Williams, “A reduction procedure for linear and integer programming models,” in: M.H. Karwan et al., eds.,Redundancy in Mathematical Programming (Springer, Berlin, 1983) pp. 87–109.
Scicon LTD, Sciconic user guide v2.00, 1990.
Author information
Authors and Affiliations
Additional information
This author was supported by a Danish SNF Research studentship.
Rights and permissions
About this article
Cite this article
Andersen, E.D., Andersen, K.D. Presolving in linear programming. Mathematical Programming 71, 221–245 (1995). https://doi.org/10.1007/BF01586000
Received:
Issue Date:
DOI: https://doi.org/10.1007/BF01586000