Originally posted by: nikextens

Hello everyone,

I am trying to identify redundant constraints in my LP. According to CPLEX manual (c++ concert) 'basicPresolve' is capable of doing that. Unfortunately the results which I get seem wrong. For debugging I created a little LP (see below); the function returns only zeros which means that none of the constraints is redundant. Does anyone have experience with using 'basicPresolve'? I attached my c++ code below. Any help is appreciated!

min 2x + 5y

x>=0

y>=0

x+y >=5

x+y>=3

x+y>=10000

IloEnv my_env = IloEnv();
                
IloModel my_model(my_env);
IloCplex my_cplex(my_env);
IloNumVarArray my_optvar = IloNumVarArray(my_env, 2, 0, IloInfinity);

IloRangeArray range_array;
range_array = IloRangeArray(my_env);
IloBoolArray redundant;
redundant = IloBoolArray(my_env);                
                
IloNumVarArray vars;
vars = IloNumVarArray(my_env);        
IloNumArray redlb;
IloNumArray redub;
redlb = IloNumArray(my_env);
redub = IloNumArray(my_env);    
                
my_model.add(IloMinimize(my_env, 2*my_optvar[0] + 5*my_optvar[1]));             
                
my_model.add(my_optvar[0] >= 0);
my_model.add(my_optvar[1] >= 0);
                
IloRange range1(my_env,0, my_optvar[0]  + my_optvar[1] - 5,IloInfinity);
my_model.add(range1);
range_array.add(range1);    
                
IloRange range2(my_env,0, my_optvar[0]  + my_optvar[1] - 3,IloInfinity);
my_model.add(range2);
range_array.add(range2);
                
IloRange range3(my_env,0, my_optvar[0]  + my_optvar[1] - 10000,IloInfinity);
my_model.add(range3);
range_array.add(range3);    

vars.add(my_optvar[0]);
vars.add(my_optvar[1]);            
                                
my_cplex.basicPresolve(vars,redlb,redub,range_array,redundant);
                
for (unsigned iter = 0; iter < redundant.getSize(); iter++)
{    cout << "iter "<< iter<< ": "<< redundant[iter]<< endl;            
}

Your example code is missing my_cplex.extract(my_model) before calling my_cplex.basicPresolve(). But even with that, basicPresolve() returns an all-0 'redundant' array.

The reason is that basicPresolve() does not detect this sort of redundancy. To find redundant rows, basicPresolve() looks at one row at a time and checks whether this row is always satisfied given the bounds of the variables in that row. If so the row is marked as redundant. basicPresolve() does not check whether there are rows with parallel left-hand side etc. For this you need to invoke full presolve.

Originally posted by: nikextens

Thanks for the answer. I was hoping that there was a different reason. So I am ending up at the regular presolver which doesn't tell me which constraints are redundant.

If you need this information for a one-time analysis only you may use the callable library to figure out some of this information. In particular, function CPXgetprestat() gives you information about the rows that survived presolve. So you could

1. IloCplex::exportModel() you problem to a SAV file
2. Load that SAV file into a callable library CPXENVptr/CPXLPptr (CPXopenCPLEX, CPXcreateprob(), CPXreadcopyprob())
3. Call CPXpresolve() or CPXmipopt() with CPX_PARAM_NODELIM=0
4. Use CPXgetprestat() to assess the results of presolve

Of course you would need a way to translate back the row indices used in the callable library to your model in Concert. This can be done easily if you assign unique names to the constraints.
 

Originally posted by: nikextens

Unfortunately, it is no one-time analysis. It is an iterative method in which I add numerous constraints each iteration. My intention was to use the information of redundancy every 100 iterations and 'remove' redundant constraints to reduce the problem and increase the method's speed by helping the presolver (which doesn't have to identify each redundant constraint in every iteration over and over again). But still, your suggestion might work. Thanks!