A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization

Gonçalo Lopes

doi:10.1016/j.cor.2025.107140

A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization

2025-05-27

0

OA

AI

DOI：10.1016/j.cor.2025.107140

Original

Original request for help

Save

Abstract

En 中文

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 multiobjective 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.

Keywords:

Multiobjective combinatorial optimization

Hypervolume scalarization

Representation of the nondominated set

Greedy hypervolume algorithm

Local bounds

A greedy hypervolume polychotomic scheme for multiobjective combinatorial optimization

Abstract

Journal

Organization

Cited Papers