Home          
 
Short Presentations Accepted
 
 
     Identifying Redundant Constraints in Linear Programming Models
     Presenter: Alejo Mosso Vãzquez
     Co-Authors: David Juãrez-Romero & Marco Antonio Cruz-Chãvez
Abstract

In this paper a method for the identification of redundant constraints in a finite set of linear inequalities in the n-dimensional Euclidian Space is presented. The identification is based on the minimization of the distance of the hyperplane of a restriction from the polyhedron of feasible solutions of the set of inequalities. The minimization problem is formulated by a linear programming model on the given inequalities set, which is designed from Fase I method of the Simplex algorithm. By means of this minimization, the redundant condition of a restriction and of those restrictions adjoining vertexes visited by the Simplex algorithm are determined by applying in each vertex a criterion called raw criterion. The proposed method is compared to two methods based on the convex hull of the gradients of the linear inequalities: the first method identifies the redundant condition of just one restriction based on convex combinations; the second identifies redundancies based on the construction of the convex hull of the complete set of constraints, whose complexity is exponential. Our method has advantage over the first method because it identifies also a set of constraints and reduces the problem dimension by one each time a redundant constraint is identified and suppressed. Our method is superior to the second method because its complexity is comparable with that of the Simplex algorithm. The validity and computational efficiency of the method presented in this paper for redundancy identification are described using two-dimension instances.

 

SDSU: Computational Science and Engineering Gateway to Latin America

Last updated: March 16, 2010 9:10 AM