Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
Output-Sensitive Algorithms for Enumerating the Extreme Nondominated Points of Multiobjective Combinatorial Optimization Problems
复制标题
枚举多目标组合优化问题极值非支配点的输出敏感算法
DOI：
10.1007/978-3-662-48350-3_25
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
P. Mutzel
中科院分区：
文献类型：
--
作者：
F. Bökler;P. Mutzel
本文研究多目标组合优化（MOCO）中枚举问题的输出敏感算法。我们开发了两种方法来枚举 MOCO 问题帕累托前沿的极值点。第一种方法基于 Benson 算法的对偶变体，该算法最初是针对多目标线性优化问题提出的。我们证明，如果可以在多项式时间内求解加权和标量化，则该算法对于每个固定数量的目标都可以在输出多项式时间内运行。因此，我们提出了第一个在输出多项式时间内解决这个一般问题的算法。我们还提出了双 Benson 算法的新词典编版本，在词典编优化变体可以在多项式时间内求解的情况下，该算法在增量多项式时间内运行。因此，对于固定数量的目标，可以在多项式时间内计算多目标生成树问题以及多目标全局最小割问题的帕累托前沿的极值点。我们的计算实验证明了改进算法的实用性：我们提出了第一个计算研究，用于计算具有五个或更多目标的分配问题的多目标版本的极值点。我们还根据经验研究了新词典版本与原始算法相比的运行时行为。
This paper studies output-sensitive algorithms for enumeration problems in multiobjective combinatorial optimization (MOCO). We develop two methods for enumerating the extreme points of the Pareto-frontier of MOCO problems. The first method is based on a dual variant of Benson’s algorithm, which has been originally proposed for multiobjective linear optimization problems. We prove that the algorithm runs in output polynomial time for every fixed number of objectives if the weighted-sum scalarization can be solved in polynomial time. Hence, we propose the first algorithm which solves this general problem in output polynomial time. We also propose a new lexicographic version of the dual Benson algorithm that runs in incremental polynomial time in the case that the lexicographic optimization variant can be solved in polynomial time. As a consequence, the extreme points of the Pareto-frontier of the multiobjective spanning tree problem as well as the multiobjective global min-cut problem can be computed in polynomial time for a fixed number of objectives. Our computational experiments show the practicability of our improved algorithm: We present the first computational study for computing the extreme points of the multiobjective version of the assignment problem with five and more objectives. We also empirically investigate the running time behavior of our new lexicographic version compared to the original algorithm.
登录
查看更多内容
DOI：
--
发表时间：
2014
期刊：
Conference on Integer Programming and Combinatorial Optimization
影响因子：
--
作者：
Hassene Aissi;A. Ridha Mahjoub;S. T. McCormick;M. Queyranne
通讯作者：
M. Queyranne
参数和动力学最小生成树
DOI：
--
发表时间：
1998
期刊：
Proceedings 39th Annual Symposium on Foundations of Computer Science (Cat. No.98CB36280)
影响因子：
--
作者：
P. Agarwal;D. Eppstein;L. Guibas;Monika Henzinger
通讯作者：
Monika Henzinger
影响因子：
0.8
作者：
CHAZELLE, B
通讯作者：
CHAZELLE, B
多加权生成树问题（扩展摘要）
DOI：
--
发表时间：
1995
期刊：
International Computing and Combinatorics Conference
影响因子：
--
作者：
J. L. Ganley;M. Golin;Jeffrey S. Salowe
通讯作者：
Jeffrey S. Salowe
DOI：
--
发表时间：
1995
期刊：
影响因子：
--
作者：
J. L. Ganley;M. Golin;Jeffrey S. Salowe
通讯作者：
Jeffrey S. Salowe