Forum Discussion
Benders decomposition failure (Java API)
I'm trying to implement Benders decomposition on a simple example (MIP master problem, LP subproblem) using a combination of a `PreIntsolCallback` (which ignores node optima but rejects heuristic solutions if they would otherwise trigger a Benders cut) and an `OptNodeCallback` (which generates the usual Benders cuts).
The solver initial finds a feasible but extremely suboptimal solution to the master problem. It then generates a series of heuristic solutions, all of which are rejected. Eventually it triggers the `OptNodeCallback` twice, the first resulting in an optimality cut and the second resulting in a feasibility cut. After that, the solver declares the initial, horribly suboptimal solution is the optimum.
I have verified that the true optimal solution satisfies both of the Benders cuts that were added, and that in both cases the `addCut()` method returned a zero value. I'm looking for suggestions as to what might be going wrong. Thanks in advance for any guidance.
Update: I have identified at least part of the issue. The `OptNodeCallback` has an argument `XpressProblem xp `, and it uses `xp.getCallbackSolution(use)` to get the values of a vector `use` of binary variables in the master problem. It turns out that some of the values returned are fractional. Does that mean that `OptNodeCallback` is called when a node LP is solved regardless of whether the node solution meets the integrality criteria?
3 Replies
Yes, the optnode callback is invoked (quote from C documentation) "after the LP relaxation has been solved for the current node, and after any internal cuts and heuristics have been applied, but before the Optimizer checks if the current node should be branched."
So if you were assuming that the callback is only invoked for integral solutions then this may be part of the problem.
Note that you can call addCut() from the preintsol callback as long as the soltype is 0. So you can inject Benders cuts directly from there unless the solution presented to the callback came from a heuristic.
Thanks Daniel. I was assuming that the optnode callback was only invoked for integral solutions. Also, I had tried calling addCut() from the preintsol callback earlier, without success, due to another error. I mistakenly thought that, since I was rejecting the proposed incumbent, I should set pReject.value = 1 in the preintsol callback. Setting it to 0 after adding the cut works.
Yes, when adding a cut in the preintsol callback, you must not set pReject.value = 1 as this drops the cut. This is implied by this sentence in the documentation:
"p_reject Set this to 1 if the solution should be rejected. When soltype is zero, this will also drop the node problem."
and
"When soltype is zero and the solution is rejected, the node itself will be dropped without further branching, regardless of whether the node problem is modified within the callback."
Admittedly, this is not as clear as it should be. We will clarify this.
