Implementation of Local Branching

Question

I've been recently reading some papers where the authors use local branching specifically in Benders Decomposition (see for reference). Although I understand up to some extend how the algorithm works, I am having hard time to understand how it is implemented in practice.

For instance, it is stated that we can divide the feasible region into two parts by using $\Delta(x_o,x) \leq \kappa$ and $\Delta(x_o,x) \geq \kappa+1$ which are identified as the left and right branches, respectively.

I was wondering if someone can briefly explain how this operation can be performed from the coding perspective when using in Java API using CPLEX.

Some academic references are:

Rei, W., Cordeau, J. F., Gendreau, M., & Soriano, P. (2009). Accelerating Benders decomposition by local branching. INFORMS Journal on Computing, 21(2), 333-345.

Baena, D., Castro, J., & Frangioni, A. (2020). Stabilized benders methods for large-scale combinatorial optimization, with application to data privacy. Management Science.

Answer 1

You need to use a callback, and CPLEX introduced a new callback system ("generic callbacks") in version 12.8 (I think) while maintaining support, at least for now, for the original callback system ("legacy callbacks"). The details of doing the branching depend in part on which system you use.

With legacy callbacks, you create a class that extends IloCplex.BranchCallback and attach it to your model using IloCplex.use(). Inside the main() method, you use one of the overloads of makeBranch() to make each branch. To create two child nodes, you call makeBranch() twice.

With generic callbacks, you create a class that implements the IloCplex.Callback.Function interface and attach it to your model using a different overload of IloCplex.use(). In this overload of use(), you have to specify a mask for the contexts in which the callback is invoked, and in particular you will need to include the "branching" context in the mask. The class implementing IloCplex.Callback.Function will have a method invoke(), which CPLEX will call, passing in an argument of type IloCplex.Callback.Context. Within your implementation of invoke(), after checking if necessary to be sure you are in the branching context, you invoke the context object's makeBranch() method once for each child node.

In both approaches, attempting to create more than two children at a node will cause the space-time continuum to collapse in on itself.