Which Soft Constraints do you Prefer?

Soft constraints are gaining popularity in diverse areas such as orchestration of Web services or optimization of scheduling decisions. However, current approaches to soft constraints preclude them from modelling certain decision problems with multiple preference criteria. We propose a new approach to soft constraints which allows a natural expression of these problems, describe an implementation in the rewriting logic system Maude, and prove its correctness.