A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization

Gonçalo Lopes

doi:10.1016/j.cor.2025.107140

2025-05-27

Gonçalo Lopes *

Kathrin Klamroth

Luís Paquete

DOI：10.1016/j.cor.2025.107140

原文链接

原文求助

摘要

En 中文

多目标组合优化的通常目标是找到非支配点的完整集合。然而，在一般情况下，非支配集可能过于庞大，以至于在严格的时间预算下无法枚举。在这种情况下，更优选的是快速获得满足给定关注属性的非支配集的简洁表示。本工作描述了一种通用的贪心方法，用于计算多目标组合优化问题的非支配集表示，该方法近似最大化支配超体积。该表示通过迭代构建，通过解决一系列超体积标量化问题，每个问题针对k个参考点，这是我们方法的一个参数。我们提出了k个参考点的超体积标量化函数的混合整数公式，以及m目标背包问题的组合分支定界法。我们经验性地分析了k与其运行时间和表示质量之间的函数关系。我们的结果表明，分支定界法是一种高效得多的方法，并且增加k并不直接转化为更好的表示质量。

Keyword:

Multiobjective combinatorial optimization

Hypervolume scalarization

Representation of the nondominated set

Greedy hypervolume algorithm

Local bounds