Node Selection Rules

Table of Contents

• Best Bound
• Best Estimate
• Breadth First
• Depth First
• Worst Bound
• Writing Your Own Node Selection Rule

Node selection rules are responsible for picking the next node to be explored within the list of active nodes. Different strategies are possible, and can be configured with the help of the with_node_selection_rule method.

Here is a quick sumary.

Rule	Purpose / Guideline
Best Bound	Pick node with best bound; fast convergence.
Best Estimate	Balance objective and feasibility; favors near-feasible nodes.
Breadth First	Explore level by level; uniform search.
Depth First	Explore deep branches first; memory-efficient, finds feasible solutions quickly.
Worst Bound	Pick worst bound; mainly for testing.

Best Bound

The best bound strategy selects the node with the best (i.e., the lowest) bound among all active nodes.

Here is how to use it.

branch_and_bound.with_node_selection_rule(BestBound());

Best Estimate

The best estimate strategy selects the node that is expected to lead to the best final solution by combining objective value and degree of infeasibility.

To do so, a score is computed for each node and the one with the lowest score is selected. The score is computed as follows.

\[ \begin{equation} \text{score} = \text{objective\_value} + \frac{ (\text{root\_node\_objective} - \text{incumbent\_objective}) \times \text{sum\_of\_infeasibilities} }{ \text{root\_node\_sum\_of\_infeasibilities} } \end{equation} \]

where

• objective_value is the objective value at the current node;
• sum_of_infeasibilities is the sum of violation of integralities constraints at the node;
• incumbent_objective is the objective value of the best known feasible point so far;
• root_onode_bjective and root_node_sum_of_infeasibilities are the values stored at the root node of "objective_value" and "sum_of_infeasibilities".

Intuitively, this balances two factors: nodes with high objective values are promising, but nodes that are less infeasible (closer to satisfying integrality constraints) are more likely to lead to feasible solutions.

If there is no incumbent solution yet, the strategy defaults to the node with the best objective value. Thus, it acts like the best bound approach.

Here is how to use it.

branch_and_bound.with_node_selection_rule(BestEstimate());

This node selection rule is due to J. J. H. Forrest et al. (1974) under the name "Best Projection".

Breadth First

The breadth first strategy explores nodes level by level, starting from the root and moving across all nodes at a given depth before descending further.

Here is how to use it.

branch_and_bound.with_node_selection_rule(BreadthFirst());

Depth First

The depth first strategy explores a branch as far as possible before backtracking. It can quickly find feasible solutions deep in the tree, which helps prune other branches early. However, it may waste time exploring suboptimal branches if the initial path is not promising.

Here is how to use it.

branch_and_bound.with_node_selection_rule(DepthFirst());

Worst Bound

The worst bound strategy selects the node with the worst (i.e., the highest) bound among all active nodes.

Here is how to use it.

branch_and_bound.with_node_selection_rule(WorstBound());

Writing Your Own Node Selection Rule

Warning

TODO write this section