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

Authors: Paulraj S.; Sumathi P.
Journal: Mathematical Problems in Engineering
 (2010)

---

## Abstract

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.


---

## Body

## 1. Introduction

Many researchers [1–17] have proposed different algorithms to identify the redundancies and removed them to get a reduced model for linear programming. In 1965, Zionts [17] suggested some improvements upon the implementation of Boot method, but not to the point where it achieved practical value. In addition, a number of other methods were developed that deal with redundancy, among which the geometric vertex enumeration method is the most well known. In geometric vertex enumeration method, the essential characteristic is the establishment of a number of situations in which redundancy can be recognized immediately without further computations.In 1971, Lisy [12] used the rules given by Ziont to identify all redundant constraints in systems of linear constraints. Gal [7] enlarged this approach by adding rules for situations in which constraints can be identified immediately as being nonredundant. Gal proposed another method to classify constraints as redundant or necessary. They produce results that are unconditionally correct; they perform iterations of an active set linear programming algorithm. Later Caron et al. [6] appended the above methods by adding rules to deal with degeneracy.Brearly et al. [4] proposed a simple method to identify redundant constraints from a system of linear constraints. This method involves the lower and upper bounds of the variables.  Telgan [15] proposed a deterministic method to identify redundant constraints by using minimum ratio criteria as in simplex method. Stojković and Stanimirović [13] proposed a method to identify redundant constraints by applying the maximum and minimum principle. Paulraj et al. [14] proposed a heuristic method to identify redundant constraints by using the intercept matrix of constraints of a linear programming problem. Gutman and Ioslovich [8] described a new approach to preprocess nonnegative large-scale problems so as to reduce the dimensions considerably by defining and removing redundant constraints and variables. This test is applicable to all nonnegative large-scale linear programming problem with group constraints. Group constraints only contain zeros and ones coefficients. Constraints and variables are removed by primal and dual tests. This method is applicable to constraints of knapsack problems.A brief introduction to the redundant constraints of linear programming problems is presented in Section2. Section 3 discusses the methods for identifying redundant constraints in linear problems. Section 4 deals with the computational results of the methods, and Section 5 concludes the paper.


## 2. Redundant Constraints

A redundant constraint is a constraint that can be removed from a system of linear constraints without changing the feasible region.Consider the following system ofm nonnegative linear inequality constraints and n variables (m≥n):
(2.1)AX≤b,X≥0,
where A∈Rmxn,b∈Rm,X∈Rn, and 0∈Rn.LetAiX≤bi be the ith constraint of the system (2.1) and let S={X∈Rn/AiX≤bi,X≥0} be the feasible region associated with system (2.1).LetSk={X∈Rn/AiX≤bi,X≥0,i≠k} be the feasible region associated with the system of equations AiX≤bi,i=1,2,…,m,i≠k. The kth constraint AkX≤bk(1≤k≤m) is redundant for the system (2.1) if and only if  S=Sk.Definition 2.1.
Redundant constraints can be classified as weakly and strongly redundant constraints.Weakly Redundant Constraints
The constraintAiX≤bi is weakly redundant if it is redundant and AiX=bi for some X∈S.Strongly Redundant Constraints
The constraintAiX≤bi is strongly redundant if it is redundant and AiX<bi for all X∈S.Binding Constraint
Binding constraint is the one which passes through the optimal solution point. It is also called a relevant constraint.Nonbinding Constraint
Nonbinding constraint is the one which does not pass through the optimal solution point.  But it can determine the boundary of the feasible region.Example 2.2.
Consider the following linear inequality constraints:
(1)2x1+1x2≤8,
(2)4x1+0x2≤15,
(3)1x1+3x2≤9,
(4)1x1+2x2≤14,
(5)1x2≤4,
(6)1x1+1x2≤5,
wherex1+x2≤0.
In  Figure1, the region OABCD is the feasible region and the vertex C is the optimal point. The constraints (1), (3), and (6) are binding, (4) and (5) are strictly redundant. The 2nd constraint is non-binding. Among the binding constraints, (6) is weakly redundant.Figure 1


