Multi-objective branch and bound

Anthony Przybylski

doi:10.1016/j.ejor.2017.01.032

Return

Multi-objective branch and bound

2017-08-01

PRE

Anthony Przybylski *

Xavier Gandibleux

DOI：10.1016/j.ejor.2017.01.032

Original

Original request for help

Save

Abstract

En 中文

Branch and bound is a well-known generic method for computing an optimal solution of a single objective optimization problem. Based on the idea divide to conquer, it consists in an implicit enumeration principle viewed as a tree search. Although the branch and bound was first suggested by Land and Doig (1960), the first complete algorithm introduced as a multi-objective branch and bound that we identified was proposed by Kiziltan and Yucaoglu (1983). Rather few multi-objective branch and bound algorithms have been proposed. This situation is not surprising as the contributions on the extensions of the components of branch and bound for multi-objective optimization are recent. For example, the concept of bound sets, which extends the classic notion of bounds, has been mentioned by Villarreal and Karwan (1981). But it was only developed for the first time in 2001 by Ehrgott and Gandibleux, and fully defined in 2007. This paper describes a state-of-the-art of multi-objective branch and bound, which reviews concepts, components and published algorithms. It mainly focuses on the contributions belonging to the class of optimization problems who has received the most of attention in this context from 1983 until 2015: the linear optimization problems with zero-one variables and mixed 0-1/continuous variables. Only papers aiming to compute a complete set of efficient solutions are discussed. (C) 2017 Elsevier B.V. All rights reserved.

Keywords:

Multiple objective programming

Branch and bound

Bound sets

AI Summary

Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.