Add lazy constraints not linked to current solution candidate in CPLEX callback

Question

I need to add some lazy constraints within a CPLEX generic callback (version 22.1.1). Those lazy constraints do not exclude the current solution candidate, but they nevertheless exclude other integer points, so they cannot be loaded as user cuts.

From the documentation for the Java API I see that IloCplex.Callback.Context.rejectCandidate(IloRange[] arg) allows to load lazy constraints, but reading the documentation is not obvious to me whether such lazy constraints MUST be violated by the current candidate solution or they can be any inequalities that preserve the optimal solution.

Also, I need to add such lazy constraints when either the lower or upper bound of the objective value change. As I am solving a minimization problem, my upper bounds are given by the value of the incumbent integer solution and my lower bounds are given by the value of the linear relaxations. Although the former are available within the same scope/state as the one that allows the insertion of lazy constraints (IloCplex.Callback.Context.Id.Candidate), the latter are available within (IloCplex.Callback.Context.Id.Relaxation) where I cannot call the method rejectCandidate(...). Do I have to store those constraints and wait for the next IloCplex.Callback.Context.Id.Candidate state to apply the related lazy constraints? (this would be unfortunate, as those states are quire rare).

So my questions are:

1. How do I load lazy constraints that do not reject the current candidate solution?

2. What is the 'recommended' way to load lazy constraints when I am able to find them during a state which is not IloCplex.Callback.Context.Id.Candidate?

Originally asked on this StackOverflow post.

Answer 1

The first part is a bit tricky. CPLEX does not guarantee to use lazy constraints to cut off future candidates even though it can, so the benefit of adding those constraints before being needed is not obvious, even if the callback accepts them. I'll circle back to this in a moment.

For the second part, what I have done in the past is put user cuts/lazy constraints that I cannot yet add (due to callback context or some other restriction) in a queue within program memory. The next time the callback is invoked in the correct context, I either empty the queue and add them all (taking my chances that any or all stick) or else scan the queue for violated constraints and add just those (which eats up some processing time).

Now back to the first part. If you do not want to add a lazy constraint that is not violated by the current candidate and risk having it ignored, you can queue it and check later candidates to see if any violate it (in which case you can use it to cut them off). There is a tradeoff in computation time you need to assess: the time spent checking queued constraints for violations v. the time spent rediscovering a constraint that you found earlier but could not use, and which now actually does cut off the current candidate.