## 3. Methods for Identification of Redundant Constraints

Many methods are available in the literature to identify the redundant constraints in linear programming problems. In this paper, the following five methods are discussed and compared(1)
bounds method [4](2)
linear programming method [6](3)
deterministic method [15](4)
stojković and Stanimirović method [13](5)
heuristic method [14].


### 3.1. Bounds Method

Brearly et al. [4] proposed a simple method for identifying redundant constraints for a Linear Programming Problem (LPP) with bounded variables. This method involves the lower and upper bounds of the variables. The upper and lower bounds of each constraint are computed and compared with the right-hand side of that constraint to decide if it is a redundant constraint or not.Procedure of the Method.
The general form of an LPP with bounded variables is(3.1)max⁡⁡z=∑j=1ncjxj,Subjectto∑j=1naijxj≤bi(i=1,2,…,m),lj≤xj≤uj(j=1,2,…,n).Step 1.
Compute upper and lower bounds for each constraint by(3.2)Ui=∑j∈Piaijuj+∑j∈Niaijlj,Li=∑j∈Piaijlj+∑j∈Niaijuj,
where Pi={j;aij>0}, and Ni={j;aij<0}, Li may be 0, and Ui may be +∞.Step 2.
Test whetherUi≤bi,i=1,2,…,m. The ith constraint ∑j=1naijxj≤bi is redundant if Ui≤bi.Example 3.1.
Consider the following LPP:(3.3)max⁡z=4x1+2x2+x3,subject  to2x1+x2+x3≤30,3x1+x2+x3≤26,x2+x3≤13,x1+2x2+x3≤45,0≤x1≤8.67,0≤x2≤13,0≤x3≤13.Solution 1.
Step 1.
Define(3.4)P1={1,2,3},N1=φ,P2={1,2,3},N2=φ,P3={2,3},N3=φ,P4={1,2,3},N4=φ,
where φ is the empty set.Step 2.
Compute(3.5)L1=0,U1=17.34+13+13=43.34,L2=0,U2=26.01+13+13=52.01,L3=0,U3=13+13=26,L4=0,U4=8.67+26+13=47.67.
Since all Ui≥bi, i=1,2,3,4, there is no redundant constraint found by this method.


### 3.2. Linear Programming Method

Caron et al. [6] developed an algorithm for identifying redundant constraints. This method will take more computational effort to identify the redundant constraints. To identify the redundant constraints, the left-hand side of each constraint is optimized subject to the remaining constraints. The optimal objective functional value is compared with the right-hand side value of corresponding constraints to decide if it is redundant or not. In this method, the objective function of the original LPP is not considered.LetP denote the given linear programming problem.LetPi denote the LP Problem without the ith constraint ∑j=1naijxj≤bi of P and let the objective function of LP problem Pi be maxzi=∑j=1naijxj.Step 1.
Find the optimal objective function value to the problemPi, i=1,2,…,m, by using the simplex method. Let zi be the optimal objective function value of problem Pi.Step 2.
Check whetherzi≤bi. The ith constraint ∑j=1naijxj≤bi is redundant if zi≤bi.
Otherwise, it is not redundant.Example 3.2.
Consider the Example3.1 presented in Section 3.1.Solution 2.
By solving the above Example3.2, we get z=43.33,  x1=4.33,  x2=13.00, and x3=0.Step 1.
Fori=1,2,3,4, consider the problem Pi as follows:
(3.6)max⁡⁡zi=left-handsideofconstrainti,subjectto3x1+x2+x3≤26,x2+x3≤13,x1+2x2+x3≤45,x1,x2,x3≥0.
Using the simplex method,the solution of problemP1 is z1=21.67, x1=4.33, x2=13.00, and x3=0.00.the solution of problemP2 is z2=45, x1=15, x2=0.00, and x3=0.00.the solution of problemP3 is z3=26, x1=0.0, x2=19.00, and x3=7.00.the solution of problemP4 is z4=30.33, x1=4.33, x2=13.0, and x3=0.00.Step 2.
Herez1<b1,z2>b2,z3>b3, and z4<b4. Therefore, the constraints (1) and (4) are redundant.


