Mathematical Problems in Engineering
Volume 2010 (2010), Article ID 723402, 16 pages
Research Article

A Comparative Study of Redundant Constraints Identification Methods in Linear Programming Problems

1Department of Mathematics, Madras Institute of Technology Campus, Anna University, Chromepet, Chennai, Tamil Nadu 600 044, India
2Anna University, Chennai, Tamil Nadu, India

Received 7 January 2010; Revised 15 April 2010; Accepted 21 September 2010

Academic Editor: Joaquim J. Júdice

Copyright © 2010 Paulraj S. and Sumathi P. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


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.