Originally posted by: youngdae

Hi,

I have a question on removing redundant equality constraints of an LP problem. I'm using CPLEX callable library. What I'm doing is as follows:

1. Set all objective coefficients to zero.

2. Solve the LP problem using CPXlpopt().

3. Get basis status of columns and rows using CPXgetbase().

4. If an artificial variable is a basic variable (i.e., rstat [i] == CPX_BASIC && sense [i] == 'E'), call CPXpivot to pivot out the artificial variable from the basis. I called CPXpivot(env, lp, CPX_NO_VARIABLE, -i-1, CPX_AT_LOWER) to pivot it out.

5. If CPXpivot failed, then I assumed that the corresponding equality constraint is redundant and removed it. I think CPXpivot failed for a basic artificial variable only if the corresponding row has only zero values for nonbasic variables.

Would this procedure allow me to identify redundant equality constraints? I did an experiment, but it seems that the procedure does not correctly identify redundant equality constraints as the LP problem with redundant rows removed gave me an unbounded solution for a given objective coefficient which should not happen as the original LP has a finite optimal solution.

Any advice would be greatly appreciated.

Originally posted by: RWunderling

When you call CPXpivot() CPLEX will conduct a single dual ratio test, where it chooses the direction of the ratio test depending on the violation of the current constraint i (CPX_AT_LOWER is in fact ignored since sense[i] == 'E').  "Failure" to do the pivot just means no blocking dual variable is found, but does not allow you to conclude redundancy.  In other words, "failure" means that if you changed rhs[i] in the chosen direction, the model would become infeasible.  This does not mean that you could not change rhs[i] in the opposite direction.  In fact, the polyhedron could be unbounded in this direction, which is consistent with your observation.

Roland