1 \documentclass[a4paper, 10pt, pagesize, smallheadings]{article}
3 %\usepackage[latin1]{inputenc}
4 \usepackage{amsmath, amsthm, amssymb}
7 \usepackage{algorithmic}
12 \usepackage{tikz-qtree}
13 \usetikzlibrary{decorations.pathmorphing} % noisy shapes
14 \usetikzlibrary{fit} % fitting shapes to coordinates
15 \usetikzlibrary{backgrounds} % drawin
16 \usetikzlibrary{shapes,snakes}
17 \addtolength{\voffset}{-20pt}
18 \title{CSP Exercise 03 Solution}
20 \renewcommand{\familydefault}{\sfdefault}
21 \newcommand{\E}{\mathcal{E}}
22 \newcommand{\R}{\mathcal{R}}
24 %\include{pythonlisting}
30 \section*{Exercise 3.1}
31 The minimal network is $N_0 = \langle (v_1,v_2,v_3),(\{2,3\},\{1,2,3,4\},\{1,3,4\}),\{<_{(v_1,v_2)},<_{(v_1,v_3)},=_{(v_2,v_3)}\} \rangle$.
33 \section*{Exercise 3.2}
34 (a) The network for the puzzle is \emph{(we do not name the variables consecutively to keep a clear connection to the original puzzle fields)}
36 N = \langle (v_1,v_2,v_3,v_8),(\{ATOLL\},\{TOLL,HEAT\},\{EAT\},\{TOLL,HEAT\}),\{R_{v_1,v_2,v_8},R_{v_2,v_3},R_{v_3,v_8}\} \rangle
40 R_{v_1,v_2,v_8} &= \{(ATOLL,HEAT,TOLL)\}\\
41 R_{v_2,v_3} &= \{(HEAT,EAT)\}\\
42 R_{v_3,v_8} &= \{(EAT,TOLL)\}
47 \tikzstyle{var}=[circle,
50 \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
51 \matrix[row sep=0.2cm,column sep=0.5cm] {
52 & \node(v1)[var]{$v_1$}; & &\\
53 \node(v2)[var]{$v_2$}; & \node(v3)[var]{$v_3$}; & \node(v8)[var]{$v_8$};\\
62 \caption{(3.2b) primal constraint graph of $N$}
67 \tikzstyle{var}=[ellipse,
70 \begin{tikzpicture}[>=latex,text height=1.5ex,text depth=0.25ex]
71 \matrix[row sep=0.2cm,column sep=0.5cm] {
72 & \node(v1v2v8)[var]{$v_1,v_2,v_8$};\\
73 \node(v2v3)[var]{$v_2,v_3$}; & &\node(v3v8)[var]{$v_3,v_8$};\\
76 (v1v2v8) edge node[auto=right]{$v_2$} (v2v3)
77 (v1v2v8) edge node[auto=left]{$v_8$} (v3v8)
78 (v2v3) edge node[auto=left]{$v_3$} (v3v8)
81 \caption{(3.2c) dual constraint graph of $N$}
84 \section*{Exercise 3.3}
85 There are more trivial examples with the required properties and it would be easier to prove the properties on them in a formal way. However, we tried to find an example, which works for all three parts of this exercise with minimal modifications. We traded off formal proofs for intuitive understanding of the underlying differences between these relations.\\\\
86 (a) Let $R_S$ be the relation with $S=(x_1,...,x_n)$ for the constraint $x_1 > \sum_{i=2}^{n}x_i$ over the domains $D_i = \{0,1,2\}$, i.e., $R_S = \{(1,0,...,0)\} \cup \{(2,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < 2\}$ or more graphically $R_S = \{(1,0,...,0),$ $(2,0,...,0,1,0,...,0),(2,1,0,...,0), (2,0,...,0,1)\}$.
88 The projection network of $R_S$ is by definition $Proj(R_S) = \langle S, D_i = \pi_{x_i}(R_S), R_{x_i,x_j}' = \pi_{x_i,x_j}(R_S)\rangle$ with $R'_{x_1,x_j} = \{(1,0),(2,0),(2,1)\}$ and for $i \neq 1$ holds $R'_{x_i,x_j}=\{(0,0),(0,1),(1,0)\}$.
90 The limited domains impose transitive relations $x_1 > x_i$ for all $1 < i \leq n$ and $x_i = x_j = 0 \lor x_i \neq x_j$ for $i \neq 1$. Since this imposed relations essentially reduce the contraint to the mentioned binary relations $R'$ it follows that all solutions of the projection network are also in the relation, i.e., $Sol(Proj(R_S)) = R_S$.
92 All projections of $R_S$ to a subset of $S$, so that $x_1$ is contained, basically reduces the network to the projection size, all properties remain unchanged, therefore the projection network of the projection of $R_S$ has only solutions which are in the projected relation (and vice versa).
94 All projections of $R_S$ to a subset of $S$ without $x_1$ mean a reduction to the constraint $2 > \sum_{i=1}^{m}x_i$ where $m$ is the projection size. This has obviously also a binary representation with $R'_{x_i,x_j} = \{(0,0),(1,0),(0,1)\}$. Again it follows that the projection network of this projection has only solutions which are in the projected relation (and vice versa).
96 Given that the relation $R_S$ itself and all its possible projections have binary representations, it holds that $R_S$ is binary decomposable. \qed\\\\
97 (c) We will do part (c) before (b) because here we use the same constraint as in part (a). However, we will expand the domains with $D_i = \{0,1,2,3\}$. This gives us the relation $R_S = \{(x_1,(x_i)_{1<i\leq n}) \mid \sum_{i=2}^{n}x_i < x_1\}$.
99 This relation has no binary representation, because no set of binary relations can enforce the constraint for $x_1 = 3$. E.g. $(3,1,1,1,0,...,0)$ is a solution of $Proj(R_S)$, because it is consistent with the constraints $R'_{x_1,x_j}=\{(1,0),(2,0),(2,1),(3,0),(3,1),(3,2)\}$ and for $i\neq 1$ $R'_{x_i,x_j}=\{(0,0),(1,0),(0,1),(1,1),(2,0)\}$ while it is not contained in $R_S$. It follows that $R_S \subseteq Sol(Proj(R_S))$ and $R_S \neq Sol(Proj(R_S))$.
101 We could have shown the same effect by leaving the domains untouched, but changing the constraint to $x_1 \geq \sum_{i=2}^nx_i$ instead, which has the same effect, it requires a systematic (here ternary) view over all variables. \qed\\\\
102 (b) This time we modify the relation like this
103 \[R_S=\{(x_1,(x_i)_{1<i\leq\frac{n-1}{2}},(x_j)_{\frac{n-1}{2}<j\leq n}) \mid \sum_{i=2}^{\frac{n-1}{2}}x_i < x_1 < \sum_{j=\frac{n-1}{2}+1}^{n}x_j\}\]
104 with domains $D_i=\{0,1,2\}$ again.
106 This modification does not change the property of the relation to have a binary representation, because solutions to the binary constraints are exactly the variable assignments from the relation (again due to the transitive relations over $x_1$).
108 However, if we use a projection without $x_1$, we lose our pivot variable for the otherwise separted sets of variables. Solutions to such a projection network induced by the projected relation without $x_1$ will again lack the systematic view over the separated sets of variables and their sums, which yields possible solutions which are inconsistent with the projected relation. From this follows that our modified $R_S$ has a binary representation but is not binary decomposable. \qed\\\\