lp-method.tex 3.28 KB
Newer Older
1
2
\chapter{The Linear Programming Method}

Michael Keller's avatar
Michael Keller committed
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