A heuristic approach for identification of redundant constraints in linear programming models

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:

• Linear programming
• Optimization
• Redundant Constraints
• Intercept matrix
• Model reduction