Originally posted by: Gert-Jaap

I have been using CPLEX for a few years now. Currently, I am working on a project where I solve a difficult MIP while using a Lazy Constraint Callback. Now I have noted the following issue: I start solving my model (a minimization objective in my case), and at some point a feasible solution is found, no lazy constraints can be added, so this is set as the incumbent. Let's assume this has objective value 100. Then in some parallel threads, other parts of the branch and bound tree are explored. What happens is that this other thread can explore a node of which the objective is higher than that of the incumbent, e.g., the value is 150. Then it keeps adding lazy constraints if applicable, even though the objective value can never get better than that of the incumbent solution (100). It only stops when it finds out that no lazy constraints have to be added any more, or that the node has no longer an integer feasible solution and more branching is needed. However, my impression is that this callback is doing a lot of useless work, it can better spend it's time on other things as another thread already found a better solution, so the current node of this thread with value 150 can already be pruned.

My impression is that the threads need to be synchronised more often in order to avoid this behaviour, as the other thread does not yet see that there is an incumbent solution with value 100 available. My question is: is this a known issue in parallel CPLEX? Or maybe a more deep question: is this actually an issue? And third: Is there any way in which I can impose a more frequent synchronisation between the threads of the most recent information regarding the incumbent solution? In the documentation about Callbacks, I read "If the default implementation of the method clone is not adequate, and if the callback is to be used for parallel optimization, this method also needs to be implemented by the user. Recall that the default clone method performs a shallow copy, so typically a user implementation needs to perform a deep copy for objects that should be local to threads or the user implementation must use the synchronize keyword where synchronization is required." I could not find any documentation about how to implement this. Does any of you have any thoughts about this?

What you observe is expected and it is indeed related to thread synchronization. More precisely, about deterministic thread synchronization. As you suspected, the thread separating those lazy constraints is not (yet) aware of the better solution that was found in the other thread.

Synchronization is a difficult topic. It is not easy to find the "right" synchronization frequency since synchronization introduces overhead. There is no way to modify this frequency by any sort of parameter. We tune this carefully but of course we cannot exclude some bad corner cases. I have filed an internal user wish to allow more control over the synchronization frequency but I cannot make any promises this is going to be implemented (soon).

If you are not concerned about determinism of results then you can do the following: Have a global (lock-protected) variable that stores the currently best known incumbent. Update this whenever you see a new incumbent. During lazy constraint separation, once you see that your solution exceeds that cutoff then stop generation of constraints. Instead just reject the solution in an incumbent callback later.

The comment about the clone() function for the callback class relates to this: For each thread CPLEX creates a clone of your callback object. This is done by invoking the callback's clone() method. The Java default implementation of clone() returns a shallow copy of the class. For example, if the class has a field that is of type 'int[]' then all clones will point to the same array. If that is ok for your case then you don't have to do anything. However, if each clone requires its own array (for example because this is a working array that different threads may use simultaneously) then you have to override the clone() method and create a deep copy of the array yourself.