Using soft csps for approximating pareto-optimal solution sets

We consider constraint satisfaction problems where so-lutions must be optimized according to multiple crite-ria. 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 approxima-tions of the Pareto-optimal set. We also derive variants that further improve the performance