A Multiobjective Branch-and-Bound Framework: Application to the Biobjective Spanning Tree Problem

This paper focuses on a multiobjective derivation of branch-and-bound procedures. Such a procedure aims to provide the set of Pareto-optimal solutions of a multiobjective combinatorial optimization problem. Unlike previous works on this issue, the bounding is performed here via a set of points rather than a single ideal point. The main idea is that a node in the search tree can be discarded if one can define a separating hypersurface in the objective space between the set of feasible solutions in the subtree and the set of points corresponding to potential Pareto-optimal solutions. Numerical experiments on the biobjective spanning tree problem are provided that show the efficiency of the approach in a biobjective setting.