### 3.3. Deterministic Method

Telgan [15] developed an algorithm for identifying redundant constraints and implicit equalities in system of linear constraints using minimum ratio criteria as in the simplex method.Procedure of the Method
Assume that a basic feasible solution is given, and the corresponding contracted simplex tableau is set up. Letyij be the entries of this tableau with yi0 the right-hand side coefficients, and let xjB and xjN represent the basic and nonbasic variables, respectively.  Let H be the set of all indices of constraints to be identified as either redundant or nonredundant.
Letuk be the slack variable corresponding to the kth constraint.
Step 1.
If the solution is nondegenerate, alluk=xjN correspond to nonredundant inequalities, remove k from H and continue with Step 3.Step 2.
In a degenerate solution check all nonbasic variablesuk=xpN with k∈H. Check the property yip≥0 for alli with yi0=0. If this holds, then the constraint Akx≤bk is not redundant, and remove k from H.Step 3.
Check all basic variablesuk=xrB with k∈H for the property yij≤ 0 for all j. If this holds, then the constraint Akx≤bk is redundant, and remove k from H.Step 4.
Check all basic variablesuk=xiB with k∈H for the property yr0/yrs=min{yio/yis,yis>0} is attained at a unique r for some s. If this holds, the constraint Akx≤bk is not redundant, and remove k from H.Step 5.
IfH=φ, then stop. Else, go to Step 6.Step 6.
If there is no basic variableuk=xiB with k∈H, then introduce a nonbasic variable  uk=xjN with k∈H (e.g., the one with the smallest index k) into the basis and continue with Step 1.Step 7.
Select a basic variableuk=xjB with k∈H (e.g., the one with the smallest index k) and perform a feasible pivot step in column p with yip=maxyij. Continue with Step 1.Example 3.3.
Consider Example3.1 presented in Section 3.1.Solution 3.
Iteration.
Contracted simplex table, see Table1.Step 1.
x1≥0,x2≥0, and x3≥0 are not redundant.Step 4.
Now, divide the RHS values by the first column and take the minimum of itmin{15,8.66,-,45}=8.66, which corresponds to the 2nd row. Therefore, constraint (2) is not redundant. Now, H={1,3,4}.Step 7.
Selectu1 and find the maximum {2,1,1}=2, which corresponds to the 1st column. Therefore, pivoting on y21, we obtain, see what is Table 2.Iteration.
Divide the RHS values by the 2nd column and take minimum of it.min{38,26,13,21.8}=13, which corresponds to the 3rd row. Therefore, constraint (3) is not redundant. Now, H={1,4}.Step 4.
Selectingu1,u3 we cannot pivot. So select u4 and the maximum {-1/3,5/3,2/3}=5/3 corresponds to the 2nd column. Therefore, pivoting on y32, we obtain, see what is Table 3.Step 3.
In the first and last row, all the coefficients are ≤0.Step 5.
H=φ. Therefore, Constraints (1) and (4) are redundant.Table 1x1x2x3RHSu121130u231126u301113u412145HereH={1,2,3,4}.Table 2u2x2x3RHSu1−2/31/31/338/3x11/31/31/326/3u301113u4−1/35/32/3109/3Table 3u2u3x3RHSu1−2/3−1/3025/3x11/3−1/3013/3x201113u4−1/3−5/3−144/3


### 3.4. Stojković and Stanimirović Method

