Identification of redundancies in a LP problem with mixed set of constraints
by
V.C. Jacob
Anna University, Madras, India
Coauthors: T.R. Natesan (Professor Emeritus - AICTE), V. Rhymend (Uthariaraj, Senior Lecturer in Systems Programming), P. Narayanasamy (Senior Lecturer in Operations Research and System Programming)

A generalized Linear Programming Problem (LPP) consists inequality constraints of the upper and lower bound types besides few equalities. Equalities are the most stringent constraints to be met while solving LP- Problems . This article develops a heuristic algorithm to detect redundancies apriori in a given general LP model incorporating mixed set of constraints. A "Matrix of Intercepts" of the inequality constraints is constructed to identify redundancies ignoring initially the set of equality constraints from the original problem. No equality constraint can be redundant in a LP model if there is an optimal solution. Redundancies among the inequalities are identified and a reduced model dropping the equality constraints is constructed. The optimal solution of the reduced model is obtained. If the reduced model's optimal solution satisfies some of the identified redundant constraints then their redundancies are confirmed. If not the balance of the apriori identified redundancies are validated by bringing them one by one into the basis using the post optimality or sensitivity analysis. Since no equality constraint can be redundant they are included in the reduced model one after the other and the solution is updated. The original LP model is solved and a comparison of the computational efforts required to solve the original and the reduced model is made. The speed of computation ratio is compared. The proposed algorithm when applied to solve the reduced model has resulted considerable saving in time. The article also illustrates taking transportation and assignment problems to show that none of the constraints can be redundant since they are all equalities. A computer code has been developed in C++ to solve a set of problem down loaded from the netlib of the Internet. Key words : Matrix of Intercept , redundancies , apriori upper bound and lower bound

Date received: January 7, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cadt-02.