Branching Rules

Table of Contents

• First Infeasible Found
• Least Infeasible
• Most Infeasible
• Pseudo Cost Branching
• Strong Branching
  • Full Strong Branching
  • Restricted Strong Branching
  • Strong Branching with Phases
  • Strong Branching with Look Ahead
  • Changing the Scoring Function
• Uniformly Random Branching
• Branching with Priorities
• Writing Your Own Branching Rule

Given a node selected for exploration, the next step is to decide how to split the node into new nodes. Here again, several strategies are at hand.

Branching Rule	Purpose / Guideline
First Infeasible Found	Branch on the first infeasible variable found; simple and fast.
Least Infeasible	Branch on variable closest to feasibility.
Most Infeasible	Branch on variable farthest from feasibility; may reduce infeasibilities faster.
Pseudo Cost	Branch on variable with highest historical impact on objective; balances efficiency and effectiveness.
Strong Branching	Test candidate branches before choosing; often gives best node reduction but more expensive.
Uniformly Random	Pick a variable randomly; mainly for testing.

First Infeasible Found

The first infeasible found strategy selects the first variable that violates its integrality constraint.

Here is how to use it.

branch_and_bound.with_branching_rule(FirstInfeasibleFound());

Least Infeasible

The least infeasible strategy selects the variable whose value is closest to an integer.

Here is how to use it.

branch_and_bound.with_branching_rule(LeastInfeasibleFound());

Most Infeasible

The most infeasible strategy selects the variable whose value is farthest from an integer.

Here is how to use it.

branch_and_bound.with_branching_rule(MostInfeasibleFound());

Pseudo Cost Branching

The pseudo cost strategy selects the variable with the highest estimated impact on the objective value, based on past branching decisions. To do so, for each branching candidate \( x_j \), two scores are first computed:

• an upper bounding score (for the branch \( x_j \le \lfloor x_j^* \rfloor \))

  \[ \text{score}^+_j = (x_j^* - \lfloor x_j^* \rfloor) \cdot \frac{ \sum_{k} \Delta\text{obj}_{kj}^+ }{ n_j } \]

• a lower bounding score (for the branch \( x_j \ge \lceil x_j^* \rceil \))

  \[ \text{score}^-_j = (\lceil x_j^* \rceil - x_j^*) \cdot \frac{ \sum_{k} \Delta\text{obj}_{kj}^- }{ n_j } \]

Here,

• \( x^* \) denotes the current node solution,
• \( n_j \) denote the number of times \( x_j \) has previously been selected for branching,
• \( \Delta\text{obj}_{kj}^+ \) (resp., \( \Delta\text{obj}_{kj}^- \)) denotes the objective change that occurred at node \( k \) after having branched on \( x_j \) in the left (resp., right) child node w.r.t. the parent node.

Then, the two scores are combined using one of the two following formulas:

• a linear one using (with default value \( \alpha = 1/16 \))

  \[ \text{score}_j = (1 - \alpha) \times \min\{ \text{score}^+_j, \text{score}^-_j \} + \alpha\times \max\{ \text{score}^+_j, \text{score}^-_j \}. \]

  This slightly favors the larger score while keeping a base weight on the smaller one. It is the default setting.
• a quadratic one using (with default value \( \varepsilon = 10^{-6} \))

  \[ \text{score}_j = \min\{ \varepsilon, \text{score}^+_j \} \times \min\{ \varepsilon, \text{score}^-_j \} \]

  This method heavily penalizes variables where one score is very small, favoring variables that are strong in both directions.

The branching candidate with the highest score is selected for branching.

Here is how to use it.

branch_and_bound.with_branching_rule(PseudoCost());

Warning

TODO add how to change node scoring function and their parameters

Strong Branching

Strong branching is a sophisticated variable selection strategy that estimates the impact of branching by temporarily solving child nodes before making the final branching decision.

More specifically, for each branching candidate, strong branching requires to solves, before branching happens, the left and right child node. Thus, two scores are computed:

• an upper bounding score (for the branch \( x_j \le \lfloor x_j^* \rfloor \))

  \[ \text{score}^+_j = \text{objective\_value}^+ - \text{parent\_objective\_value} \]

• a lower bounding score (for the branch \( x_j \ge \lceil x_j^* \rceil \))

  \[ \text{score}^-_j = \text{objective\_value}^- - \text{parent\_objective\_value} \]