This method is proposed by Stojković and Stanimirović [13]. It is a simple method. It verifies the existence of the saddle point of payoff matrix for the game problem by applying the maxmin and minmax principles.Procedure of the Method
Step 1.
Computedij=aij/bicj,i=1,2,…,m, and j=1,2,…,n.Step 2.
Ifmax1≤i≤mmin1≤j≤ndij=min1≤i≤nmax1≤i≤mdij, then there are no redundant constraints. Stop.
Else, if there existk and l such that dkj≤dlj, for all j=1,2,…, then the kth constraint is redundant.Example 3.4.
Consider the Example3.1 presented in Section 3.1.Solution 4.
Step 1.
(3.7)dij=[212016013031041521260521261131180290145]=min⁡[0.016660.016660.03330.028850.019230.03850.00.03850.07690.00550.02220.0222]0.016660.019230.00.0055.max⁡0.028850.03850.0769Step 2.
(3.8)max⁡1≤i≤4⁡min⁡1≤j≤3⁡dij=0.01923,min⁡1≤j≤3max⁡1≤i≤4⁡dij=0.02855,max⁡1≤i≤3⁡min⁡1≤j≤4⁡dij≠min⁡1≤j≤4⁡max⁡1≤i≤4⁡dij.
There must be at least one redundant constraint in the above problem.
Hered1j≤d2j, j=1,2,3, hence the constraint (1) is redundant.


### 3.5. Heuristic Method

Paulraj et al. [14] proposed a heuristic method to identify redundant constraint by using the intercept matrix of constraints of a linear programming problem.Procedure of the Method
Step 1.
LetI be the set of subscripts associated with the initial basic variables (slack variables). Initially let that set be I={1,2,…,m}.
LetJ be the set of subscripts associated with the initial decision variables. Initially let that set be J={1,2,…,n}.Step 2.
Construct an intercept matrix “θ” using the following relationship
(3.9)θji=biaij,aij>0,forj∈J,i∈I.Step 3.
Determine the entering variables making use of the following steps.(i)
Calculatezj-cj=CBB-1aj-cj for all nonbasic variables aj=(a1j,a2j,…,amj)T.(ii)
Letβj=min{θji}, forj∈J,i∈I.(iii)
Computezj′-cj′=βj(zj-cj) forj∈J.Step 4.
(i) Letzk′-ck′=minj∈J{zj′-cj′}.
(ii) Ifzk′-ck′≥0, then the problem has no redundant constraints and stop.
(iii) Otherwise, take away the elementk from the set J, that is, J=J-{k}.
(iv) Letθkl=mini∈I{θki}=βk.
(v) Take away the element l from the setI, that is, I=I-{l}.
(vi) Findp such that min {θpl}=βp for p∈J. If so, take away such p elements from the set J, that is, J=J-{p}.Step 5.
IfJ=φ, then go to Step 6. Otherwise, go to Step 4.Step 6.
IfI=φ, then the problem has no redundant constraints and stop. Otherwise, all the constraints i∈I whose intercepts on coordinate axis j satisfy the condition θji≥max{βj} where i∈I and j=1,2,…,n are redundant. Stop.Example 3.5.
Consider the Example3.1 presented in Section 3.1Solution 5.
Step 1.
(i)I={1,2,3,4}, (ii)  J={1,2,3}.Step 2.
[see Table4].Step 3.
[see Table4].Step 4.
[see Table5].Step 5.
J=φ. Constraints (1) and (4) are redundant constraints.Table 4Basic variablesDecision variablesS1S2S3S4zj-cjβjzj′-cj′X1158.67—45−48.67−34.68X230261322.5−213−26X330261345−113−13Table 5Iteration numberkJlIJ11{2,3}2{1,3,4}{2,3}22{3}3{1,4}{3}33Φ3{1,4}φ


## 3.1. Bounds Method

