A comparative study of redundant constraints identification methods for Linear Programming problems
Main Article Content
Abstract
Linear programming (LP) is one of the most important methods used in modeling and solving to manage the resources effectively. Formulating LP model may include the redundant constraints so it takes more time-consuming to achieve the optimal solutions.
In this paper, we study and compare the three methods to identify the redundant constraints to reduce time-consuming but not alter the optimal solutions.
Article Details

This work is licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives 4.0 International License.
The Journal of Science and Science Education (JSSE) retain the right of all articles published in JSSE. The coresponding author or the authorized person on behalf of the authors must send the complete Copyright Transfer Form to JSSE before any article get published in JSSE.
Copyright Transfer Form
The JSSE request the coresponding author or the authorized person on behalf of the authors upload the manuscript under the together with the Copyright Transfer Form under the supplementary data. The guidline for uploading both manuscript and Copyright Transfer Form is shown below:
1. Upload the manuscript in the sub-menu, Article Component > Article Text.
2. Upload the the Copyright Transfer Form in the sub-menu, Article Component > Other.
Download Copyright Transfer Form
References
Brearley, A. L., Mitra, G., and Williams, H. P. (1975). Analysis of mathematical programming problems prior to applying the simplex algorithm. Mathematical Programming, 8(1), 54-83.
Caron, R. J., McDonald, J. F., and Ponic, C. M. (1989). A degenerate extreme point strategy for the classification of linear constraints as redundant or necessary. Journal of Optimization Theory and Applications, 62(2), 225-237.
Estiningsih, Y., Farikhin, and Tjahjana, R. H. (2019). Some methods for identifying redundant constraints in linear programming. Journal of Physics: Conference Series, 1321, 022073.
Ioslovich, I. (2001). Robust reduction of a class of large-scale linear programs. SIAM journal on Optimization, 12(1), 262-282.
Paulraj, S., Chellappan, C., and Natesan, T. R. (2006). A heuristic approach for identification of redundant constraints in linear programming models. International Journal of Computer and Mathematics, 83(8-9), 675-683.
Paulraj, S. and Sumathi, P. (2010). A Comparative Study of Redundant Constraints Identification Methods in Linear Programming Problems. Mathematical Problems in Engineering, 2010, 723402.
Paulraj, S. and Sumathi, P. (2012). A new approach for selecting a constraint in linear programming problems to identify the redundant constraints. International Journal of Scientific and Engineering Research, 3(8), 1345-1348.
Stojković, N. V. and Stanimirović, P. S. (2001). Two direct methods in linear programming. European Journal of Operation Research, 131(2), 417-439.
Telgen, J. (1979). On R. W. Llewellyn’s rules to identify redundant constraints: A detailed critique and some generalizations. Zeitschrift Für Operations Research, 23(5), 197–206.
Telgen, J. (1983). Identifying redundant constraints and implicit equalities in systems of linear constraints. Management Science, 29(10), 1209-1222.