lp-method.tex 6 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 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 \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 based on it's neighborhood. Instead, swapping between three pixels as seen below leads to every pixel containing 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}; \path[every node/.style={font=\sffamily\small}] (1) edge[left] node [above] {$b$} (2) (2) edge[left] node [above] {$c$} (3) (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 Apr 21, 2022 44 45 46 47 48 49 50 If we allowed swapping between neighboring pixels this would indeed be tricky. If instead we restrict ourselves to only swapping between non-neighboring pixels however, then the score function changes only linearly and we can use linear programming to find the optimal swap. Concretely, we setup the following linear program. Let $P$  Michael Keller committed Apr 22, 2022 51 be a set of $n$ non-neighboring pixels. Every pixel  Michael Keller committed Apr 21, 2022 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 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 based on the pixels neighborhood to plant that crop 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*} Then we are trying to maximize the function: \begin{displaymath} \text{maximize } c^T x \end{displaymath} subject to the constraints that: \begin{enumerate} \item We don't allow less than $0$ or more than $1$ of each crop to be planted in a pixel \item Every Pixel must contain a total amount of crops equaling $1$ \item The amount of each crop we are redistributing must stay the same \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 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 150 151 152 In theory an optimal solution to this linear program could result in fractional amounts of crop being planted in a pixel. However, the following theorem demonstrates that there is always an optimal integer solution. \begin{theorem} The linear program for finding the optimal swap between non neighboring pixels (described above) always has an optimal integer solution. \end{theorem} \begin{proof} The essence of our proof is that we first show that when we remap $k$ crops between $k$ pixels there must exist an integer solution, because then we are in a Birkhoff polytope. Then we will generalize the $k$ crop to $k$ pixels remapping to a $m$ crop to $k$ pixels remapping. 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. In this case our solution space is the Birkhoff polytope. 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*} In order for a solution to be valid every row 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 Birkhoff polytope. Because the vertices of the Birkhoff polytope are the permutation matrices, 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. What when the number of crop types is smaller then the number of involved pixels? Even then the linear program must have an optimal integer solution. TODO: finish proof \end{proof}  Michael Keller committed Apr 21, 2022 153 154 \section{Method}  Michael Keller committed Apr 22, 2022 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 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: \begin{algorithm} \caption{Random LP Iteration Algorithm} \begin{algorithmic} \State $i \gets 0$ \State $x_0 \gets \text{Random initial valid field}$ \While{$i \leq \text{Max Iterations}$} \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}