The next theorem shows that an aggregate compatible mapping must be a semiring homomorphism.

Theorem 6.1. Let α : S → Se be a mapping between two totally ordered semirings. Then α is aggregate compatible if and only if α *is a semiring homomorphism.*
Proof. **A semiring homomorphism is clearly aggregate compatible. On the other** hand, suppose α is aggregate compatible. Since it is monotonic, α **preserves**
sums. Moreover, by Equation 8, for any a, b ∈ S, taking I1 = {**a, b**}, I2 = {a×b},
from α(a×b) = α(a×b) we have α(a)×eα(b) = α(a×b). That is, α **also preserves**
products. Hence α **is a semiring homomorphism.**
Therefore our framework is also a generalization of that of de Givry **et al.**
More importantly, results obtained in Sections 4 and 5 can be applied to valued CSPs.

We first note that any monotonic mapping from a totally ordered set is order-reflecting.

Lemma 6.1. Let (C, ⊑) be a totally ordered set, and (A, ≤) *a poset. Suppose* α : **C → A** is monotonic mapping. Then α *is order-reflecting.* Proof. By contradiction, suppose there are a, b ∈ C such that α(a) < α(b**) but**
a 6⊏ b. Then since ⊑ is a total order we know b ⊑ a**. But by the monotonicity**
of α, we have α(b) ≤ α(a). This contradicts the assumption that α(a) < α(b). Therefore α **is order-reflecting.**
Now, we have the following corollary of Theorem 4.1, which was also obtained by de Givry et al. [4] for aggregation compatible mappings.

Corollary 6.1. Let α *be a semiring homomorphism between two c-semirings* S
and Se. Suppose S is a totally ordered c-semiring. Then for any SCSP P *over* S*, it holds that* Opt(P) ⊆ Opt(α(P)).

Proof. By Lemma 6.1, α **is order-reflecting. The conclusion then follows directly** from Theorem 4.1.

## 7 Conclusions

In this paper we proposed a homomorphism based abstraction scheme for soft constraints. The intuition is that we first work in the abstract problem, finding all optimal solutions, and then use them to find optimal solutions of the concrete problem. Surprisingly, our framework turns out to be a generalization of that of de Givry et al. [4], where they consider totally ordered sets.

In detail, our Theorem 4.1 showed that a mapping preserves optimal solutions if and only if it is an order-reflecting semiring homomorphism; and Theorem 5.1 showed that, for a semiring homomorphism α and a problem P **over** S,
if t is an optimal solution of α(P), then there is an optimal solution of P**, say** t¯,
such that t¯ is also optimal in α(P) and has the same value as t**. These results**
greatly improved or generalized those obtained in Bistarelli et al. [1].