An algorithm computing the Pareto frontier in constraint satisfaction problems

Real-life problems often exhibit a multi-criteria structure: user requirements are many and possibly conflicting. In combinatorial optimization, criteria are functions, ranging on the set of possible solutions. A widely used approach suggests to compute a weighted sum of the different criteria. Unluckily, deciding the weights beforehand is not always straightforward; moreover, the weighted sum approach often provides extreme solutions, while the user usually prefers balanced solutions. In this paper, we propose an algorithm to compute Pareto optimal solutions in Constraint Satisfaction Problems. A solution is Pareto optimal if it is not possible an improvement in one criterion without worsening other criteria. The algorithm is complete, and can provide the whole set of Pareto optimal solutions. Since the set of Pareto optimal solutions can be huge and the algorithm needs to access them efficiently, we propose to arrange them in a suitable data structure, namely Point Quad-Trees. Experimental results show the effectiveness of the proposed method.