Bucket elimination for multiobjective optimization problems
Bucket elimination for multiobjective optimization problems
复制标题
多目标优化问题的桶消除
DOI：
10.1007/s10732-006-6726-y
复制
发表时间：
2006
影响因子：
2.7
通讯作者：
J. Larrosa
中科院分区：
文献类型：
--
作者：
E. Rollon;J. Larrosa
多目标优化处理涉及应同时优化的多个性能指标的问题。在本文中，我们将桶消除（BE）（一种众所周知的动态规划通用算法）从单目标优化扩展到多目标优化。我们表明，所得算法 MO-BE 可以应用于真正的多目标问题以及具有背包（或相关）全局约束的单目标问题。我们还将迷你桶消除（MBE）（BE 的近似形式）扩展到多目标优化。新算法MO-MBE可以用来获得高质量的多目标下界，也可以将其集成到多目标分支定界中以提高其剪枝效率。其准确性在实际调度问题以及 Max-SAT-ONE 和生物目标加权最小顶点覆盖问题中进行了实证评估。
Multiobjective optimization deals with problems involving multiple measures of performance that should be optimized simultaneously. In this paper we extend bucket elimination (BE), a well known dynamic programming generic algorithm, from mono-objective to multiobjective optimization. We show that the resulting algorithm, MO-BE, can be applied to true multi-objective problems as well as mono-objective problems with knapsack (or related) global constraints. We also extend mini-bucket elimination (MBE), the approximation form of BE, to multiobjective optimization. The new algorithm MO-MBE can be used to obtain good quality multi-objective lower bounds or it can be integrated into multi-objective branch and bound in order to increase its pruning efficiency. Its accuracy is empirically evaluated in real scheduling problems, as well as in Max-SAT-ONE and biobjective weighted minimum vertex cover problems.