lp-method.tex 3.28 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 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 \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 However, the question is how we find such a multi-way swap. 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$ be a set on non-neighboring pixels. Every pixel 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*} \section{Method} Now that we have an understanding of the