Originally posted by: Michael_D

In a C++ application using concert technology with cplex 12.2, a LazyConstraintCallback is used to solve an MIP.

For a small test instance, the following output is generated:

This is @(#)IBM ILOG Software: product Concert, library concert.lib, version 12.2, date 07/20/2010, (C) Copyright IBM Co
rp. 1990, 2010 All Rights Reserved. US Government Users Restricted Rights - Use, duplication or disclosure restricted by
GSA ADP Schedule Contract with IBM Corp. This product includes software developed by the University of California, Berk
eley and its contributors.

Tried aggregator 1 time.
MIP Presolve eliminated 2 rows and 3 columns.
MIP Presolve modified 10 coefficients.
Reduced MIP has 18 rows, 418 columns, and 106 nonzeros.
Reduced MIP has 53 binaries, 0 generals, 0 SOSs, and 0 indicators.
Probing time = 0.00 sec.
Tried aggregator 1 time.
Presolve time = 0.05 sec.
Probing time = 0.00 sec.
Clique table members: 18.
MIP emphasis: balance optimality and feasibility.
MIP search method: traditional branch-and-cut.
Parallel mode: none, using 1 thread.
Root relaxation solution time = 0.00 sec.
Lazy constraint callback called.
Separated lazy constraints for k = 2.

Nodes Cuts/
Node Left Objective IInf Best Integer Best Node ItCnt Gap Variable B NodeID Parent Depth

0 0 -64.8000 16 -70.0000 12
Lazy constraint callback called.
No lazy constraints separated.
0 0 -63.5000 8 Fract: 1 18
Lazy constraint callback called.
No lazy constraints separated.
Lazy constraint callback called.
No lazy constraints separated.

• 0 0 integral 0 -63.0000 Cuts: 2 22 0.00%

0 0 cutoff -63.0000 -63.0000 22 0.00% 0 0
Elapsed real time = 0.23 sec. (tree size = 0.00 MB, solutions = 1)

Cover cuts applied: 1
Gomory fractional cuts applied: 2

Questions:
Why is the callback called twice in a row? After the first of the two consecutive calls, no lazy constraints are separated. So, what is to be expected from a second call?

After the line with 'Cuts: 2', the lazy constraint callback is not called again, but the resulting solution is declared optimal. How can this be? How can cplex know whether a solution is optimal without calling the lazy constraint callback?
In an earlier thread, Tobias Achterberg wrote the following on when a lazy constraint callback is called (most probably referring to version 12.3):

'There are two cases to distinguish:
(a) the incumbent was found as integral solution to a node LP relaxation,
(b) the incumbent was found by a primal heuristic.

In case (a) we call first the lazy constraint callback and then the incumbent callback.

In case (b) it is only guaranteed that we call the incumbent callback, with "wherefrom" equal to CPX_CALLBACK_MIP_INCUMBENT_USERSOLN or CPX_CALLBACK_MIP_INCUMBENT_HEURSOLN. We may also call the lazy constraint callback (before calling the incumbent callback), but this happens only for heuristics that look close to the LP optimum and for which adding lazy constraints tightens the formulation at the area of interest.'
Does this mean that in cplex 12.3, instead of the former cut callback, there are three callbacks to be implemented: lazy constraint callback, cut callback (as Tobias wrote earlier, it is also sometimes sensible to check the lazy constraints during the cut loop), and incumbent callback (to handle case (b))?

Why shouldn't the lazy constraint callback be called under all circumstances before a potential solution is declared an 'incumbent'? If the lazy constraint callback is not called, it is impossible to say whether a potential incumbent is feasible, that is, fulfils all constraints, including the lazy ones.

What could be meant by 'heuristics that look close to the LP optimum and for which adding lazy constraints tightens the formulation at the area of interest'? How can cplex know whether or not 'adding lazy constraints tightens the formulation at the area of interest' when the lazy constraints are not separated?

Could it be that also in version 12.2, the cut callback may or may not be called when a potential incumbent is found by a heuristic, although the documentation (version 12.2) says: 'An instance of the class IloCplex::CutCallbackI represents a user-written callback in an application that uses an instance of IloCplex to solve a mixed integer programming problem (a MIP). This class offers a method to add a local or global cut to the current node LP subproblem from a user-written callback. CPLEX also calls the callback when comparing an integer feasible solution, including one provided by a MIP start before any nodes exist, against lazy constraints.' (IDE and OPL > OPL Interfaces > C++ interface reference manual > optim.cplex.cpp.advanced > Classes > Class IloCplex::CutCallbackI)?

Thanks in advance for shedding some light on this issue.

Michael
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Hi Michael,

(1) Hard to tell why the lazy constraint callback is called twice. I would guess the first call is to separate cuts for the LP relaxation solution, and the second call is after CPLEX found the LP solution to be feasible in order to give the lazy constraints a chance to cut off the integral solution.
The underlying reason for this behavior is that up to version 12.2.0.2 we treated the lazy constraint and the cut callback identically. This has changed with 12.3.

(2) The lazy constraint callback was already called before the log line is printed (see 1). So, you definitely had a chance to reject the solution.

(3) Sorry about the confusion. I checked the source code again. This is a little complicated, and I found out that those heuristics (which are just a few) that would not call the lazy constraint callback are not invoked in the presence of a lazy constraint callback. Thus, having a lazy constraint callback or an incumbent callback should suffice to reject all solutions that violate any of your constraints. Of course, you can have both, but you do not need to.
If you also want to separate fractional LP solutions (this may yield better performance but is not needed for correctness), then you should also install a cut callback. But note that this is not a big implementation overhead: just implement your lazy constraint check method as a separate method and call this from the two callbacks.

Could you please point me to the thread where I gave a wrong answer, such that I can correct myself there?

Thanks,

Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Michael_D

Hi Tobias,

thank you very much for answering so promptly, and, of course, for the content of the answer. This is really good news.

Michael

P.S.: I just saw that you already found the other thread yourself and posted a reply there, too. Thanks again.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MasoudC

Hello,

The main discussion backs to a long time ago. However, I have a similar question which was asked by Michael_D.

In C++, with callable libraries of CPLEX 12.6, I am using USERCUTCALLBACK for my branch-and-cut algorithm to solve a multi-period VRP. I observe that the USERCUTCALLBACK is called a second time even when there is no fractional violated (in my case: subtour elimination) constraint. Computationally speaking, this means I have to spend, at each fractional node, one more LP solution time. This is while I am using a deterministic separation heuristic which will return for the second time no violated constraint. How can I prevent this second round of call?

 

I guess the CPLEX stopping condition at each fractional node is to check for the LP gap improvement to be less than a small amount (say, optimality gap). Therefore, CPLEX needs to check for the second time to recognize that no more cuts is added. If the number of newly added cuts can be added to the stopping condition, then when there is no more cuts to be added, CPLEX can stop calling USERCUTCALLBACK. Am I right?

 

Best regards,

Masoud

#CPLEXOptimizers
#DecisionOptimization

Sorry, I am not exactly clear what your problem is. If you add cuts then CPLEX will re-solve and give you a chance for more cuts in a second call. Note however that you can explicitly ask CPLEX to stop separation of any cuts by calling abortCutLoop().

Using setNodeData and getNodeData you could also mark the current node in the first invocation of the callback and in the second invocation of the callback recognize that you were already called on this node and thus just do nothing.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: MasoudC

Hello Daniel,

 

Thank you very much for your prompt reply. It is exactly what I needed.

At the same node of the search tree, I need to prevent the CPLEX to call my separation algorithm one more iteration, when no violated valid inequality is found in the current iteration. The reason is that I am using a deterministic procedure which will not be able to find a new violated valid inequality when it was not able to find any in the previous iteration.

 

Best regards,

Masoud

#CPLEXOptimizers
#DecisionOptimization