
## 5 Computing Concrete Optimal Solutions From Abstract Ones

In the above section, we investigated conditions under which all **optimal solutions of concrete problem can be related** *precisely* **to those of abstract problem.**
There are often situations where it suffices to find *some* **optimal solutions or simply a good approximation of the concrete optimal solutions. This section shows**
that, even without the order-reflecting condition, semiring homomorphism can be used to find some optimal solutions of concrete problem using abstract ones.

Theorem 5.1. Let α : S → Se *be a semiring homomorphism. Given an SCSP*
P over S*, suppose* t ∈ Opt(α(P)) has value v in P and value ev in α(P)*. Then* there exists t¯ ∈ Opt(P) ∩ Opt(α(P)) with value v¯ ≥S v in P *and value* ve in α(P)*. Moreover, we have* α(¯v) = α(v) = ev.

Proof. **Suppose** P = hC, coni, C = {ci}
m i=1 and ci = hdefi, conii**. Set** con =
con ∪
S{conj}
m j=1 and k = |con|. Suppose t **is an optimal solution of** α(P),
with semiring value ve in α(P) and v in P**. By definition of solution, we have**

$$v=S o l(P)(t)=\sum_{t^{\prime}|_{\mathrm{con}}^{\mathrm{cons}}=t\,j=1}^{m}\prod_{\operatorname*{def}_{j}(t^{\prime}|_{\mathrm{con}_{j}})}.$$

Denote
$T(t)=\{t':t\}$
′is a |k|**-tuple with** t

Set n = |T (t)|, and write T = {t1, · · · , tn}. For each 1 ≤ i ≤ n **and each**
1 ≤ j ≤ m**, set** vij = defj (ti|conj
$$t^{\prime}|_{\mathrm{con}}^{\mathrm{con}}=t\}.$$
). Then
$$v=\sum_{i=1}^{n}\prod_{j=1}^{m}v_{i j},\;\;\widetilde{v}=\widetilde{\sum}_{i=1}^{n}\widetilde{\prod}_{j=1}^{m}\alpha(v_{i j}).$$
Since α **preserves sums and products, we have**

$$\alpha(v)=\alpha(\sum_{i=1}^{n}\prod_{j=1}^{m}v_{i j})=\widehat{\sum}_{i=1}^{n}\alpha(\prod_{j=1}^{m}v_{i j})=\widehat{\sum}_{i=1}^{n}\widehat{\prod}_{j=1}^{m}\alpha(v_{i j})=\widehat{v}.$$
$$\mathbf{r}\mathbf{a}$$

Notice that if t is also optimal in P, then we can choose t¯ = t**. Suppose** t is not optimal in P. Then there is a tuple t¯ that is optimal in P**, say with value**
v >S v**. Denote**

T (t**¯) =** {t
′: t
′is a |k|**-tuple with** t
′|
$$\stackrel{\mathrm{ion}}{|\mathrm{con}}={\bar{t}}\}.$$
Clearly |T (t¯)| = |T (t)| = n. Write T (t¯) = {t¯1, · · · ,t¯n}. For each 1 ≤ i ≤ n and each 1 ≤ j ≤ m**, set** uij = defj (t¯i|conj**). Then**

$${\overline{{v}}}=\sum_{i=1}^{n}\prod_{j=1}^{m}u_{i j}.$$
$$11$$
