A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization
提出一种贪婪方法，通过求解一系列超体积标量化问题，快速获得多目标组合优化问题非支配集的简洁表示，并近似最大化支配超体积。
The usual goal in multiobjective combinatorial optimization is to find the complete set of nondominated points. However, in general, the nondominated set may be too large to be enumerated under a tight time budget. In these cases, it is preferable to rapidly obtain a concise representation of the nondominated set that satisfies a given property of interest. This work describes a generic greedy approach to compute a representation of the nondominated set for multi-objective combinatorial optimization problems that approximately maximizes the dominated hypervolume. The representation is built iteratively by solving a sequence of hypervolume scalarized problems, each of which with respect to k reference points, which is a parameter of our approach. We present a mixed-integer formulation of the hypervolume scalarization function for k reference points as well as a combinatorial branch-and-bound for the m -objective knapsack problem. We empirically analyse the functional relationship between k and its running-time and representation quality. Our results indicate that the branch-and-bound is a much more efficient approach and that increasing k does not directly translate into much better representation quality.