15th European Conference on Artificial Intelligence
  July 21-26 2002     Lyon     France  

ECAI-2002 Conference Paper

[PDF] [full paper] [prev] [tofc] [next]

An Algorithm for Multi-Criteria Optimization in CSPs

Marco Gavanelli

Constraint Satisfaction and Optimization are important areas of Artificial Intelligence. However, in many real-life applications, more functions should be optimized at the same time; the user needs to be provided a set of solutions and a posteriori choose the most preferable. In this paper, we propose an algorithm for solving Multi-Criteria Optimization problems in this setting. The algorithm is complete, i.e., it finds all the non-dominated solutions, and does not make any assumption on the structure of the constraints nor on the type of the objective functions. It exploits Point Quad-Trees for the representation of the non-dominated frontier, in order to efficiently access the data. We describe the implementation and give experimental results showing that our algorithm outperforms widely used methods.

Keywords: Constraint Programming, Constraint Satisfaction, Search

Citation: Marco Gavanelli: An Algorithm for Multi-Criteria Optimization in CSPs. In F. van Harmelen (ed.): ECAI2002, Proceedings of the 15th European Conference on Artificial Intelligence, IOS Press, Amsterdam, 2002, pp.136-140.

[prev] [tofc] [next]

ECAI-2002 is organised by the European Coordinating Committee for Artificial Intelligence (ECCAI) and hosted by the UniversitÚ Claude Bernard and INSA, Lyon, on behalf of Association Franšaise pour l'Intelligence Artificielle.