bounds.tex 6.89 KB
 Michael Keller committed Apr 21, 2022 1 2 \chapter{Bounds}  Michael Keller committed Apr 27, 2022 3 4 5 6 To gage the effectiveness of our algorithms we want to know how close to the optimal solution we are. For this we present two bounds.  Michael Keller committed Apr 21, 2022 7 8 \section{Basic Bound}  Michael Keller committed Apr 27, 2022 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 For this bound we assume every relationship between neighboring crops has a score of $1$. Then the maximum possible score is: \begin{align*} \text{Pixels with $8$ neighbors} & = (X-2) \cdot (Y-2) \\ \text{Pixels with $5$ neighbors} & = 2 \cdot (X-2) + 2 \cdot (Y-2) = 2X + 2Y - 8 \\ \text{Pixels with $3$ neighbors} & = 4 \\ \text{Maximum possible score} & = 8 \cdot (X-2) \cdot (Y-2) + 5 \cdot (2X + 2Y - 8) + 3 \cdot 4 \\ & = 8XY - 16X - 16Y + 32 + 10X + 10Y - 40 + 12 \\ & = 8XY -6X -6Y + 4 \end{align*} which for our benchmark $15 \times 15$ field results in an upper bound of $1624$.  Michael Keller committed May 15, 2022 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 % \section{Gärtner Bound} % TODO: This is wrong? If a pixel has a negative % neighborhood the border leads to us underestimating. % Think of $R(c_1, c_2) = -1$. % The basic bound is rather optimistic. If % our $R$ function assigns no two crops % the value of $1$ the basic bound still assumes % it will. Instead we can take the $R$ function % into account when calculating a bound. Consider the % following $3 \times 3$ subfield: % \FloatBarrier % \begin{figure}[h] % \centering % \begin{tikzpicture}[auto,node distance=1cm,thick,main node/.style={circle,draw,font=\sffamily\Large}] % \node[main node] (1) {}; % \node[main node] (2) [right of=1] {}; % \node[main node] (3) [right of=2] {}; % \node[main node] (4) [below of=1]{}; % \node[main node] (5) [right of=4] {}; % \node[main node] (6) [right of=5] {}; % \node[main node] (7) [below of=4] {}; % \node[main node] (8) [right of=7] {}; % \node[main node] (9) [right of=8] {}; % \path[every node/.style={font=\sffamily\small}] (1) edge[red] (2); % \path[every node/.style={font=\sffamily\small}] (2) edge[red] (3); % \path[every node/.style={font=\sffamily\small}] (4) edge[red] (5); % \path[every node/.style={font=\sffamily\small}] (5) edge[red] (6); % \path[every node/.style={font=\sffamily\small}] (7) edge[red] (8); % \path[every node/.style={font=\sffamily\small}] (8) edge[red] (9); % \path[every node/.style={font=\sffamily\small}] (1) edge[red] (4); % \path[every node/.style={font=\sffamily\small}] (4) edge[red] (7); % \path[every node/.style={font=\sffamily\small}] (2) edge[red] (5); % \path[every node/.style={font=\sffamily\small}] (5) edge[red] (8); % \path[every node/.style={font=\sffamily\small}] (3) edge[red] (6); % \path[every node/.style={font=\sffamily\small}] (6) edge[red] (9); % \path[every node/.style={font=\sffamily\small}] (1) edge[blue] (5); % \path[every node/.style={font=\sffamily\small}] (4) edge[blue] (2); % \path[every node/.style={font=\sffamily\small}] (2) edge[blue] (6); % \path[every node/.style={font=\sffamily\small}] (5) edge[blue] (3); % \path[every node/.style={font=\sffamily\small}] (4) edge[blue] (8); % \path[every node/.style={font=\sffamily\small}] (7) edge[blue] (5); % \path[every node/.style={font=\sffamily\small}] (5) edge[blue] (9); % \path[every node/.style={font=\sffamily\small}] (8) edge[blue] (6); % \end{tikzpicture} % \end{figure} % \FloatBarrier % where every vertex represents a pixel and edges represent % neighborhood relationships. Red edges are non-diagonal neighborhood % relationships, while blue edges are diagonal relationships. % Using exhaustive search we can find for each crop % an optimal solution where that crop is in the center % of the subfield above. Then we multiply the value % of all of the red edges with $\frac{1}{6}$ and that % of the blue edges with $\frac{1}{4}$. Then let % $b(c)$ denote the sum of all of the now multiplied % edges in the $3 \times 3$ field for crop $c$. % The optimal score is then bounded by the number % of pixels that are of this crop type multiplied by % $b(c)$. % \begin{displaymath} % \sum_{c \in \Cps} X \cdot Y \cdot D(c) \cdot b(x) % \end{displaymath} % The multipliers are chosen to ensure that all % edges/ crop relationships are counted. A red edge % could be counted by up to $6$ pixels, while a blue % edge could be counted by up to $4$. When they are % not counted $6$ respectively $4$ times, it is because % they no longer represent valid relationships % within our field. % This bound therefore takes into account that there % might be crop types that just do not have good % local neighborhood solutions. We do however count % some non-existant relationships over the field % border, but this may be offset by the other gains % the bound brings. This bound therefore performs well % for pixel farming problems that don't have solutions % with high scores relative to their field size. % Our first benchmark problem is bounded here by % .... while our second problem is bounded by  Michael Keller committed Apr 27, 2022 115 116 117 118  \section{LP bound} We can also use the solution to the  Michael Keller committed May 15, 2022 119 following linear program as a bound.  Michael Keller committed Apr 27, 2022 120 121 The variables are all of the possible crop pairings:  Michael Keller committed Apr 27, 2022 122 123 124 125 126 127 128 129 \begin{align*} x &= \begin{bmatrix} x_{1, 1}\\ x_{1, 2}\\ \vdots\\ x_{1, C}\\ x_{2, 2}\\ \vdots\\  Michael Keller committed Apr 27, 2022 130  x_{C, C}  Michael Keller committed Apr 27, 2022 131 132  \end{bmatrix} &  Michael Keller committed Apr 27, 2022 133  x_{i, j} &= \text{How much of crop } c_i \text{ is planted next to } c_j \text{ in the field}  Michael Keller committed Apr 27, 2022 134 135 136 137 138 139 140 141 142 143 144 \end{align*} where the objective function is the sum of the relationship function for both involved crops the variable has: \begin{align*} c &= \begin{bmatrix} R(c_1, c_1) + R(c_1, c_1)\\ R(c_1, c_2) + R(c_2, c_1)\\ \vdots\\ R(c_1, c_C) + R(c_C, c_1)\\ R(c_2, c_2) + R(c_2, c_2)\\ \vdots\\  Michael Keller committed Apr 27, 2022 145  R(c_{C}, c_C) + R(c_C, c_{C})  Michael Keller committed Apr 27, 2022 146 147 148 149 150 151 152 153  \end{bmatrix} \end{align*} and we are trying to maximize $c^T \cdot x$ under the constraints that we use the correct number of total relationships between pixels: \begin{align*} \sum_{x_i \in x} 2 \cdot x_i = \text{Basic Bound} \end{align*}  Michael Keller committed May 15, 2022 154 as well as that we do not plant too much of a  Michael Keller committed Apr 27, 2022 155 156 specific crop. Here we simply enforce an upper bound on the number of possible connections a crop could have:  Michael Keller committed Apr 27, 2022 157 \begin{align*}  Michael Keller committed Apr 27, 2022 158 159 160 161 162 163  \mathcal{A}_c = \{ x_{i, j} \|\ x_{i, j} \in x \land \left( i = c \lor j = c \right) \}\\ \forall c \in \{1, \dots, C\} \quad \sum_{a \in \mathcal{A}_c} a \leq 8 \cdot X \cdot Y \cdot D(c_c) \end{align*} As an optimal solution for a pixel farming problem meets these constraints, this is a valid bound. It should be noted that this bound does not enforce any constraints  Michael Keller committed May 15, 2022 164 on the shape of the field or that this score  Michael Keller committed Apr 27, 2022 165 166 167 is achievable with only one field (and not multiple disjoint fields).  Michael Keller committed May 15, 2022 168 The bound for the first benchmark problem is $950$ and for  Michael Keller committed May 15, 2022 169 the second benchmark problem $1624$.