Multi-objective branch-and-bound. Application to the bi-objective spanning tree problem.

Francis Sourd (francis.sourdlip6.fr)
Olivier Spanjaard (olivier.spanjaardlip6.fr)

Abstract: This paper focuses on a multi-objective derivation of branch-and-bound procedures. Such a procedure aims to provide the set of Pareto optimal solutions of a multi-objective 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 bi-objective spanning tree problem are provided that show the efficiency of the approach.

Keywords: multi-objective combinatorial optimization; branch-and-bound; bi-objective spanning tree problem

Category 1: Other Topics (Multi-Criteria Optimization )

Citation: Working paper. LIP6. 2006.

Download: [PDF]

Entry Submitted: 02/14/2007
Entry Accepted: 02/14/2007
Entry Last Modified: 03/05/2007

Modify/Update this entry