lp-method.tex 6 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
\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's avatar
Michael Keller committed
43
The question is how we find such a multi-way swap.
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
51
be a set of $n$ non-neighboring pixels. Every pixel
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
153
154
\section{Method}

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