The GCG Branching Candidate Selection Heuristics

The branching candidate selection heuristic decides which of the candidates provided by the branching rule is selected. As this influences the size of the branch-and-bound tree, it can be highly influential on the runtime of the overall algorithm.

List of Selection Heuristics

As the the type of candidates can differ between the branching rules, the concrete implementation of the heuristics changes as well. Which heuristics are implemented for which branching rules in GCG is listed in the following table, more detailed explanations can be found below:

	Original Variable	Ryan-Foster	Vanderbeck Generic
Random Branching	X	X	X
Most Fractional/Infeasible Branching	X	(X)²
Pseudocost Branching	X	(X)²
Strong Branching with Column Generation¹	X	X
Strong Branching without Column Generation¹	X	X
Hybrid Branching¹	X	(X)³
Reliability Branching¹	X	(X)³
Hierarchical Branching¹	X	(X)³

¹ : GCG offers a highly customizable implementation of strong branching-based heuristics (currently in an experimental state), which, among other things, allows to combine them. Refer to this page for more information.
² : GCG can only aggregate the respective scores of the individual variables.
³ : These heuristics where originally meant to use pseudocost branching, see ². However, pseudocost branching can also be substituted by any other heuristic, with varying performance.

Discussion of Available Selection Heuristics

The goal of any selection heuristic is to select candidates in a way that will result in the smallest branch-and-bound tree. As determining these candidates is (to our current knowledge) computationally infeasible, the heuristics instead pick candidates that optimize some other criterion that is potentially thought to be a good indicator of the resulting tree size.

Random Branching

Randomly selects a candidate.

Most Fractional/Infeasible Branching

Selects one of the candidates where the distance of the current solution value of the corresponding variable to the next candidate is maximal.

The following heuristics all try to maximize the aggregated gain in dual bound in the child nodes that would be created if a given candidate was branched on. Letting \( z \) and \( z_i \) be the dual bound of the current node and child node \( i \), respectively, the gain of child node \( z_i \) is equal to \( z - z_i \).

Pseudocost Branching

Pseudocost branching was designed to be used in conjunction with branching on (original/master) variables, and will likely not be as effective if used with other branching rules.

Pseudocost branching estimates the gain by averaging previous nodes where a given candidate was branched on: given some candidate that introduces bounds on a single variable \( x_i \), the projected up gain ("upwards pseudocost") is

\begin{align} \Phi^+(x_i) := \frac{1}{|I^+_i|}\sum_{i \in I^+_i}\frac{z'_{u_i(y)} - z'_y}{\bar{x}_i - \lfloor\bar{x}_i\rfloor}, \end{align}

where \( I^+_i \) is the set of nodes where \( x_i \) already was branched on and the up branch has already been solved, \( u_i(y) \) is the up branch when branching on \( x_i \) in node \( y \), \( z'_y \) is the local lower bound of node \( y \), and \( \bar{x}_i \) is the solution value of \( x_i \) in the current node. The projected down gain can be calculated analogously.

Strong Branching (with or without Column Generation)

Strong branching estimates the gain by actually solving the respective child nodes. Fully evaluating all child nodes is called (all) full strong branching. We additionally differentiate between strong branching with and strong branching without column generation, i.e. strong branching can be relaxed by not performing column generation to evaluate the child nodes. Using strong branching generally results in smaller trees, however its significant computational effort means that it is usually not worth it to use just strong branching.

Hybrid Pseudocost/Strong Branching

Hybrid pseudocost/strong branching uses strong branching for nodes up to a given depth, and pseudocost branching for all nodes after that. GCG can substitute any of the aformentioned heuristics for the latter, and both strong branching with and without column generation for the former. Furthermore, GCG can dynamically adjust the height parameter based on the total number of binary and integer variables.

Reliability Branching

Reliability branching uses strong branching for some candidate \( if \) if its pseudocost values are not reliable enough yet, i.e. if the size of either I^+_i or I^-_i (see the section on pseudocost branching) is below a given threshold. Pseudocost branching is applied to all other candidates. GCG can substitute any of the aformentioned heuristics (except hybrid branching) for the latter, and both strong branching with and without column generation for the former.

Hierarchical Branching

In hierarchical branching, the selection process is divided into three phases, where

in phase 0, the candidates are filtered based on some heuristic that is quick to compute (e.g. pseudocost branching), then
in phase 1, the remaining candidates are filtered based their strong branching without column generation scores, and finally
in phase 2, a candidate is selected out of the remaining candidates based on the score the candidates receive from strong branching with column generation.

Parameters for Branching Candidate Selection Heuristics

Some of the selection heuristics, in GCG primarily those that are based on strong branching, can further be adjusted by setting values for certain parameters. These parameters include the depth until which strong branching is performed for hybrid branching, the reliability parameter for reliability branching, or the number of candidates that pass through each phase for hierarchical branching. See here for a full list of the available parameters, together with descriptions, value ranges and default values.
While in GCG, the parameters can individually be changed before optimizing a given problem, the best way to do so is by loading a settings file. This can either be done from inside GCG by entering

set load [path/to/settings/file].set

or when starting GCG from the command line by adding the option

-s "[path/to/settings/file].set"

You can find further information on settings files here.
GCG already has several preconfigured settings files for the heuristics introduced on this page, which can be found in the settings folder, where orig refers to original variable branching and rf to Ryan-Foster branching:

[orig/rf]Random              : random branching
origMostFrac                 : most fractional/infeasible branching
origPseudo                   :
[orig/rf]FullSBCG            : full strong branching with column generation
[orig/rf]FullSBnoCG          : full strong branching without column generation
[orig/rf]HybridCGFixedParams : hybrid pseudocost/strong branching with column generation with fixed depth parameters
[orig/rf]HybridCGDynParams   : hybrid pseudocost/strong branching with column generation with dynamic depth parameters
[orig/rf]ReliabilityCG       : reliability branching with column generation
[orig/rf]Hierarchical        : hierarchical strong branching
[orig/rf]HybridHierarchical  : hierarchical strong branching combined with hybrid branching
rfHierarchicalNoP0           : hierarchical strong branching without the first phase

These files might provide a good starting point for the configuration you wish to achieve. Additionally, the file strongBranchingParams.set again contains all parameters together with descriptions, value ranges and default values.
As you might have noticed, the above list also contains settings files that combine multiple of the aforementioned heuristics ([orig/rf]HybridHierarchical.set). This is possible because all of the strong branching-based heuristics are implemented inside the same method. Combining heuristics this way can be beneficial for some instances.

Adding own Branching Candidate Selection Heuristics

If you want to add your own branching candidate selection heuristics, i.e. define exactly which candidates are selected please consider our "How to add" for that.

How to add branching rules & selection heuristics