
## 4 Mappings Preserving Optimal Solutions

In this section we discuss when a translation preserves optimal solutions, i.e.

when all optimal solutions of the concrete problem are also optimal in **the abstract problem.**
Definition 4.1. Let α : S → Se **be a mapping between two c-semirings. We**
say α preserves optimal solutions if Opt(P) ⊆ Opt(α(P**)) holds for any SCSP** P **over** S.

The following order-reflecting property plays a key role.

Definition 4.2. Let (C, ⊑) and (A, ≤) be two posets. A mapping α : **C → A** is said to be *order-reflecting* if

$\sqsubseteq b$. 
(∀a, b ∈ C) α(a) < α(b) ⇒ a ⊏ b (4)
In the remainder of this section we show that α **preserves optimal solutions**
if and only if α **is an order-reflecting semiring homomorphism. To this end, we** need several lemmas.

Recall that + is idempotent and monotonic on ≤S **for any c-semiring** S =
hS, +, ×, 0, 1i**. The following lemma then identifies a necessary and sufficient**
condition for α **preserving optimal solutions.**
Lemma 4.1. Let α be a mapping from c-semiring S to c-semiring Se *such that* α(0) = 0e, α(1) = 1e. Then α *preserves optimal solutions for all constraint* systems if and only if the following condition holds for any two positive integers m, n:

$$\sum\nolimits_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(u_{ij})<_{\widetilde{S}}\widetilde{\sum}_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(v_{ij})\Rightarrow\sum\limits_{i=1}^{n}\prod\limits_{j=1}^{m}u_{ij}<_{S}\sum\limits_{i=1}^{n}\prod\limits_{j=1}^{m}v_{ij}.\tag{5}$$

Proof. Suppose that α **satisfies the above Equation 5. Given an SCSP** P =
hC, coni over S **with** C = {ci}
m i=1 and ci = hdefi, conii. Take a tuple t **that is**
optimal in P. We now show t **is also optimal in** α(P).

Set con = con ∪
Sm k=1 conk. Take T (t) = {t
′: t
′| con con = t}**. Set** n = |T (t)| and write T (t) = {ti: 1 ≤ i ≤ n}. For each 1 ≤ i ≤ n and each 1 ≤ j ≤ m**, set** uij = cj (ti| con conj
). Then

$$\operatorname{and}$$
$$u=Sol(P)(t)=\sum_{t_{i}\in T(t)}\prod_{j=1}^{m}c_{j}(t_{i}|_{\mathsf{con}_{j}}^{\mathrm{con}})=\sum_{i=1}^{n}\prod_{j=1}^{m}u_{i j},$$  $$\widetilde{u}=Sol(\alpha(P))(t)=\widetilde{\sum}_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(u_{i j}).$$

Suppose t is not optimal in α(P). Then there exists some t¯ **that has value**
v > e Se ue in α(P). Notice that T (t**¯) =** {t
′: t
′| con con = t¯} **also has** n = |T (t)|