Here,

• \( \text{parent\_objective\_value} \) denotes the optimal objective function value of the parent node,
• \( \text{objective\_value}^+ \) (resp., \( \text{objective\_value}^- \)) denotes the objective value of the left (resp., right) node.

Then, the two scores are combined using one of the two formulas that are detailed in the pseudo cost section.

The branching candidate with the highest score is selected for branching.

Several variants of strong branching exists, and are detailed next along with their implementation in idol.

Full Strong Branching

Full strong branching denotes the standard strong branching rule which solves twice as many nodes as there are branching candidates at each node selected for branching. Thus, a clear drawback is that it may take a lot of time to solve all these sub-problems.

Here is how to use it.

branch_and_bound.with_branching_rule(StrongBranching());

Restricted Strong Branching

Restricted strong branching is an attempt to reduce the computational burden of full strong branching. The idea is to consider only a maximum of \(K\) branching candidates at each branching decision instead of the whole set of branching candidates. At each node, we therefore build a "restricted branching candidate set" obtained by taking the \( K \) first variables selected by another branching rule. Then, strong branching is applied on these \( K \) variables.

Here is how to use it, here with \( K = 10 \).

branch_and_bound.with_branching_rule(StrongBranching().with_max_n_variables(10));

By default, the branching rule used to select the \( K \) candidates is the most infeasible branching rule.

Strong Branching with Phases

Strong branching with phases is a combination of the above approaches which applies different schemes depending on the level of the current node in the branch-and-bound tree. Additionally, it allows to solve each node only approximately by, e.g., imposing a maximum number of iterations for the underlying optimizer.

Here is an example of strong branching with phases which, for nodes whose level is below or equal to 3, applies full strong branching, then switches to restricted strong branching with \( K = 30 \) and solves nodes with an iteration limit of 20.

auto strong_branching = StrongBranching();
strong_branching.add_phase(StrongBranchingPhases::WithNodeOptimizer(), std::numeric_limits<unsigned int>::max(), 3)
strong_branching.add_phase(StrongBranchingPhases::WithIterationLimit(20), 30, std::numeric_limits<unsigned int>::max());
 
branch_and_bound.with_branching_rule(strong_branching);

Observe how we used :code:std::numeric_limits<unsigned int>::max() to remove restrictions on the number of considered variables and on the maximum depth for the final phase. Note that, by default, if no phase is triggered for a given depth, e.g., because it was not specified, full strong branching is applied. Here, however, we make sure that the second phase is always triggered.

Strong Branching with Look Ahead

Strong branchign with look ahead is similar to restricted strong branching yet differs from it by not specifying a fixed size for the "restricted branching candidate set". Instead, it considers a look ahead parameter, noted \( L \), and applies the full strong branching rule until the branching candidate does not change after \( L \) iterations. Then, the algorithm stops and the current branching candidate is returned.

Unfortunately, this approach is not yet implemented in idol.

Changing the Scoring Function

The scoring function can be changed using the .with_scoring_function method. For instance, here is how to use the quadratic scoring function.

auto strong_branching = StrongBranching();
strong_branching.with_scoring_function(NodeScoreFunctions::Product()); 

Uniformly Random Branching

The uniformly random strategy selects a branching variable randomly among all candidates.

Here is how to use it.

branch_and_bound.with_branching_rule(UniformlyRandom());

Branching with Priorities

Branching with priorities groups variables into batches according to user-defined priorities. Within each batch, a standard branching rule (e.g., most infeasible) is applied to select the next variable. Higher-priority batches are always considered before lower-priority ones, allowing you to control the order in which variables are branched on.

Here is an example.

std::vector<Var> high_priority = { x[0], x[1], x[3] };
std::vector<Var> low_priority = { x[4], x[5], x[6] };
 
auto branching_with_priority = BranchingWithPriority();
branching_with_priority.add_branching_rule(StrongBranching(high_priority.begin(), high_priority.end()));
branching_with_priority.add_branching_rule(MostInfeasible(low_priority.begin(), low_priority.end()));

Here, the branching strategy is as follows. First, it considers variables in the high-priority batch and uses (full) strong branching. Once all the variables in this batch have integer values, it considers the low-priority batch and uses the most infeasible rule.

Writing Your Own Branching Rule

Warning

TODO write this section