IJSER Home >> Journal >> IJSER
International Journal of Scientific and Engineering Research
ISSN Online 2229-5518
ISSN Print: 2229-5518 8    
Website: http://www.ijser.org
scirp IJSER >> Volume 3,Issue 8,August 2012
A New Approach for Selecting a Constraint in Linear Programming Problems to Identify the Redundant Constraints
Full Text(PDF, )  PP.1345-1348  
Dr. S.Paulraj, Mrs. P.Sumathi
— linear programming, restrictive constraint, redundant constraints
Linear programming (LP) is one of the most important techniques used in modeling and solving practical optimisation prob-lems 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.
[1] E.D.Andersen and K.D.Andersen, “Presolving in linear programming”, Mathematical programming series B, vol.71, no. 2, pp. 221-245, 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.72-88, 1961.

[3] JE.Beasley, OR-Library, “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. 419-441, 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, 53-83, 1975.

[6] A.Boneh,S.Boneh and R.J.Caron, “Constraint classification in mathematical programming”, Math. Programming, vol. 61,no.1, pp. 61-73, 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. 225-237, 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.1401-1409, 2007.

[10] H.J.Greenberg, “Consistency redundancy and implied equalities in linear systems”, Ann.Math. artificial intelligence, vol.17, pp.37-83, 1996.

[11] Ilya Ioslovich, “Robust reduction of a class of large-scale 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. 247-260, 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.8-9, 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.1209-1222, 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. 588-608, 1996.

Untitled Page