Originally posted by: Panos_N89

Hello!

My model has been formulated in MATLAB, where CPLEX is called via a MEX-file. In particular, after the problem object is populated, CPXXpresolve and CPXXgetprestat are called successively in order to obtain Presolve Status Information. 

My LP problem consists of a number of "L" inequality constraints and a single equality constraint, which I have converted into two "L" ineq constraints. The equality constraint actually demands the sum of the variables to be equal to a constant.

Since I am only interested in constraint reduction, what values should I set to the objective coefficients?
(Note that I have tested zeros, ones and rand. The last two give the same results regarding presolve status! ).

Once I get my presolved problem, I use cplexlp (MATLAB) to ensure that solutions of the initial and presolved problem are the same. Everything works fine. However, I have figured out that even if I manually remove some more constraints from the reduced problem, the "re-reduced" problem is still able to return the same solution as the initial one. Doesn't that mean that the extra constraints I removed are redundant? Why presolve didn't detect them?

For example, take a look at the attached LP. Presolved problem consists of 68 constraints. However, it is theoretically expected that constraints 1-6 should not be critical. Indeed, if I manually remove these constraints, reduced LP keeps returning the same correct solution..

Could you possibly know the reason? Is there any way to detect redundant constraints more thoroughly?

Details:
- I have set objective coefficients equal to ones. I think that is not significant, since the equality constraint maintains sum of variables to a constant value.
   Zero coefficients lead to extended constraint reduction, eg for the attached example, presolved LP would only have 2 critical constraints.
   Sounds perfect, but doesn't quite conform to desired results..
- Lately, I figured out that my constraints could be reformulated so that every pair of them forms a range constraint. Could this by any chance affect the
  number of reductions?
- I have even tried to test a much smaller LP (550 constraints). Presolve returned 22 critical constraints, while noredund.m (an m file that removes
redundant constraints by recording which of them generate points on the convex hull) returned just 4. 

Thank you,
Panos


 

Originally posted by: T_O

First of all, it can of course happen that a constraint is not active at the optimal solution. That does not mean that it is redundant. It might become binding if you use another objective function.

Second: Detecting redundancy is not a trivial problem. So, i guess, CPLEX only removes constraints that are (more or less) trivially redundant. To remove all redundant constraints, one would have to solve an LP for each constraint (if I remember correctly).

Best regards,
Thomas

As Thomas already pointed out, there is no guarantee that the presolved problem will contain only a minimal, non-redundant set of constraints. In general, if you know that certain constraints are redundant then it is a much better idea to not add redundant constraints at all instead of leaving it to CPLEX to figure out redundancy.

As for the objective coefficients: Depending on the constraints it can make a big difference to presolve whether a variable has a zero or non-zero coefficient in the objective. Consider for example a constraint like (this is an over-simplification):

x <= y,  x,y >= 0, y <= b

and assume y does not appear in any other constraint. If the objective function coefficient of y is 0 then one can immediately fix y=b and eliminate y. If the objective function coefficient of y is non-zero then this fixing is not necessarily correct.

If you really want to find a minimal set of non-redundant constraints you could look into software like polymake that allows investigation of the underlying polytope.

Originally posted by: Panos_N89

Thank you both for your useful answers!

So, in conclusion, it turns out that CPLEX presolve doesn't necessarily determine the constraints that form the feasible region, have I understood right? 

Polymake seems a really nice suggestion and I am definitely going to use it to double-check results. However, for the time being I have to insist on CPLEX, since I know that a research organization has successfully used it to define critical constraints. 

It is not that I actually know certain redundant constraints. What I really do is call CPLEX presolve for several LP problems and compare the results. Let's say, I have two LP's. What Presolve returns, looks like:
LP1, critical constraints: 11, 12, 13, 14
LP2, critical constraints: 13, 14, 15, 16
Well, these LP problems are just different expressions of the same system. Thus, they have to return identical results. As already described above, removing constraints 11, 12 and 15, 16 from LP1 and LP2 respectively has no effect on the solution of the problem.

Regarding what Thomas suggested in the second part of the answer, I am thinking of solving the presolved LP, each time removing one of the remaining constraints. If the solution is unchanged, then the removed constraint is redundant. Does this one sound right to you?
 

Originally posted by: T_O

I think you misunderstood me slightly. My approach is to remove constraints that are redundant for the constraint system. There might of course be constraints that are not redundant but still not active at the optimal solution.

Best regards,
Thomas

Originally posted by: Panos_N89

Hmm, I see. I just thought Presolve would take objective coefficients into consideration and would remove constraints that, although not redundant for the constraint system, are not expected to be active.
Thanks!