Discrete Mathsfor Engineers

5. Node Selection Strategies

In Branch & Bound, pruning depends on bounds, but performance also depends on which node is explored next.

Even with the same branching structure and the same bounding function, different node selection strategies can lead to very different search behavior.

5.1 Why node selection matters

At any point in the algorithm, several live nodes may remain in the frontier. The algorithm must decide which one to expand next.

This decision matters because:

• it affects how quickly a good incumbent is found,
• it influences how much memory is required,
• and it changes how early pruning becomes effective.

5.2 The frontier of live nodes

The algorithm keeps a set of nodes that have been generated but not yet expanded.

These nodes are often called live nodes, and the full set is called the frontier.

A node selection strategy is essentially a rule for choosing one node from this frontier.

5.3 Depth-first search (DFS)

In a depth-first strategy, the algorithm always continues along the most recently generated branch.

This is usually implemented with a stack.

• Advantage: low memory usage
• Advantage: often finds a complete solution quickly
• Disadvantage: may spend a long time in an unpromising region

DFS is especially attractive when memory is limited or when obtaining an initial incumbent early is useful.

5.4 Breadth-first search (BFS)

In a breadth-first strategy, the algorithm explores nodes level by level.

This is usually implemented with a queue.

• Advantage: systematic level-by-level exploration
• Advantage: useful for certain structural analyses
• Disadvantage: can require a large amount of memory

In large combinatorial problems, BFS is often expensive in practice because the frontier may grow very quickly.

5.5 Best-first search

In a best-first strategy, the algorithm chooses the live node with the most promising bound.

This is usually implemented with a priority queue.

• Advantage: often finds strong incumbents early
• Advantage: can improve pruning significantly
• Disadvantage: requires maintaining ordered priorities

Best-first is one of the most common strategies in practical Branch & Bound implementations.

5.6 Comparing the main strategies

• DFS: low memory, deep exploration
• BFS: wide exploration, high memory
• Best-first: exploration guided by bound quality

The best strategy depends on the problem, the quality of the bound, and the computational resources available.

5.7 Interaction with the incumbent

Node selection affects how quickly the incumbent improves.

If a strategy tends to find good complete solutions early, then the incumbent becomes strong sooner, which makes pruning more aggressive later.

This is one reason why best-first search often performs well in practice: it tends to prioritize nodes that are likely to yield strong completions.

5.8 Summary

• Node selection determines the exploration order
• DFS uses a stack
• BFS uses a queue
• Best-first uses a priority queue
• The strategy affects memory, incumbent quality, and pruning efficiency