Branch Selection Callback

INDEX PREVIOUS NEXT

After CPXsetbranchcallbackfunc is called with a pointer to a user callback routine, the user routine is called whenever CPLEX makes a branching decision. CPLEX indicates which variable has been chosen for branching and allows the user to modify that decision. The user may specify the number of children for the current node (between 0 and 2), and the set of bounds or constraints that are modified for each child through one of the routines CPXbranchcallbackbranchbds, CPXbranchcallbackbranchconstraints, or CPXbranchcallbackbranchgeneral. The children are explored in the order that they are returned. The branch callback routine is called for all viable nodes. In particular, it will be called for nodes that have zero integer infeasibilities; in this case, CPLEX will not have chosen a branch variable, and the default action will be to discard the node. The user can choose to branch from this node and in this way impose additional restrictions on integer solutions.

For example, a user branch routine may call CPXgetcallbacknodeintfeas to identify branching candidates, call CPXgetcallbackpseudocosts to obtain pseudo-cost information on these variables, call CPXgetcallbackorder to get priority order information, make a decision based on this and perhaps other information, and then respond that the current node will have two children, where one has a new lower bound on the branch variable and the other has a new upper bound on that variable.

We should point out one important detail associated with the use of the CPX_PARAM_MIPCBREDLP parameter in a branch callback. If this parameter is set to CPX_OFF (0), the user can choose branch variables (and add bounds) for the original problem. However, not every fractional variable is actually available for branching. Recall that some variables are replaced by linear combinations of other variables in the presolved problem. Since branching involves adding new bounds to specific variables in the presolved problem, a variable must be present in the presolved problem for it to be branched on. The user should use the CPXgetcallbacknodeintfeas routine from the Advanced Presolve Interface to find branching candidates (those for which CPXgetcallbacknodeintfeas returns CPX_INTEGER_INFEASIBLE). The CPXcopyprotected routine can be used to prevent presolve from removing specific variables from the presolved problem. (In Concert Technology, this issue is handled for you automatically.) While restricting branching may appear to limit your ability to solve a problem, in fact a problem can always be solved to optimality by branching only on the variables of the presolved problem.