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

How to Cite
โบจรัส ร. (2022). A comparative study of redundant constraints identification methods for Linear Programming problems. Journal of Science and Science Education (JSSE), 5(1), 141–147. https://doi.org/10.14456/jsse.2022.12
Section
Academic Articles in Science

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.