Node Selection: Best-First, Depth-First, Best-Estimate

After branching, a solver typically has many open nodes waiting to be processed. The rule for deciding which one to process next is called the node selection strategy. The choice affects how fast the solver tightens its global bound, how fast it finds feasible integer solutions, and how much memory it uses.

Consider a minimization MILP. Every open node $N$ carries an LP relaxation value $z^{\text{LP}}_N,$ which is a lower bound on the integer optimum over the subtree rooted at $N.$ The global lower bound is the minimum of these values over the set $\mathcal{A}$ of open nodes:

$$\underline{z} \;=\; \min_{N \in \mathcal{A}} z^{\text{LP}}_N.$$

Best-first (also called best-bound) node selection picks the open node attaining this minimum:

$$N^{*} \;=\; \arg\min_{N \in \mathcal{A}} z^{\text{LP}}_N.$$

The motivation: that node is the one currently holding $\underline{z}$ down, so processing it has the greatest potential to raise the global bound and close the optimality gap.

For example, if the open nodes have LP bounds $12.4,\ 9.7,\ 11.0,\ 13.5,$ best-first selects the node with bound $9.7.$