Originally posted by: Ccl_

Hello,

I am using concert for C++ (version 12.6.0) and I am trying to implement a branch and cut algorithm using a UserCutCallBack.

When executing my code, it first works rather well, violated cuts are found and the LP bound is tightened.

But at some point in the execution, another usercut is added to the model and when solving the new problem Cplex finds the same solution as before adding the cut.

After that point, the same cut is generated at each iteration. It seems that Cplex does not take this cut in account when solving the LP relaxation, because we get the same solution over and over and it does an infinite loop.

I checked that my separation algorithm was working properly ie was actually returning a constraint violated by the current LP relaxation.

I tried to adjust the EpRHS parameter (I set it to1e-9) but it didn't change anything. In fact, the cut that is added at each iteration is "largely" violated (with a value like 0.1).

I thought maybe the problem came from Cplex cut filtering process and I tried to add each cut with the parameter "UseCutForce", but it didn't help neither.

Does anyone have any idea of what is happening here ?

Thanks in advance!

This sounds very odd and should certainly not happen. Do you have a minimal code that reproduces the problem and that you could share? If you don't want to share it in public, you can send it directly to daniel(dot)junglas(at)de(dot)ibm(dot)com.
 

Originally posted by: PierreBonami

Hi,

Did you check the scaled violation of the cut you are adding?

You should divide the violation by the largest coefficient in the cut to know the violation (if this number is too small it may be below feasibility tolerances).

Originally posted by: Ccl_

Hi,

Thank you for your answers! The coefficients in the cuts are only ones and zeros so the scaled violation stays the same (0.1).

I attached the smallest code I could write that reproduces the problem. Sorry if it is a bit long, I didn't manage to reproduce the problem without using my separation algorithm, so I included it, with as few features as possible.

Thanks again!

The problem is that the expressions in your cuts contain constant terms. In other words, for some of your cuts cons->getExpr().getConstant() is non-zero. This constant is ignored when the cut is added to CPLEX (which looks like a bug).

Can you please either make sure your expressions do not contain constants or replace the code that adds the cut like this:

#if 1
                       IloNum lb = cons->getLB();
                       IloNum ub = cons->getUB();
                       IloExpr expr = cons->getExpr();
                       IloNum constant = expr.getConstant();
                       if ( fabs(constant) > 0.0 ) {
                          // The cut has a non-zero constant in its linear expression.
                          // Move that constant into the bounds instead.
                          if ( fabs(lb) < IloInfinity )
                             lb -= constant;
                          if ( fabs(ub) < IloInfinity )
                             ub -= constant;
                          expr.setConstant(0);
                       }
                       add(IloRange(getEnv(), lb, expr, ub), IloCplex::UseCutForce).end();
                       expr.end();
#else
                       add(*cons, IloCplex::UseCutForce);
#endif

Originally posted by: Ccl_

It works now, thank you very much!