Using Soft CSPs for Approximating Pareto-Optimal Solution Sets

Marc Torrens and Boi Faltings

We consider constraint satisfaction problems where solutions must be optimized according to multiple criteria. When the relative importance of different criteria cannot be quantified, there is no single optimal solution, but a possibly very large set of Pareto-optimal solutions. Computing this set completely is in general very costly and often infeasible in practical applications. We consider several methods that apply algorithms for soft CSP to this problem. We report on experiments, both on random and real problems, that show that such algorithms can compute surprisingly good approximations of the Pareto-optimal set. We also derive variants that further improve the performance.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.