lp-method.tex 9.41 KB
 Michael Keller committed Apr 20, 2022 1 2 \chapter{The Linear Programming Method}  Michael Keller committed Apr 21, 2022 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 \section{Problem Setup} The core idea with this method is to replace the simple swap between two pixels in the simulated annealing approach with a multi-way swap. Picture the following scenario of three non-neighboring pixels: \FloatBarrier \begin{figure}[h] \centering \begin{tabular}{@{}cccc@{}} \toprule Pixel & Currently Contains & Preferred & Strongly Disliked\\ \midrule W & $a$ & $c$ & $b$ \\ U & $b$ & $a$ & $c$ \\ V & $c$ & $b$ & $a$ \\ \bottomrule \end{tabular} \end{figure} \FloatBarrier Using only swaps involving two pixels will always lead to a pixel containing a crop it strongly dislikes  Michael Keller committed May 15, 2022 23 24 based on its neighborhood. Instead, swapping between three pixels, as seen below, leads to every pixel containing  Michael Keller committed Apr 21, 2022 25 26 27 28 29 30 31 32 33 34 35 their preferred crop: \FloatBarrier \begin{figure}[h] \centering \begin{tikzpicture}[->,>=stealth',auto,node distance=2cm,thick,main node/.style={rectangle,draw,font=\sffamily\Large}] \node[main node] at (-3, 0) (1) {U}; \node (hidden) [right of=1] {}; \node[main node] (2) [right of=hidden] {V}; \node[main node] (3) [above of=hidden] {W};  Michael Keller committed May 15, 2022 36 37 38  \path[every node/.style={font=\sffamily\small}] (1) edge[left] node [above] {$b$} (2) (2) edge[left] node [above] {$c$} (3)  Michael Keller committed Apr 21, 2022 39 40 41 42  (3) edge[right] node [above] {$a$} (1); \end{tikzpicture} \end{figure} \FloatBarrier  Michael Keller committed Apr 22, 2022 43 The question is how we find such a multi-way swap.  Michael Keller committed May 15, 2022 44 If we allowed swapping between neighboring pixels, this would  Michael Keller committed Apr 21, 2022 45 indeed be tricky. If instead we restrict ourselves to only  Michael Keller committed May 15, 2022 46 swapping between non-neighboring pixels, then the score  Michael Keller committed Apr 21, 2022 47 function changes only linearly and we can use linear programming  Michael Keller committed Apr 25, 2022 48 49 to find the optimal swap. Let the following linear program be defined as the swap LP.  Michael Keller committed Apr 21, 2022 50 51  Concretely, we setup the following linear program. Let $P$  Michael Keller committed Apr 22, 2022 52 be a set of $n$ non-neighboring pixels. Every pixel  Michael Keller committed Apr 21, 2022 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 gets $C$ variables that denote how much of each crop is planted within the pixel: \begin{align*} x &= \begin{bmatrix} x_{1, 1} \\ \vdots \\ x_{1, C} \\ \vdots \\ x_{n, C} \end{bmatrix} & & x_{i, j} = \text{Pixel } p_i \text{'s amount of crop } j \end{align*} And the function we are trying to maximize shows for every variable in $x$ how good it would be  Michael Keller committed May 15, 2022 68 based on the pixel's neighborhood to plant that crop  Michael Keller committed Apr 21, 2022 69 70 71 72 73 74 75 76 77 78 79 80 there: \begin{align*} c &= \begin{bmatrix} c_{1, 1} \\ \vdots \\ c_{1, C} \\ \vdots \\ c_{n, C} \end{bmatrix} & & c_{i, j} = \text{Score change for planting } 1 \text{ of crop } j \text{ in pixel } i \end{align*}  Michael Keller committed Apr 25, 2022 81 Then we are trying to maximize the function $c^T x$  Michael Keller committed Apr 21, 2022 82 83 subject to the constraints that: \begin{enumerate}  Michael Keller committed May 15, 2022 84  \item we don't allow less than $0$ or more than $1$ of each crop to  Michael Keller committed Apr 21, 2022 85  be planted in a pixel  Michael Keller committed May 15, 2022 86 87  \item every Pixel must contain a total amount of crops equaling $1$ \item the amount of each crop in $x$ before the swap and  Michael Keller committed Apr 25, 2022 88  in $x^*$ after the swap must be the same  Michael Keller committed Apr 21, 2022 89 90 91 92 93 94 95 96 \end{enumerate} or formally, a solution $x^*$ must satisfy: \begin{align*} 0 \leq x^*_{i, j} &\leq 1\\ \forall p \in P:\quad \sum_{c \in \Cps} x^*_{p, c} &= 1\\ \forall c \in \Cps:\quad \sum_{p \in P} x^*_{p, c} &= \sum_{p \in P} x_{p, c} \end{align*}  Michael Keller committed Apr 22, 2022 97 98 In theory an optimal solution to this linear program could result in fractional amounts of crop being  Michael Keller committed Apr 25, 2022 99 planted in a pixel. However, the following theorems  Michael Keller committed May 15, 2022 100 demonstrate that there is always an optimal integer solution.  Michael Keller committed Apr 22, 2022 101   Michael Keller committed Apr 25, 2022 102 103 104 105 106 107 108 109 110 111 112 First we will show the specific case of swapping $k$ different crops among $k$ non-neighboring pixels, then we will generalize the statement to $m$ different crops amount $k$ different pixels. Let $\F$ denote all valid integer solutions to the LP above, or formally: \begin{displaymath} \F := \{f \ | \ f \in \Z^{n \cdot C} \land f \text{ denotes a valid field}\} \end{displaymath}  Michael Keller committed Apr 22, 2022 113 \begin{theorem}  Michael Keller committed Apr 25, 2022 114 115 116 117  \label{kByKOptSwap} If $x \in \F$, then the solution $x^*$ to the swap LP for $k$ pixels swapping $k$ different crops is also in $\F$.  Michael Keller committed Apr 22, 2022 118 119 120 121 122 \end{theorem} \begin{proof} The essence of our proof is that we first show that when we remap $k$ crops between $k$ pixels  Michael Keller committed May 15, 2022 123 124  an optimal integer solution must exist, because then we are in a Birkhoff Polytope.  Michael Keller committed Apr 22, 2022 125 126 127 128  Consider the case where we select $k$ non-neighboring pixels that all contain a different crop. Then we ask how to best remap these $k$ crops among the $k$ pixels.  Michael Keller committed May 15, 2022 129  In this case our solution space is the Birkhoff Polytope.  Michael Keller committed Apr 22, 2022 130 131 132 133 134 135 136 137 138 139  Consider the following representation of our $x$ as a matrix: \begin{align*} \begin{bmatrix} x_{1, 1} & x_{1, 2} & \dots & x_{1, C}\\ x_{2, 1} & x_{2, 2} & \dots & x_{2, C}\\ \vdots & \vdots & & \vdots\\ x_{n, 1} & x_{n, 2} & \dots & x_{n, C} \end{bmatrix} \end{align*}  Michael Keller committed May 15, 2022 140  In order for a solution to be valid, every row  Michael Keller committed Apr 22, 2022 141 142 143 144  must sum up to $1$ (a pixel contains a total crop amount of $1$) and each column must sum up to $1$ (we only have $1$ of each crop to distribute among the pixels). This is the definition of the  Michael Keller committed May 15, 2022 145 146  Birkhoff Polytope. Because the vertices of the Birkhoff Polytope are the permutation matrices,  Michael Keller committed Apr 22, 2022 147 148 149 150 151 152  these correspond exactly to our integer solutions. Lastly, because the function we are maximizing is linear, we know that at least one optimal solution will be at a vertex. Because there is an optimal solution at a vertex we know to be integer, we know there must be an optimal integer solution.  Michael Keller committed Apr 25, 2022 153 154 155 \end{proof} Next we use this theorem to prove that the LP  Michael Keller committed May 15, 2022 156 for swapping any number of crop types among  Michael Keller committed Apr 25, 2022 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 non-neighboring pixels must result in an integer solution. \begin{theorem} If $x \in \F$, then the solution $x^*$ to the swap LP is also in $\F$. \end{theorem} \begin{proof} We will formulate a swap LP' that must have an optimal integer solution $x^* \in \F$ and demonstrate that $x^*$ can also be translated into an optimal integer solution for our swap LP. We want to use theorem \ref{kByKOptSwap} to show that the swap LP' we are going to construct  Michael Keller committed May 15, 2022 173  has an optimal integer solution. Therefore, we need  Michael Keller committed Apr 25, 2022 174 175 176 177 178 179 180 181 182 183 184  to have the same number of crops as pixels. Consider again a set $P$ of non-neighboring pixels. For any two pixels $p_1, p_2 \in P$ that contain the same crop $c$ in $x$ we introduce a new crop $c'$ that behaves exactly the same with all other crops as $c$ does and replace one of the occurrences of $c$ with $c'$. We iterate this procedure until there are no more of the same two crops. By theorem \ref{kByKOptSwap} it now follows, as we have $k$ distinct crops among $k$ pixels, that  Michael Keller committed May 15, 2022 185 186  an optimal integer solution $x^* \in F$ for the swap LP' must exist.  Michael Keller committed Apr 25, 2022 187 188 189 190 191 192 193 194 195  We now show that 1) this solution can be translated into an integer solution for the swap LP and 2) that this solution is optimal. The first part is trivial. Simply replace the cloned' crops with their originals and we obtain a valid solution for the swap LP.  Michael Keller committed May 15, 2022 196  Next, we show that an optimal solution $x^*$ for  Michael Keller committed Apr 25, 2022 197  the swap LP must be $\leq$ an optimal solution  Michael Keller committed May 15, 2022 198  for the swap LP'. For this we simply iterate through  Michael Keller committed Apr 25, 2022 199 200 201 202 203 204 205  all duplicate crops in $x^*$ and replace them with cloned versions. Now again we have the exact same score, as the cloned crop version behave the same as the originals, but have a valid solution for the swap LP'. Obviously the optimal solution for the swap LP' is bounded from below by this solution $x^*$ for the swap LP.  Michael Keller committed Apr 22, 2022 206   Michael Keller committed May 15, 2022 207  Finally, we show that an optimal solution $x^*$ for  Michael Keller committed Apr 25, 2022 208 209 210 211 212 213  the swap LP' must be $\leq$ an optimal solution for the swap LP. Again, we replace all of the cloned crop versions with their original crop. The score must remain the same. Thus we have bounded the optimal solution for the swap LP from below with the score of $x^*$ for the solution to the swap LP'.  Michael Keller committed Apr 22, 2022 214   Michael Keller committed Apr 25, 2022 215 216 217 218 219 220 221 222  As we have shown both that the optimal solution for swap LP $\leq$ the optimal solution for swap LP' and the optimal solution for swap LP' $\leq$ the optimal solution for swap LP it must follow that the optimal score for both linear programs is the same. Therefore, using the swap LP' we can generate an optimal integer solution for the swap LP.  Michael Keller committed Apr 22, 2022 223 224 \end{proof}  Michael Keller committed Apr 21, 2022 225 226 \section{Method}  Michael Keller committed Apr 22, 2022 227 228 229 Now that we have a way to find the optimal multi-way swap between pixels, how do we use it? We tried the following procedure:  Michael Keller committed Apr 27, 2022 230 \FloatBarrier  Michael Keller committed Apr 22, 2022 231 232 233 234 235 \begin{algorithm} \caption{Random LP Iteration Algorithm} \begin{algorithmic} \State $i \gets 0$ \State $x_0 \gets \text{Random initial valid field}$  Michael Keller committed Apr 27, 2022 236  \While{$i \leq \text{Max Iterations}$ and $x_0$ not converged}  Michael Keller committed Apr 22, 2022 237 238 239 240 241 242 243 244  \State $P \gets \{\text{random set of non-neighboring pixels}\}$ \State $opt \gets solveLP(P, x_0)$ \State $x_0 \gets updateField(opt, x0)$ \State $i \gets i + 1$ \EndWhile\\ \Return $x_0$ \end{algorithmic} \end{algorithm}  Michael Keller committed Apr 27, 2022 245 246 \FloatBarrier After running this algorithm repeatedly for around 24h  Michael Keller committed May 15, 2022 247 on a standard laptop we were able to generate the  Michael Keller committed May 15, 2022 248 249 250 251 252 253 254 255 256 257 258 259 260 261 following solutions for our benchmark problems: \FloatBarrier \begin{figure}[h] \centering \begin{tabular}{@{}cccc@{}} \toprule Dataset & Best known bound & Arnold score & LP Method\\ \midrule 1 & $950$ & $635$ & $658$\\ 2 & $1624$ & TODO & TODO\\ \bottomrule \end{tabular} \end{figure} \FloatBarrier which are a slight improvement over the previous best scores.`