×

Presolving in linear programming. (English) Zbl 0846.90068

Summary: 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. 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 problem (Gay, 1985) are reported to illustrate the efficiency of the presolve methods.

MSC:

90C05 Linear programming

Software:

CPLEX; KORBX; SCICONIC; OSL
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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. · Zbl 0752.90043 · doi:10.1287/ijoc.1.2.84
[2] 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. · Zbl 0682.90061 · doi:10.1007/BF01587095
[3] R. Anbil, R. Tanga and E.L. Johnson, ”A global approach to crew-pairing optimization,”IBM Systems Journal 31 (1) (1992) 71–78. · Zbl 0814.90044 · doi:10.1147/sj.311.0071
[4] E.D. Andersen, ”Finding all linearly dependent rows in large-scale linear programming,”Optimization Methods and Software, to appear.
[5] R.E. Bixby, ”Implementing the simplex method: The initial basis,”ORSA Journal on Computing 4 (3) (1992) 267–284. · Zbl 0759.90063 · doi:10.1287/ijoc.4.3.267
[6] R.E. Bixby, ”Progress in linear programming,”ORSA Journal on Computing 6 (1) (1994) 15–22. · Zbl 0798.90101 · doi:10.1287/ijoc.6.1.15
[7] 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. · Zbl 0758.90056 · doi:10.1287/opre.40.5.885
[8] 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.
[9] 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. · Zbl 0317.90037 · doi:10.1007/BF01580428
[10] 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. · doi:10.1287/opre.38.2.240
[11] S.F. Chang and S.T. McCormick, ”A hierachical algorithm for making sparse matrices sparser,”Mathematical Programming 56 (1) (1992) 1–30. · Zbl 0770.90039 · doi:10.1007/BF01580890
[12] J.J.H. Forrest and J.A. Tomlin, ”Implementing the simplex method for optimization subroutine library,”IBM Systems Journal 31 (1) (1992) 11–25. · Zbl 0814.90075 · doi:10.1147/sj.311.0011
[13] D.M. Gay, ”Electronic mail distribution of linear programming test problems,”COAL Newsletter 13 (1985) 10–12.
[14] M. Kojima, N. Megiddo and S. Mizuno, ”A primal–dual infeasible-interior-point algorithm for linear programming,”Mathematical Programming 61 (3) (1993) 263–280. · Zbl 0808.90093 · doi:10.1007/BF01582151
[15] 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. · Zbl 0731.65049 · doi:10.1016/0024-3795(91)90275-2
[16] 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. · Zbl 0814.90080
[17] 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. · Zbl 0771.90066 · doi:10.1137/0802022
[18] 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. · Zbl 0811.90068 · doi:10.1007/BF01581140
[19] 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. · Zbl 0798.90100 · doi:10.1287/ijoc.6.1.1
[20] S. Mehrotra, ”On the implementation of a primal–dual interior point method,”SIAM Journal on Optimization 2 (4) (1992) 575–601. · Zbl 0773.90047 · doi:10.1137/0802028
[21] J.A. Tomlin and J.S. Welch, ”Formal optimization of some reduced linear programming problems,”Mathematical Programming 27 (2) (1983) 232–240. · Zbl 0535.90059 · doi:10.1007/BF02591947
[22] J.A. Tomlin and J.S. Welch, ”A pathological case in the reduction of linear programs,”Operations Research Letters 2 (1983) 53–57. · Zbl 0506.90050 · doi:10.1016/0167-6377(83)90036-6
[23] J.A. Tomlin and J.S. Welch, ”Finding duplicate rows in a linear program,”Operations Research Letters 5 (1986) 7–11. · Zbl 0621.65058 · doi:10.1016/0167-6377(86)90093-3
[24] 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.
[25] Scicon LTD, Sciconic user guide v2.00, 1990.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.