Branching Strategies: Most Fractional, Pseudocost, Strong Branching

Three rules for choosing the branching variable in branch-and-bound: most fractional branching (closest to a half-integer), pseudocost branching (predicted degradation from historical averages), and strong branching (probing both child LPs directly). Each rule is evaluated with the product-rule branching score, and strong branching is extended to handle infeasible child LPs via variable fixing.

Step 1 of 157%

Tutorial

The Branching Variable Choice and Most Fractional Branching

In branch-and-bound, solving the LP relaxation of a subproblem produces a fractional point $\bar{\mathbf{x}}$ . If some integer-constrained variable $x_j$ takes a fractional value $\bar{x}_j$ , we branch by creating two children: the down branch with $x_j \leq \lfloor \bar{x}_j \rfloor$ and the up branch with $x_j \geq \lceil \bar{x}_j \rceil$ .

When several variables are fractional, the choice of branching variable can drastically alter the size of the search tree. The simplest selection rule is most fractional branching: pick the variable whose value lies closest to a half-integer. Quantitatively, define the fractionality

f_j = \min\!\left(\bar{x}_j - \lfloor \bar{x}_j \rfloor,\; \lceil \bar{x}_j \rceil - \bar{x}_j\right) \in \left[0,\, \tfrac{1}{2}\right],

and select $j^\star \in \arg\max_j f_j$ .

For example, $\bar{x}_1 = 4.3$ gives $f_1 = \min(0.3,\, 0.7) = 0.3$ , while $\bar{x}_2 = 7.5$ gives $f_2 = \min(0.5,\, 0.5) = 0.5$ . The most fractional choice is $x_2$ .

The intuition: a near-half-integer value is maximally ambiguous, so branching on it forces a real commitment in both children. The rule is fast but completely ignores the objective function.