  In the bi-objective branch-and-bound literature, a key ingredient is
objective branching, i.e. to create smaller and disjoint sub-problems in the
objective space, obtained from the partial dominance of the lower bound set by
the upper bound set. When considering three or more objective functions,
however, applying objective branching becomes more complex, and its benefit has
so far been unclear. In this paper, we investigate several ingredients which
allow to better exploit objective branching in a multi-objective setting. We
extend the idea of probing to multiple objectives, enhance it in several ways,
and show that when coupled with objective branching, it results in significant
speed-ups in terms of CPU times. We also investigate cut generation based on
the objective branching constraints. Besides, we generalize the best-bound idea
for node selection to multiple objectives and we show that the proposed rules
outperform the, in the multi-objective literature, commonly employed
depth-first and breadth-first strategies. We also analyze problem specific
branching rules. We test the proposed ideas on available benchmark instances
for three problem classes with three and four objectives, namely the
capacitated facility location problem, the uncapacitated facility location
problem, and the knapsack problem. Our enhanced multi-objective
branch-and-bound algorithm outperforms the best existing branch-and-bound based
approach and is the first to obtain competitive and even slightly better
results than a state-of-the-art objective space search method on a subset of
the problem classes.
