Multi-objective branch and bound
Multi-objective branch and bound
复制标题
DOI：
10.1016/j.ejor.2017.01.032
复制
发表时间：
2017-08
期刊：
影响因子：
--
通讯作者：
Anthony Przybylski;X. Gandibleux
中科院分区：
文献类型：
--
作者：
Anthony Przybylski;X. Gandibleux
分支定界法是一种计算单目标优化问题最优解的通用方法。基于“分而治之”的思想，它包含了一个被视为树搜索的隐枚举原则。虽然分支和界限是由Land和Doig（1960）首先提出的，但我们确定的第一个完整的多目标分支和界限算法是由Kiziltan和Yucaoglu（1983）提出的。很少有人提出多目标分支定界算法。这种情况并不奇怪，因为对多目标优化的分支和边界组件扩展的贡献是最近的。例如，Villarreal和Karwan（1981）提到了边界集的概念，它扩展了经典的边界概念。但直到2001年Ehrgott和Gandibleux才首次提出，并于2007年得到完整定义。本文介绍了多目标分支与定界的最新研究进展，对相关概念、组成部分和已发表的算法进行了综述。它主要集中在属于最优化问题的类别的贡献，从1983年到2015年，在这方面受到了最多的关注：具有0 - 1变量和混合0-1/连续变量的线性优化问题。仅讨论旨在计算一整套有效解的论文。
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.