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.