Brearly et al. [4] proposed a simple method for identifying redundant constraints for a Linear Programming Problem (LPP) with bounded variables. This method involves the lower and upper bounds of the variables. The upper and lower bounds of each constraint are computed and compared with the right-hand side of that constraint to decide if it is a redundant constraint or not.Procedure of the Method.
The general form of an LPP with bounded variables is(3.1)max⁡⁡z=∑j=1ncjxj,Subjectto∑j=1naijxj≤bi(i=1,2,…,m),lj≤xj≤uj(j=1,2,…,n).Step 1.
Compute upper and lower bounds for each constraint by(3.2)Ui=∑j∈Piaijuj+∑j∈Niaijlj,Li=∑j∈Piaijlj+∑j∈Niaijuj,
where Pi={j;aij>0}, and Ni={j;aij<0}, Li may be 0, and Ui may be +∞.Step 2.
Test whetherUi≤bi,i=1,2,…,m. The ith constraint ∑j=1naijxj≤bi is redundant if Ui≤bi.Example 3.1.
Consider the following LPP:(3.3)max⁡z=4x1+2x2+x3,subject  to2x1+x2+x3≤30,3x1+x2+x3≤26,x2+x3≤13,x1+2x2+x3≤45,0≤x1≤8.67,0≤x2≤13,0≤x3≤13.Solution 1.
Step 1.
Define(3.4)P1={1,2,3},N1=φ,P2={1,2,3},N2=φ,P3={2,3},N3=φ,P4={1,2,3},N4=φ,
where φ is the empty set.Step 2.
Compute(3.5)L1=0,U1=17.34+13+13=43.34,L2=0,U2=26.01+13+13=52.01,L3=0,U3=13+13=26,L4=0,U4=8.67+26+13=47.67.
Since all Ui≥bi, i=1,2,3,4, there is no redundant constraint found by this method.


## 3.2. Linear Programming Method

Caron et al. [6] developed an algorithm for identifying redundant constraints. This method will take more computational effort to identify the redundant constraints. To identify the redundant constraints, the left-hand side of each constraint is optimized subject to the remaining constraints. The optimal objective functional value is compared with the right-hand side value of corresponding constraints to decide if it is redundant or not. In this method, the objective function of the original LPP is not considered.LetP denote the given linear programming problem.LetPi denote the LP Problem without the ith constraint ∑j=1naijxj≤bi of P and let the objective function of LP problem Pi be maxzi=∑j=1naijxj.Step 1.
Find the optimal objective function value to the problemPi, i=1,2,…,m, by using the simplex method. Let zi be the optimal objective function value of problem Pi.Step 2.
Check whetherzi≤bi. The ith constraint ∑j=1naijxj≤bi is redundant if zi≤bi.
Otherwise, it is not redundant.Example 3.2.
Consider the Example3.1 presented in Section 3.1.Solution 2.
By solving the above Example3.2, we get z=43.33,  x1=4.33,  x2=13.00, and x3=0.Step 1.
Fori=1,2,3,4, consider the problem Pi as follows:
(3.6)max⁡⁡zi=left-handsideofconstrainti,subjectto3x1+x2+x3≤26,x2+x3≤13,x1+2x2+x3≤45,x1,x2,x3≥0.
Using the simplex method,the solution of problemP1 is z1=21.67, x1=4.33, x2=13.00, and x3=0.00.the solution of problemP2 is z2=45, x1=15, x2=0.00, and x3=0.00.the solution of problemP3 is z3=26, x1=0.0, x2=19.00, and x3=7.00.the solution of problemP4 is z4=30.33, x1=4.33, x2=13.0, and x3=0.00.Step 2.
Herez1<b1,z2>b2,z3>b3, and z4<b4. Therefore, the constraints (1) and (4) are redundant.


## 3.3. Deterministic Method

