Choquet optimal set in biobjective combinatorial optimization

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 dierent 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 dened. 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 specic area of the objective space, but are much harder to compute than weighted sum optimal solutions