Relaxation of soft constraints via a unified semiring

The semiring framework for constraint satisfaction allows us to model a wide variety of problems of choice. Semiring constraint satisfaction problems are able to represent both classical consistency and optimisation problems, as well as soft constraint problems such as valued and weight CSPs. In this paper we pose and answer the question: how can we represent and ‘solve’ the relaxation of a semiring constraint satisfaction problem