Telgan [15] developed an algorithm for identifying redundant constraints and implicit equalities in system of linear constraints using minimum ratio criteria as in the simplex method.Procedure of the Method
Assume that a basic feasible solution is given, and the corresponding contracted simplex tableau is set up. Letyij be the entries of this tableau with yi0 the right-hand side coefficients, and let xjB and xjN represent the basic and nonbasic variables, respectively.  Let H be the set of all indices of constraints to be identified as either redundant or nonredundant.
Letuk be the slack variable corresponding to the kth constraint.
Step 1.
If the solution is nondegenerate, alluk=xjN correspond to nonredundant inequalities, remove k from H and continue with Step 3.Step 2.
In a degenerate solution check all nonbasic variablesuk=xpN with k∈H. Check the property yip≥0 for alli with yi0=0. If this holds, then the constraint Akx≤bk is not redundant, and remove k from H.Step 3.
Check all basic variablesuk=xrB with k∈H for the property yij≤ 0 for all j. If this holds, then the constraint Akx≤bk is redundant, and remove k from H.Step 4.
Check all basic variablesuk=xiB with k∈H for the property yr0/yrs=min{yio/yis,yis>0} is attained at a unique r for some s. If this holds, the constraint Akx≤bk is not redundant, and remove k from H.Step 5.
IfH=φ, then stop. Else, go to Step 6.Step 6.
If there is no basic variableuk=xiB with k∈H, then introduce a nonbasic variable  uk=xjN with k∈H (e.g., the one with the smallest index k) into the basis and continue with Step 1.Step 7.
Select a basic variableuk=xjB with k∈H (e.g., the one with the smallest index k) and perform a feasible pivot step in column p with yip=maxyij. Continue with Step 1.Example 3.3.
Consider Example3.1 presented in Section 3.1.Solution 3.
Iteration.
Contracted simplex table, see Table1.Step 1.
x1≥0,x2≥0, and x3≥0 are not redundant.Step 4.
Now, divide the RHS values by the first column and take the minimum of itmin{15,8.66,-,45}=8.66, which corresponds to the 2nd row. Therefore, constraint (2) is not redundant. Now, H={1,3,4}.Step 7.
Selectu1 and find the maximum {2,1,1}=2, which corresponds to the 1st column. Therefore, pivoting on y21, we obtain, see what is Table 2.Iteration.
Divide the RHS values by the 2nd column and take minimum of it.min{38,26,13,21.8}=13, which corresponds to the 3rd row. Therefore, constraint (3) is not redundant. Now, H={1,4}.Step 4.
Selectingu1,u3 we cannot pivot. So select u4 and the maximum {-1/3,5/3,2/3}=5/3 corresponds to the 2nd column. Therefore, pivoting on y32, we obtain, see what is Table 3.Step 3.
In the first and last row, all the coefficients are ≤0.Step 5.
H=φ. Therefore, Constraints (1) and (4) are redundant.Table 1x1x2x3RHSu121130u231126u301113u412145HereH={1,2,3,4}.Table 2u2x2x3RHSu1−2/31/31/338/3x11/31/31/326/3u301113u4−1/35/32/3109/3Table 3u2u3x3RHSu1−2/3−1/3025/3x11/3−1/3013/3x201113u4−1/3−5/3−144/3


## 3.4. Stojković and Stanimirović Method

This method is proposed by Stojković and Stanimirović [13]. It is a simple method. It verifies the existence of the saddle point of payoff matrix for the game problem by applying the maxmin and minmax principles.Procedure of the Method
Step 1.
Computedij=aij/bicj,i=1,2,…,m, and j=1,2,…,n.Step 2.
Ifmax1≤i≤mmin1≤j≤ndij=min1≤i≤nmax1≤i≤mdij, then there are no redundant constraints. Stop.
Else, if there existk and l such that dkj≤dlj, for all j=1,2,…, then the kth constraint is redundant.Example 3.4.
Consider the Example3.1 presented in Section 3.1.Solution 4.
Step 1.
(3.7)dij=[212016013031041521260521261131180290145]=min⁡[0.016660.016660.03330.028850.019230.03850.00.03850.07690.00550.02220.0222]0.016660.019230.00.0055.max⁡0.028850.03850.0769Step 2.
(3.8)max⁡1≤i≤4⁡min⁡1≤j≤3⁡dij=0.01923,min⁡1≤j≤3max⁡1≤i≤4⁡dij=0.02855,max⁡1≤i≤3⁡min⁡1≤j≤4⁡dij≠min⁡1≤j≤4⁡max⁡1≤i≤4⁡dij.
There must be at least one redundant constraint in the above problem.
Hered1j≤d2j, j=1,2,3, hence the constraint (1) is redundant.


