Choquet optimal set in biobjective combinatorial optimization |
| |
Authors: | Thibaut Lust Antoine Rolland |
| |
Affiliation: | 1. LIP6, Université Pierre et Marie Curie, 4, place Jussieu, F-75252 Paris Cedex 05, France;2. Laboratoire ERIC - Université Lumière Lyon 2, 5, avenue Pierre Mendes-France, F-69676 Bron Cedex, France |
| |
Abstract: | We study in this paper the generation of the Choquet optimal solutions of biobjective combinatorial optimization problems. Choquet optimal solutions are solutions that optimize a Choquet integral. The Choquet integral is used as an aggregation function, presenting different parameters, and allowing to take into account the interactions between the objectives. We develop a new property that characterizes the Choquet optimal solutions. From this property, a general method to easily generate these solutions in the case of two objectives is defined. We apply the method to two classical biobjective optimization combinatorial optimization problems: the biobjective knapsack problem and the biobjective minimum spanning tree problem. We show that Choquet optimal solutions that are not weighted sum optimal solutions represent only a small proportion of the Choquet optimal solutions and are located in a specific area of the objective space, but are much harder to compute than weighted sum optimal solutions. |
| |
Keywords: | Multiobjective optimization Choquet integral Algorithmic decision theory Knapsack problem Minimum spanning tree problem |
本文献已被 ScienceDirect 等数据库收录! |
|