Using soft CSPs for approximating pareto-optimal solution sets

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.