3
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks for the detailed information! Suppose I go with the generic callback, and have a candidate incumbent solution x. When I call makeBranch method, it seems like the method can take two parameters as IloRange[], double. My first question is that, the paper shows that we only add a cut, however, the method does not take a single parameter. Does that mean I can simply insert an estimated objective? $\endgroup$ – whitepanda Sep 28 at 20:44
  • $\begingroup$ The second question is that how one can define the direction of the branch as left and right? There is a method called branchDirection, but it is defined as up and down. Lastly, how do we let CPLEX optimize the left branch while keep branching from the right side? $\endgroup$ – whitepanda Sep 28 at 20:44
  • $\begingroup$ My understanding is that we use cplex.use() only once in generic callback. In this scenario, as you mentioned, I am supposed to combine all information in a single mask. For example, I can attach an incumbent solution to the mask via IloCplex.Callback.Context.Id.Candidate. Now, based on your post, I should incorporate branching context here. However, IloCplex.Callback.Context does not give me makeBranch option. I did understand how makeBranch works in a legacy callback. Is there a document showing how to handle branching decisions in a generic callback? $\endgroup$ – whitepanda Sep 28 at 21:22
  • $\begingroup$ First question: Yes, you just need to put in an estimate of the objective value at the child, which can be the objective value at the parent if you do not know anything more precise. $\endgroup$ – prubin Sep 29 at 15:17
  • $\begingroup$ Second question: I have no idea what "left" and "right" mean as branch directions. The up and down designations when branching on a variable mean round up and round down respectively. When branching on a constraint, I think the up/down designation is meaningful only if the user has specified a branching priority (e.g., branch in the down direction first). $\endgroup$ – prubin Sep 29 at 15:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.