## 3.5. Heuristic Method

Paulraj et al. [14] proposed a heuristic method to identify redundant constraint by using the intercept matrix of constraints of a linear programming problem.Procedure of the Method
Step 1.
LetI be the set of subscripts associated with the initial basic variables (slack variables). Initially let that set be I={1,2,…,m}.
LetJ be the set of subscripts associated with the initial decision variables. Initially let that set be J={1,2,…,n}.Step 2.
Construct an intercept matrix “θ” using the following relationship
(3.9)θji=biaij,aij>0,forj∈J,i∈I.Step 3.
Determine the entering variables making use of the following steps.(i)
Calculatezj-cj=CBB-1aj-cj for all nonbasic variables aj=(a1j,a2j,…,amj)T.(ii)
Letβj=min{θji}, forj∈J,i∈I.(iii)
Computezj′-cj′=βj(zj-cj) forj∈J.Step 4.
(i) Letzk′-ck′=minj∈J{zj′-cj′}.
(ii) Ifzk′-ck′≥0, then the problem has no redundant constraints and stop.
(iii) Otherwise, take away the elementk from the set J, that is, J=J-{k}.
(iv) Letθkl=mini∈I{θki}=βk.
(v) Take away the element l from the setI, that is, I=I-{l}.
(vi) Findp such that min {θpl}=βp for p∈J. If so, take away such p elements from the set J, that is, J=J-{p}.Step 5.
IfJ=φ, then go to Step 6. Otherwise, go to Step 4.Step 6.
IfI=φ, then the problem has no redundant constraints and stop. Otherwise, all the constraints i∈I whose intercepts on coordinate axis j satisfy the condition θji≥max{βj} where i∈I and j=1,2,…,n are redundant. Stop.Example 3.5.
Consider the Example3.1 presented in Section 3.1Solution 5.
Step 1.
(i)I={1,2,3,4}, (ii)  J={1,2,3}.Step 2.
[see Table4].Step 3.
[see Table4].Step 4.
[see Table5].Step 5.
J=φ. Constraints (1) and (4) are redundant constraints.Table 4Basic variablesDecision variablesS1S2S3S4zj-cjβjzj′-cj′X1158.67—45−48.67−34.68X230261322.5−213−26X330261345−113−13Table 5Iteration numberkJlIJ11{2,3}2{1,3,4}{2,3}22{3}3{1,4}{3}33Φ3{1,4}φ


## 4. Numerical Results

