×

A comparative study of redundant constraints identification methods in linear programming problems. (English) Zbl 1204.90069

Summary: The objective function and the constraints can be formulated as linear functions of independent variables in most of the real-world optimization problems. Linear Programming (LP) is the process of optimizing a linear function subject to a finite number of linear equality and inequality constraints. Solving linear programming problems efficiently has always been a fascinating pursuit for computer scientists and mathematicians. The computational complexity of any linear programming problem depends on the number of constraints and variables of the LP problem. Quite often large-scale LP problems may contain many constraints which are redundant or cause infeasibility on account of inefficient formulation or some errors in data input. The presence of redundant constraints does not alter the optimal solutions(s). Nevertheless, they may consume extra computational effort. Many researchers have proposed different approaches for identifying the redundant constraints in linear programming problems. This paper compares five of such methods and discusses the efficiency of each method by solving various size LP problems and netlib problems. The algorithms of each method are coded by using a computer programming language C. The computational results are presented and analyzed in this paper.

MSC:

90C05 Linear programming
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] E. D. Andersen and K. D. Andersen, “Presolving in linear programming,” Mathematical Programming. Series B, vol. 71, no. 2, pp. 221-245, 1995. · Zbl 0846.90068 · doi:10.1007/BF01586000
[2] M. L. Balinski, “An algorithm for finding all vertices of convex polyhedral sets,” Journal of the Society for Industrial and Applied Mathematics, vol. 9, no. 1, pp. 72-88, 1961. · Zbl 0108.33203 · doi:10.1137/0109008
[3] J. C. G. Boot, “On trivial and binding constraints in programming problems,” Management Science, vol. 8, no. 4, pp. 419-441, 1962. · Zbl 0995.90612 · doi:10.1287/mnsc.8.4.419
[4] A. L. Brearley, G. Mitra, and H. P. Williams, “Analysis of mathematical programming problems prior to applying the simplex algorithm,” Mathematical Programming, vol. 8, pp. 54-83, 1975. · Zbl 0317.90037 · doi:10.1007/BF01580428
[5] A. Boneh, S. Boneh, and R. J. Caron, “Constraint classification in mathematical programming,” Mathematical Programming, vol. 61, no. 1, pp. 61-73, 1993. · Zbl 0782.90104 · doi:10.1007/BF01582139
[6] R. J. Caron, J. F. McDonald, and C. M. Ponic, “A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary,” Journal of Optimization Theory and Applications, vol. 62, no. 2, pp. 225-237, 1989. · Zbl 0651.90047 · doi:10.1007/BF00941055
[7] T. Gal, “Weakly redundant constraints and their impact on post optimal analysis,” European Journal of Operational Research, vol. 60, pp. 315-326, 1979.
[8] P. O. Gutman and I. Isolovich, “Robust redundancy determination and evaluation of the dual variables of linear programming problems in the presence of uncertainty, on the generalized wolf problem: preprocessing of nonnegative large scale linear programming problems with group constraints,” Technion-Israel Institute of Technology, vol. 68, no. 8, pp. 1401-1409, 2007. · Zbl 1143.93303
[9] H. J. Greenberg, “Consistency, redundancy, and implied equalities in linear systems,” Mathematics and Artificial Intelligence, vol. 17, pp. 37-83, 1996. · Zbl 0887.90114 · doi:10.1007/BF02284624
[10] M. H. Karwan, V. Lotfi, J. Telgen, and S. Zionts, Eds., Redundancy in Mathematical Programming: A State-of-the-Art Survey, Springer, Berlin, Germany, 1983. · Zbl 0524.90058
[11] T. H. Mattheis, “An algorithm for determining irrelevant constraints and all vertices in systems of linear inequalities,” Operations Research, vol. 21, pp. 247-260, 1973. · Zbl 0265.90024 · doi:10.1287/opre.21.1.247
[12] J. Lisy, “Metody pro nalezini redundantnich omezeni vulohach linerniho programovani. Ekonomicko MatematicS,” Obzor, vol. 7, no. 3, pp. 285-298, 1971.
[13] N. V. Stojković and P. S. Stanimirović, “Two direct methods in linear programming,” European Journal of Operational Research, vol. 131, no. 2, pp. 417-439, 2001. · Zbl 0991.90087 · doi:10.1016/S0377-2217(00)00083-7
[14] S. Paulraj, C. Chellappan, and T. R. Natesan, “A heuristic approach for identification of redundant constraints in linear programming models,” International Journal of Computer Mathematics, vol. 83, no. 8-9, pp. 675-683, 2006. · Zbl 1128.90040 · doi:10.1080/00207160601014148
[15] J. Telgen, “Identifying redundant constraints and implicit equalities in system of linear constraints,” Management Science, vol. 29, no. 10, pp. 1209-1222, 1983. · Zbl 0527.90066 · doi:10.1287/mnsc.29.10.1209
[16] G. L. Thompson, F. M. Tonge, and S. Zionts, “Techniques for removing nonbinding constraints and extraneous variables from linear programming problems,” Management Science, vol. 12, no. 7, pp. 588-608, 1996. · Zbl 0135.19904 · doi:10.1287/mnsc.12.7.588
[17] S. Zionts, Size of reduction techniques of linear programming and their applications, Dissertation, Carnegie Institute of Technology, 1965.
[18] “Netlib problems,” http://ftp.zib.de/pub/mp-testdata/madlib/node2.html.
[19] J. E. Beasley, “Distributing test problems by electronic mail,” Journal of Operational Research Society, vol. 41, pp. 1069-1107, 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.