  We consider range minimization problems featuring exponentially many
variables, as frequently arising in fairness-oriented or bi-objective
optimization. While branch and price is successful at solving cost-oriented
problems with many variables, the performance of classical branch-and-price
algorithms for range minimization is drastically impaired by weak linear
programming relaxations. We propose range branching, a generic branching rule
that directly tackles this issue and can be used on top of problem-specific
branching schemes. We show several desirable properties of range branching and
show its effectiveness on a series of instances of the fair capacitated vehicle
routing problem and fair generalized assignment problem. Range branching
significantly improves multiple classical branching schemes in terms of
computing time, optimality gap, and size of the branch-and-bound tree, allowing
us to solve many more large instances than classical methods. Moreover, we show
how range branching can be successfully generalized to order-based objective
functions, such as the Gini deviation.
