Multi-objective branch-and-bound. Application to the bi-objective spanning tree problem.
Francis Sourd (francis.sourdlip6.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.
Entry Submitted: 02/14/2007
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|