Forum Discussion
Lazy cut callback in Java
In Java, how can one separate cuts in a lazy manner, i.e. only separate cuts at the integer nodes? Such an approach is common in for instance a standard TSP formulation where the subtour elimination constraint are omitted initially (it would be intractable to generate these constraints beforehand).
From the Optimizer Reference Manual, I would suspect that I need to use the XPRSaddcbpreintsol callback (I guess the XPRSpreIntsolListener in Java). It is however not clear to me whether I can add cuts through this callback, or whether I can only accept/reject solutions. An example would be really helpful here. For instance, in case of the TSP, the integer solution might include a subtour which can be straightforwardly identified by a separation algorithm. At this point, one would set ifreject=1 to reject the solution, and at the same time add a cut?
A similar problem arises when implementing a classical Benders decomposition, where the master problem is a MIP and the subproblem an LP. When an integer node is encountered, one might have to generate a feasibility or an optimality cut. Let's assume that we want to generate an optimality cut. Should we then still set ifreject=1 to reject the solution even though, strictly speaking, the solution ain't infeasible? How should the optimality cut at an integer node be handled?
8 Replies
Cuts are expected to be added in the 'OPTNODE' callback (so XPRSoptNodeListener from Java). Regarding the use of this callback for the implementation of TSP subtour elimination constraints you may want to take a look at the example f5touroptcbrandom.mos that shows an implementation with Mosel (the use of the Optimizer callbacks follows the same logic as what one would employ in a Java program): within the implementation of the OPTNODE callback function the solver parameter MIPINFEAS is queried to decide whether to trigger cut generation.
Attached you can find a short example for a TSP problem that separates subtour elimination constraints lazily. There are two things you have to do
- Hook into the preintsol callback to reject integer feasible solutions that do not satisfy all the lazy cuts.
- Hook into the optnode callback to generate violated lazy cuts.
Note that you can check
if (prob.attributes().getMIPInfeas() != 0) return;in the optnode callback to restrict separation to nodes that are integer feasible
@Daniel Junglas It seems there's a bug in your TSP implementation. For small node values (e.g. 6 in your implementation), XPRSoptNodeEvent never gets invoked. When setting nodes=27 (new TSP(27).solve();), the model gets into an endless loop. I'm not quite sure what's causing this.
If the problem is too easy then the solver can find the optimal solution without branching. In that case the optnode callback will indeed not be invoked. You can try to disable heuristics (set HEURSTRATEGY to 0) to artificially make the problem harder.
I could not reproduce the infinite loop for 27 nodes. What was your setup for this? Could you provide the beginning of your log? In particular the part where non-default parameter settings and thread counts are reported?
@Daniel Junglas Please find the log attached. I ran your TSP.java with 2 minor modifications: (1) I changed "new TSP(6).solve();" to "new TSP(27).solve();", and (2) I load the license file. Please find the log attached. It seems that XPRSoptNodeEvent gets executed endlessly at the end. When I add a print statement to print double[] sol inside XPRSoptNodeEvent(.) it indeed prints the same fractional solution over and over again:
sol: [-0.0, 1.1102230246251565E-16, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, 0.6666666666666667, -0.0, -0.0, -0.0, -0.0, 0.3333333333333335, 0.9999999999999999, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.3333333333333333, 0.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.6666666666666665, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, 0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.33333333333333326, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.6666666666666667, -0.0, -0.0, 1.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, 0.6666666666666667, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, 0.0, -0.0, -0.0, 0.6666666666666667, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.3333333333333335, -0.0, 0.6666666666666665, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 0.33333333333333326, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, 0.33333333333333326, -0.0, -0.0, -0.0, -0.0, 0.0, -0.0, -0.0, -0.0, -0.0, 0.6666666666666667, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, -0.0, 1.0, -0.0, -0.0, 0.33333333333333326, -0.0, -0.0, -0.0, -0.0]Thanks again for all the effort you put into answering all these questions! It's very much appreciated.
hi Daniel, I was wondering whether you were able to see what went wrong in the log file I attached. Thank you!
Hi Joris, sorry for the long delay. I first had a hard time reproducing your issue and then got side-tracked by some other things.
Here is what I found by now:
We get into an infinite loop because the example separates the same cut over and over again. This happens for two reasons
- The example separates cuts even for nodes that are not integer feasible.
- The example does not check whether the cut is sufficiently violated before adding it
I suggest to separate cuts only for integer feasible nodes (prob.attributes().getMIPInfeas() == 0) that should fix both issues (because any violated cut found that way will be significantly violated). It also reduces the overhead for non-integral nodes.
An alternative is of course to check that the presolved cut is sufficiently violated. For this you will need the solution to the presolved problem. That can be obtained by function prob.getPresolveSol().
Here is a slightly modified version of the example that now avoids the endless loop.
