A New Approach for Selecting a Constraint in Linear Programming Problems to Identify the Redundant Constraints

Full Text(PDF, ) PP.13451348


Author(s) 
Dr. S.Paulraj, Mrs. P.Sumathi 

KEYWORDS 
— linear programming, restrictive constraint, redundant constraints 

ABSTRACT 
Linear programming (LP) is one of the most important techniques used in modeling and solving practical optimisation problems that arise in industry, commerce and management. It is well known that, for largest LP problems, only a relatively small percentage of constraints are binding at the optimal solution. In fact, large LP problems almost contain a significant number of redundant constraints and variables. Therefore it is worthwhile to devote some efforts in presolving for considerable reduction in the size of the problem. This paper presents a new approach for selecting a constraint in linear programming problems to identify the redundant constraints. The algorithm is coded by using a computer programming language C. The computational results are presented and analyzed in this paper. 

References 

[1] E.D.Andersen and K.D.Andersen, “Presolving in linear programming”, Mathematical programming series B, vol.71, no. 2, pp. 221245,
1995.
[2] M.L.Balinski , “An algorithm for finding all vertices of convex polyhedral sets”, J.Soc. Indust Appl. Math, vol.9, no.1, pp.7288, 1961.
[3] JE.Beasley, ORLibrary, “Distributing test problems by electronic
mail”, Journal of operational research society, vol.41, (1990), pp 1069
1072.
[4] J.C.G.Boot, “On trivial and binding constraints in programming
problems”, Management science, vol.8, no.4, pp. 419441, 1962.
[5] A.L.Brearley, G.Mitra and H.P.Williams, “Analysis of mathematical
programming problems prior to applying the simplex algorithm”,
Mathematical programming, vol. 8,no.1, pp, 5383, 1975.
[6] A.Boneh,S.Boneh and R.J.Caron, “Constraint classification in mathematical programming”, Math. Programming, vol. 61,no.1, pp. 6173,
1993.
[7] R.J.Caron, J.F.McDonald, and C.M.Ponic, “A degenerate extreme
point strategy for the classification of linear constraints as redundant
or necessary”, journal of optimisation theory and application, vol.62,
no.2, pp. 225237, 1989.
[8] T.Gal, “Weakly redundant constraints and their impact on post optimal analysis”, European journal of operational research. vol.60, pp.315
326, 1979.
[9] P.O.Gutman and I.Isolovich, “On the generalized wolf Problem: Preprocessing of nonnegative large scale linear programming
problems with group constraints”, Automation and remote control.vol.68, no.8, pp.14011409, 2007.
[10] H.J.Greenberg, “Consistency redundancy and implied equalities in
linear systems”, Ann.Math. artificial intelligence, vol.17, pp.3783, 1996.
[11] Ilya Ioslovich, “Robust reduction of a class of largescale linear programs”, Siam journal of optimization, vol.12,no.1, pp.262 – 282, 2001.
[12] T.H.Mattheis, “An algorithm for determining irrelevant constraints
and all vertices in systems of linear inequalities”, Operations Research.,
vol.21, pp. 247260, 1973.
[13] N.V.Stojkovic and P.S.Stanimirovic,“Two direct methods of linear
programming”, European Journal of Operational Research, vol.131,no.2,
pp.417– 439, 2001.
[14] S.Paulraj, C.Chellappan and T.R.Natesan, “A heuristic approach
for identification of redundant constraints in linear programming
models”, International Journal of Computer Mathematics, vol.83, no.89,
pp.675–683, 2006.
[15] S.Paulraj and P.Sumathi, “A Comparative Study of Redundant constraints Identification Methods in Linear Programming Problems”,
Mathematical Problems in Engineering, Hindawi Publishing Corporation,
Article ID 723402, 2010.
[16] J.Telgan, “Identifying redundant constraints and implicit equalities
in system of linear constraints.” Management Science, vol.29, no.10,
pp.12091222, 1983.
[17] G.L.Thompson, F.M.Tonge and S.Zionts , “Techniques for removing
nonbinding constraints and extraneous variables from linear programming problems”, Management Science, vol. 12, no.7, pp. 588608,
1996.


