This paper addresses two issues: how to choose between solutions for a problem specified by multiple criteria, and how to search for solutions in such situations. We argue against an approach common in decision theory, reducing several criteria to a single ‘cost’ (e.g., using a weighted sum cost function) and instead propose a way of partially ordering solutions satisfying a set of prioritised soft constraints. We describe a generalisation of the A^* search algorithm which uses this ordering and prove that under certain reasonable assumptions the algorithm is complete and optimal.