A heuristic approach for identification of redundant constraints in linear programming models
- 1 September 2006
- journal article
- research article
- Published by Taylor & Francis Ltd in International Journal of Computer Mathematics
- Vol. 83 (8-9), 675-683
- https://doi.org/10.1080/00207160601014148
Abstract
Linear programming (LP) is one of the most important techniques used in modelling and solving practical optimization problems that arise in industry, commerce, and management. When formulating an LP model, systems analysts and researchers often include all possible constraints although some of them may not be binding at the optimal solution. The presence of redundant constraints does not alter the optimum solution(s), but may consume extra computational effort. Many researchers have proposed algorithms for identifying the redundant constraints in LP models. Here we propose a heuristic approach using an intercept matrix to identify redundant constraints prior to the start of the solution process. An interesting observation of the proposal technique is that the tendency of variables to pop in and pop out of the basis is eradicated after eliminating the redundancies. The eradication of pop-in and pop-out substantially reduces the number of iterations. A significant reduction in the computational effort is achieved for LP problems of different sizes.Keywords
This publication has 9 references indexed in Scilit:
- Advanced preprocessing techniques for linear and quadratic programmingOR Spectrum, 2003
- Two direct methods in linear programmingEuropean Journal of Operational Research, 2001
- Robust Reduction of a Class of Large-Scale Linear ProgramsSIAM Journal on Optimization, 2001
- Presolve Analysis of Linear Programs Prior to Applying an Interior Point MethodINFORMS Journal on Computing, 1997
- Finding duplicate rows in a linear programming modelOperations Research Letters, 1986
- Identifying Redundant Constraints and Implicit Equalities in Systems of Linear ConstraintsManagement Science, 1983
- Redundancy in Mathematical ProgrammingPublished by Springer Science and Business Media LLC ,1983
- Analysis of mathematical programming problems prior to applying the simplex algorithmMathematical Programming, 1975
- An Algorithm for Determining Irrelevant Constraints and all Vertices in Systems of Linear InequalitiesOperations Research, 1973