Representative Solutions for Multi-Objective Constraint Optimization Problems

Solving a multi-objective constraint optimization problem (MO-COP) typically consists in computing all Pareto optimal solutions, which are exponentially many in the general case. This causes two problems: time complexity and lack of decisiveness. We present an approach which, given a number k of desired solutions, selects k Pareto optimal solutions that are representative of the Pareto front. We analyze the computational complexity of the underlying computational problem and provide exact and approximation procedures.