The comparative results of the five methods are presented in the following tables. Table6 shows the comparison results of small-scale problems, Table 7 shows the comparison results of medium-scale problems, and Table 8 shows the comparison results of netlib problems [18]. Comparison results of large size problems from OR library [19] are presented in Table 9.Table 6
Comparison of five methods: small-scale problems.
S. no.12345678910No. of constraints3334434557No. of variables22233352410Brearly’s method                                        (constraint no.)0001 (4)1 (4)1 (3)1 (4)002 (3,7)No. of multiplication/divisionsWith redundant9393933113113363365055351894Without redundant939393167167186186505535883Linear programming method (constraint no.)1 (3)01 (3)2 (3,4)2 (1,4)1 (3)2 (3,4)4 (2,3, 4,5)2 (2,4)5 (2,3, 4,6,7)No. of multiplication/divisionsWith redundant9393933113113363365055351894Without redundant429342767597887050161Deterministic method  (constraint no.)1 (3)01 (3)1(3)2 (1,4)2 (2,3)2 (3,4)2 (3,5)1 (2)0No. of multiplication/divisionsWith redundant9393933113113363365055351894Without redundant429342168758888159501894Stojković-Stanimirović method (constraint no.)00001 (1)002 (2,3)1 (2)0No. of multiplication/divisionsWith redundant9393933113113363365055351894Without redundant9393933111671783361591671894Heuristic method (constraint no.)1 (3)1 (1)1 (3)2 (3,4)2(1,4)1 (3)2 (3,4)3 (3,4,5)3 (2,3,4)5 (2,3,4,6,7)No. of multiplication/divisionsWith redundant9393933113113363365055351894Without redundant424242767597887050161Table 7
Comparison of five methods: medium-scale problems.
S. no.Size of the problemNumber of redundant constraints identified byno. of constraintsno. of variablesBrearly’s methodlinear programming methoddeterministic methodStojković- Stanimirović methodheuristic method11661413511422051718101732561723302343032429180295375293512035640238393803974533443100438505284911049Table 8
Comparison of five methods: netlib problems.
S. no. and File nameSize of the problemNumber of redundant constraints identified  byNo. of constraintsNo. of variablesBrearly’s methodLinear programming methodDeterministic methodStojković- Stanimirović methodHeuristic method(1) afiro202093004(2) fit1d24242100013(3) fit2d25250190719(4) sc50b2828070010(5) sc50a29291110211(6) kb2393931301414(7) vtpbase51511210430(8) bore3d5252421702218Table 9
Comparison of five methods: Large Size Problems.
S. no. and File nameSize of the problemsNumber of redundant constraints identified byNo. of constraintsNo. of variablesBrearly methodLinear programming methodDeterministic methodStojković Stanimirović methodHeuristic method(1) scpcyc062401921972352010236(2) scpe250500314038043(3) scp432001000142195136143196(4) scp52200200018719716398198(5) scpa3300300016518112393293(6) scpd3400400024330531564395(7) scpcyc081792102480015121328541780(8) scpc1r13409571510233608320404083In Figures2, 3, 4 and 5, the comparative results of small scale problems, medium scale problems, netlibFigure 2Figure 3Figure 4Figure 5problems and large size problems are shown graphically. Figure2 shows that the heuristic and linear programming methods identify more redundant constraints than the other three methods. Figure 3 indicates that the Stojkovic and stanimirovic method identifies no redundant constraints where as deterministic method identifies very low redundant constraints compared with other methods. Figure 4 indicates that the deterministic method identifies nothing; brearly’s, Stojkovic and stanimirovic methods identify very low redundant constraints and the remaining methods more or less coincide. Figure 5 shows that the Stojkovic and stanimirovic method identifies very less redundant constraints where as heuristic method identify more redundant constraints than the others.The tables deal with the identification of the number of redundant constraints in linear programming problems by using the five methods. It is very easy to identify quickly the best method in finding redundant constraints of LP problems.  Heuristic method seems to be less time consuming, and it requires less computational effort. It also finds more redundant constraints when compared with the other four methods. So this method would be easy and reliable method for identifying redundant constraints. Even though the LP method identifies more redundant constraints, it needs more computational work and takes more time. Brearly’s method identifies less redundant constraints with less computational effort than heuristic and LP methods. Deterministic methods identify more redundant constraints with more computational effort. So time consumption is bigger when compared with heuristic method. Stojković and Stanimirović identified a smaller number of redundant constraints than the others.The efficiency of the algorithms was also tested by solving the first set of Linear Programming Problems mentioned before and after removing the redundant constraints, identified by each method.   Table6 gives the computational results.


## 5. Conclusions

In this paper, the heuristic approach [14] for identifying redundant constraints has been compared with other four methods. Each method has its own role in viewing computational effort and time factor. Linear programming method [6] and deterministic method [15] more or less coincide with heuristic method in most of the problems. Brearly et al.  [4] method depends on the upper and lower bounds of the decision variables for identifying the redundant constraints. Hence, the heuristic method is more useful than the other methods.



---

*Source: 723402-2010-12-23.xml*