helpers.tex 17.4 KB
 Michael Keller committed Apr 20, 2022 1 2 3 4 \chapter{Helpful Statements} \section{Growing solutions} Michael Keller committed May 14, 2022 5 6 7 8 9 10 11 12 13 14 We have seen that the general problem is NP complete. However, small problems can still be computed by simply testing out all possible solutions. We aim to demonstrate that we can build solutions for larger fields with the same score to field size ratio. These solutions may not be optimal, but in some situations may lead to good quality results quickly. For the sake of a clearer presentation Michael Keller committed May 15, 2022 15 we demonstrate a method that stretches the Michael Keller committed May 14, 2022 16 17 18 19 20 21 22 23 24 25 26 27 solution by the same factor in both the $x$ and $y$ direction. Consider an algorithm that is given a small optimal solution $sol$ of size $X \times Y$ that we would like to stretch by an odd factor of $f$. We propose the following method for generating a larger solution $sol'$. We use $0$ indexing for cleaner formulas: \begin{align*} sol'_{i, j} &= sol_{a, b} & & i \in \{0, \dots, f \cdot (X-1)\} & j \in \{0, \dots, f \cdot (Y-1)\} \end{align*} \begin{displaymath} Michael Keller committed May 15, 2022 28 f \in \{ 2i + 1 \ | \ i \in \N \} Michael Keller committed May 14, 2022 29 30 \end{displaymath} \begin{displaymath} Michael Keller committed May 15, 2022 31 a = \lfloor i / f \rfloor + ((i + \lfloor i / f \rfloor) \text{ mod } 2) \quad \quad b = \lfloor j / f \rfloor + ((j + \lfloor j / f \rfloor) \text{ mod } 2) Michael Keller committed May 14, 2022 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 \end{displaymath} which is a bit puzzling in its formal form. The idea is that we want to multiply the connections for all non-border pixels the same amount of time. To achieve this we try to reuse all of the good intercrop relationships that are hopefully present in the small field. We essentially "ping pong" between all of the connections $f$ times. Here is an example for $f = 3$: \begin{displaymath} \begin{bmatrix} 1 & 2 & 3\\ 4 & 5 & 6\\ 7 & 8 & 9\\ \end{bmatrix} \to \begin{bmatrix} 1 & 2 & 1 & 2 & 3 & 2 & 3\\ 4 & 5 & 4 & 5 & 6 & 5 & 6\\ 1 & 2 & 1 & 2 & 3 & 2 & 3\\ 4 & 5 & 4 & 5 & 6 & 5 & 6\\ 7 & 8 & 7 & 8 & 9 & 8 & 9\\ 4 & 5 & 4 & 5 & 6 & 5 & 6\\ 7 & 8 & 7 & 8 & 9 & 8 & 9\\ \end{bmatrix} \end{displaymath} Here the only non-border pixel is pixel $5$. In the small solution it is connected to all other pixels exactly once. The reader is invited to verify that pixel $5$ in the grown solution is connected to every other pixel exactly $f^2 = 9$ times. Next we introduce the concept of relative score. We define it as: \begin{displaymath} \text{Relative Score} := \frac{\text{score}}{\text{maximum possible score}} \end{displaymath} where for the maximum possible score we use the standard bound discussed in the section on bounds. Hence if the score for our small field is $s$ then the relative score is: \begin{displaymath} \frac{s}{8XY - 6X - 6Y + 4} \end{displaymath} Michael Keller committed May 15, 2022 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 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 We are now able to formulate the following theorem: \begin{theorem} For any solution to a field there exists a factor by which we can scale up the field such that the relative score doesn't worsen and we only slightly violate the distribution constraint. \end{theorem} \begin{proof} We first bound the score for the grown field $s'$ from below: \begin{align*} s' &\geq f^2 \cdot s - 2 \cdot 3 \cdot (f \cdot (X-1) + 1) - 2 \cdot 3 \cdot (f \cdot (Y-1) + 1) + 4\\ &\geq f^2 \cdot s - 6 \cdot (f \cdot X - f + 1) - 6 \cdot (f \cdot Y - f + 1) + 4\\ &\geq f^2 \cdot s - 6f \cdot X + 6f - 6 - 6f \cdot Y + 6f - 6 + 4\\ &\geq f^2 \cdot s - 6f \cdot (X + Y - 2) -8\\ &\geq f^2 \cdot s - 6f \cdot (X + Y) \end{align*} which means our new relative score can be bounded from below by: \begin{align*} &\frac{s'}{8 \cdot (f (X-1) + 1) \cdot (f (Y-1) + 1) - 6 \cdot (f (X-1) + 1) - 6 \cdot (f (Y-1) + 1) + 4}\\ &= \frac{s'}{8 \cdot (f X - f + 1) \cdot (f Y - f + 1) - 6 \cdot (f X - f + 1) - 6 \cdot (f Y - f + 1) + 4}\\ &= \frac{s'}{8f^2XY - 8f^2X - 8f^2Y + 2fX + 2fY - 4f + 8f^2}\\ &= \frac{s'}{8f^2XY - 8f^2X - 8f^2Y + 2f \cdot (X + Y - 2) + 8f^2}\\ &= \frac{s'}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)}\\ &\geq \frac{f^2 \cdot s - 6f \cdot (X + Y)}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)} \end{align*} Which in turn allows us to find the following condition on $f$ that guarantees our property: \begin{align*} \frac{s}{8XY - 6X - 6Y + 4} &\leq \frac{f^2 \cdot s - 6f \cdot (X + Y)}{8f^2 (XY - X - Y + 1) + 2f \cdot (X + Y - 2)}\\ \frac{s}{8XY - 6X - 6Y + 4} &\leq \frac{f \cdot s - 6 \cdot (X + Y)}{8f (XY - X - Y + 1) + 2 \cdot (X + Y - 2)}\\ - 2fsX - 2fsY + 4fs + 2s \cdot (X + Y - 2) &\leq - 6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)\\ f \cdot 2s \cdot (X + Y - 2) - 2s \cdot (X + Y - 2) &\geq 6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)\\ f &\geq \frac{6 \cdot (X + Y) \cdot (8XY - 6X - 6Y + 4)}{2s \cdot (X + Y - 2)} + 1 \end{align*} which means if $f$ is at least what we bound it by here the relative score will not worsen. Lastly we consider that we slightly violate the distribution constraint for the crops that are planted in pixels on the border. Concretely every crop planted in a corner would need to be planted: \begin{displaymath} f^2 - (f-1)^2 = 2f - 1 \end{displaymath} more times and crops planted in other places on the border would need to be planted $f$ more times. It should be stated that this would also require the grown field to be made even larger to accommodate the extra plants. It is worth noting however that the violation in the problem constraints is only linear, while in general the total number of planted pixels grows quadratically. Hence it is somewhat reasonable to ignore these violation on fields that are grown by very large factors in order to receive the guarantee of not worsening the relational score. \end{proof} Michael Keller committed May 14, 2022 150 151 Michael Keller committed Apr 20, 2022 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 \section{Creating integer solutions from fractional solutions} If we were able to take a field that can contain multiple crops in a pixel and transform it into a solution of the same quality where every pixel contains exactly one crop, this would enable us to try additional standard optimization techniques. Of course the field with fractional amounts of crops in pixels has to meet the distribution requirement of the pixel farming problem as well as only contain positive or $0$ amounts of planted crop in a pixel. \subsection{The standard method} First we introduce a method that has good results on large fields and requires no conditions of $R$. \begin{theorem} Michael Keller committed Apr 27, 2022 171 \label{makeInt1} Michael Keller committed Apr 20, 2022 172 173 174 175 176 177 178 179 180 181 A fractional pixel farming solution can be transformed to a fractional solution with at least the same score where up to $4 \cdot \binom{C}{2}$ pixels are still fractional. All other pixels contain only one crop. \end{theorem} \begin{proof} The key insight for this statement is that the score function changes linearly when swapping Michael Keller committed May 15, 2022 182 crops between non-neighboring pixels. Imagine Michael Keller committed Apr 20, 2022 183 184 185 186 187 two non-neighboring pixels that both contain the crops $c_1$ and $c_2$: \FloatBarrier \begin{figure}[h] \centering Michael Keller committed Apr 21, 2022 188 \begin{tikzpicture}[->,>=stealth',auto,node distance=3cm,thick,main node/.style={rectangle,draw,font=\sffamily\Large}] Michael Keller committed Apr 20, 2022 189 190 191 192 193 \node[main node] (1) {U}; \node[main node] (2) [right of=1] {V}; \path[every node/.style={font=\sffamily\small}] Michael Keller committed May 15, 2022 194 (1) edge[bend left] node [above] {$\lambda \cdot c_1$} (2) Michael Keller committed Apr 20, 2022 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 (2) edge[bend left] node [below] {$\lambda \cdot c_2$} (1); \end{tikzpicture} \end{figure} \FloatBarrier Because the neighborhoods remain constant, the shift function above changes the score linearly. This means there is always a direction in which we can swap crops without making the score worse. We perform the swap until at least one of the two pixels is unable to continue with swapping (i.e. runs out of crop to give to the other pixel). Therefore, every time we swap like this, we eliminate at least one crop from at least one fractional pixel. Michael Keller committed May 15, 2022 210 211 212 Next we argue that it is not necessary to swap between neighboring pixels for this result. Consider the field Michael Keller committed Apr 20, 2022 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 below. If we only swap between pixels that have the same color, then we never have to swap between neighboring pixels. It is always possible to color a rectangle field in this fashion with $4$ colors. \FloatBarrier \begin{figure}[h] \centering \begin{tikzpicture}[x=1cm] \foreach \x in {0,...,3} \foreach \y in {0,...,3} { \pgfmathparse{mod(\x+\y,2) ? (mod(\x,2) ? "red" : "green") : (mod(\x,2) ? "blue" : "gray")} \edef\colour{\pgfmathresult} \path[fill=\colour] (\x,\y) rectangle ++ (1,1); } \draw (0,0)--(0,4)--(4,4)--(4,0)--cycle; \end{tikzpicture} \end{figure} \FloatBarrier Michael Keller committed May 15, 2022 232 233 234 Further, we argue that iterating this method terminates. While pixels of the same color that both contain the same two crops exist, we perform the swap as outlined above. Eventually, Michael Keller committed Apr 20, 2022 235 236 237 238 239 240 241 242 243 244 because we get rid of at least one fractional crop every time we swap, we must reach a state for a pixel color where no two pixels contain two of the same crop. Because only a finite amount of fractional crops can exist in a field, we must terminate in finite time. A state where no two pixels contain the same crop means in the worst case there are up to $\binom{C}{2}$ pixels that each contain two crops. All other pixels must now contain exactly one unit of one crop. Because Michael Keller committed May 15, 2022 245 there are four colors among which we swap, Michael Keller committed Apr 20, 2022 246 247 248 249 250 251 252 253 254 255 in the worst case we end up with $4 \cdot \binom{C}{2}$ pixels that are still fractional. \end{proof} \subsection{The advanced method} There might be situations where up to $4 \cdot \binom{C}{2}$ still fractional pixels are unacceptable. This might be the case in relatively small fields with relatively large amounts Michael Keller committed May 15, 2022 256 of different crops. Here the following, slightly stronger, Michael Keller committed Apr 21, 2022 257 statement with a condition on $R$ might be helpful: Michael Keller committed Apr 20, 2022 258 259 \begin{theorem} Michael Keller committed Apr 27, 2022 260 \label{makeInt2} Michael Keller committed Apr 20, 2022 261 262 263 264 265 266 267 268 269 270 271 272 273 If every crop prefers all other crops over itself, then a fractional pixel farming solution can be transformed to a fractional solution with at least the same score where up to $\binom{C}{2}$ pixels are still fractional. All other pixels contain only one crop. \end{theorem} \begin{proof} The general proof strategy is the same as with the previous theorem. The change we make is that we allow swapping of crops between neighboring pixels. Michael Keller committed Apr 21, 2022 274 Michael Keller committed May 15, 2022 275 We now need to know what condition must be Michael Keller committed Apr 21, 2022 276 277 278 met to ensure that swapping in either direction even among neighboring pixels is never detrimental. Michael Keller committed May 09, 2022 279 Let us consider the change in the score function $\Delta S$ Michael Keller committed May 09, 2022 280 when swapping $c_\alpha, c_\beta \in \Cps$ between Michael Keller committed May 09, 2022 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 two neighboring pixels $u$ and $v$. Because the score change generated with the neighboring set $N(u) \cup N(v) \setminus \{u, v\}$ (the gray pixels in the sketch below) is linear, as these neighboring pixels stay constant, we will ignore them for now. \FloatBarrier \begin{figure}[h] \centering \begin{tikzpicture}[->,>=stealth',auto,node distance=10mm,thick,main node/.style={rectangle,draw,font=\sffamily\Large}] \node[main node] (1) {U}; \node[main node] (2) [right of=1] {V}; \node[main node, fill=black!20,] (3) [below of=1] {N}; \node[main node, fill=black!20,] (4) [right of=3] {N}; \node[main node, fill=black!20,] (5) [right of=4] {N}; \node[main node, fill=black!20,] (6) [above of=5] {N}; \node[main node, fill=black!20,] (7) [above of=6] {N}; \node[main node, fill=black!20,] (8) [left of=7] {N}; \node[main node, fill=black!20,] (9) [left of=8] {N}; \node[main node, fill=black!20,] (10) [left of=9] {N}; \node[main node, fill=black!20,] (11) [below of=10] {N}; \node[main node, fill=black!20,] (12) [below of=11] {N}; Michael Keller committed May 15, 2022 303 304 \path[every node/.style={font=\sffamily\small}] (1) edge[bend left] node [above] {$c_\alpha$} (2) Michael Keller committed May 09, 2022 305 306 307 308 309 (2) edge[bend left] node [below] {$c_\beta$} (1); \end{tikzpicture} \end{figure} \FloatBarrier The interesting score change is the following quadratic one Michael Keller committed May 09, 2022 310 311 312 313 314 between the pixels $u$ and $v$. Here $p_c$ denotes the amount of crop $c$ pixel $p$ contains before the swap. $p_c'$ is defined analogously for after the swap. Michael Keller committed May 09, 2022 315 \begin{align*} Michael Keller committed May 09, 2022 316 317 318 319 320 321 322 323 324 325 326 327 328 &\sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &= \sum_{c_i \in \{c_\alpha, c_\beta \}} \sum_{c_j \in \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \{c_\alpha, c_\beta \}} \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}} \sum_{c_j \in \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}} \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ Michael Keller committed May 09, 2022 329 \end{align*} Michael Keller committed May 15, 2022 330 We can now utilize that: Michael Keller committed May 09, 2022 331 \begin{align*} Michael Keller committed May 09, 2022 332 333 u'_\alpha &= u_\alpha - \lambda & v'_\alpha &= v_\alpha + \lambda\\ u'_\beta &= u_\beta + \lambda & v'_\beta &= v_\beta - \lambda\\ Michael Keller committed May 09, 2022 334 \end{align*} Michael Keller committed May 15, 2022 335 which gives us: Michael Keller committed May 09, 2022 336 \begin{align*} Michael Keller committed May 09, 2022 337 338 339 340 341 342 343 344 345 346 347 348 349 &\sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &= \sum_{c_i \in \{c_\alpha, c_\beta \}} \sum_{c_j \in \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \{c_\alpha, c_\beta \}} \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}} \sum_{c_j \in \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u_i \cdot v'_{j} - u_i \cdot v_{j})\\ &+ \sum_{c_i \in \Cps \setminus \{c_\alpha, c_\beta \}} \sum_{c_j \in \Cps \setminus \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u_i \cdot v_{j} - u_i \cdot v_{j}) Michael Keller committed May 09, 2022 350 \end{align*} Michael Keller committed May 15, 2022 351 where the last term is simply $0$ and the second Michael Keller committed May 09, 2022 352 353 and third terms are linear functions in $\lambda$. We again focus only on the quadratic term: Michael Keller committed May 09, 2022 354 \begin{align*} Michael Keller committed May 09, 2022 355 356 357 358 359 360 361 362 363 364 365 &\sum_{c_i \in \{c_\alpha, c_\beta \}} \sum_{c_j \in \{c_\alpha, c_\beta \}} R(c_i, c_j) \cdot (u'_i \cdot v'_{j} - u_i \cdot v_{j})\\ &= R(c_\alpha, c_\alpha) \cdot (u'_\alpha \cdot v'_{\alpha} - u_\alpha \cdot v_{\alpha})\\ &+ R(c_\alpha, c_\beta) \cdot (u'_\alpha \cdot v'_{\beta} - u_\alpha \cdot v_{\beta})\\ &+ R(c_\beta, c_\alpha) \cdot (u'_\beta \cdot v'_{\alpha} - u_\beta \cdot v_{\alpha})\\ &+ R(c_\beta, c_\beta) \cdot (u'_\beta \cdot v'_{\beta} - u_\beta \cdot v_{\beta})\\ &= R(c_\alpha, c_\alpha) \cdot ((u_\alpha - \lambda) \cdot (v_\alpha + \lambda)- u_\alpha \cdot v_{\alpha})\\ &+ R(c_\alpha, c_\beta) \cdot ((u_\alpha - \lambda) \cdot (v_\beta - \lambda) - u_\alpha \cdot v_{\beta})\\ &+ R(c_\beta, c_\alpha) \cdot ((u_\beta + \lambda) \cdot (v_\alpha + \lambda) - u_\beta \cdot v_{\alpha})\\ &+ R(c_\beta, c_\beta) \cdot ((u_\beta + \lambda) \cdot (v_\beta - \lambda) - u_\beta \cdot v_{\beta})\\ Michael Keller committed May 09, 2022 366 &= R(c_\alpha, c_\alpha) \cdot (u_\alpha \cdot \lambda - v_\alpha \cdot \lambda - \lambda^2)\\ Michael Keller committed May 09, 2022 367 &- R(c_\alpha, c_\beta) \cdot (u_\alpha \cdot \lambda + v_\beta \cdot \lambda - \lambda^2)\\ Michael Keller committed May 09, 2022 368 &+ R(c_\beta, c_\alpha) \cdot (u_\beta \cdot \lambda + v_\alpha \cdot \lambda + \lambda^2)\\ Michael Keller committed May 09, 2022 369 370 371 372 373 374 &- R(c_\beta, c_\beta) \cdot (u_\beta \cdot \lambda - v_\beta \cdot \lambda + \lambda^2)\\ &= \lambda^2 \cdot \left ( R(c_\alpha, c_\beta) + R(c_\beta, c_\alpha) - R(c_\alpha, c_\alpha) - R(c_\beta, c_\beta) \right )\\ &+ \lambda \cdot (R(c_\alpha, c_\alpha) - R(c_\alpha, c_\beta)) \cdot u_\alpha\\ &+ \lambda \cdot (R(c_\beta, c_\alpha) - R(c_\beta, c_\beta)) \cdot u_\beta\\ &+ \lambda \cdot (R(c_\beta, c_\alpha) - R(c_\alpha, c_\alpha)) \cdot v_\alpha\\ &+ \lambda \cdot (R(c_\beta, c_\beta) - R(c_\alpha, c_\beta)) \cdot v_\beta Michael Keller committed May 09, 2022 375 \end{align*} Michael Keller committed May 09, 2022 376 Of special note here is the quadratic term. Michael Keller committed May 15, 2022 377 If every crop likes all the other crops Michael Keller committed May 09, 2022 378 379 380 381 382 383 384 at least as much as it likes itself, then the quadratic term is positive. The quadratic term being positive means we can always swap in at least one direction without the score getting worse. The optimal swap direction is determined by all of the linear functions in $\lambda$ we put to the side Michael Keller committed May 15, 2022 385 throughout this proof. Therefore, Michael Keller committed May 09, 2022 386 387 388 389 390 391 392 393 a relationship function $R$ fulfilling $R(c_i, c_j) \geq R(c_i, c_i)$ ensures there is always a good way to swap crops among neighboring pixels. Being allowed to swap even amongst neighboring pixels allows us to disregard the pattern structure we had for the standard swapping method Michael Keller committed May 15, 2022 394 395 396 397 and we can, by the same reasoning, conclude that this new method has at most $\binom{C}{2}$ still fractional pixels after terminating. Michael Keller committed Apr 20, 2022 398 \end{proof}