lp-method.tex 9.41 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
\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's avatar
Michael Keller committed
23
24
based on its neighborhood. Instead, swapping between
three pixels, as seen below, leads to every pixel containing
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
39
40
41
42
        (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
If we allowed swapping between neighboring pixels, this would
Michael Keller's avatar
Michael Keller committed
45
indeed be tricky. If instead we restrict ourselves to only
Michael Keller's avatar
Michael Keller committed
46
swapping between non-neighboring pixels, then the score
Michael Keller's avatar
Michael Keller committed
47
function changes only linearly and we can use linear programming
Michael Keller's avatar
Michael Keller committed
48
49
to find the optimal swap. Let the following linear program
be defined as the swap LP.
Michael Keller's avatar
Michael Keller committed
50
51

Concretely, we setup the following linear program. Let $P$
Michael Keller's avatar
Michael Keller committed
52
be a set of $n$ non-neighboring pixels. Every pixel
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
68
based on the pixel's neighborhood to plant that crop
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
81
Then we are trying to maximize the function $c^T x$
Michael Keller's avatar
Michael Keller committed
82
83
subject to the constraints that:
\begin{enumerate}
Michael Keller's avatar
Michael Keller committed
84
    \item we don't allow less than $0$ or more than $1$ of each crop to
Michael Keller's avatar
Michael Keller committed
85
    be planted in a pixel
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
88
    in $x^*$ after the swap must be the same
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
97
98
In theory an optimal solution to this linear program
could result in fractional amounts of crop being
Michael Keller's avatar
Michael Keller committed
99
planted in a pixel. However, the following theorems
Michael Keller's avatar
Michael Keller committed
100
demonstrate that there is always an optimal integer solution.
Michael Keller's avatar
Michael Keller committed
101

Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
113
\begin{theorem}
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
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's avatar
Michael Keller committed
123
124
    an optimal integer solution must exist, because
    then we are in a Birkhoff Polytope.
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
129
    In this case our solution space is the Birkhoff Polytope.
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
140
    In order for a solution to be valid, every row
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
145
146
    Birkhoff Polytope. Because the vertices of the
    Birkhoff Polytope are the permutation matrices,
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
153
154
155
\end{proof}

Next we use this theorem to prove that the LP
Michael Keller's avatar
Michael Keller committed
156
for swapping any number of crop types among
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
173
    has an optimal integer solution. Therefore, we need
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
185
186
    an optimal integer solution
    $x^* \in F$ for the swap LP' must exist.
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
196
    Next, we show that an optimal solution $x^*$ for
Michael Keller's avatar
Michael Keller committed
197
    the swap LP must be $\leq$ an optimal solution
Michael Keller's avatar
Michael Keller committed
198
    for the swap LP'. For this we simply iterate through
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
206

Michael Keller's avatar
Michael Keller committed
207
    Finally, we show that an optimal solution $x^*$ for
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
214

Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
223
224
\end{proof}

Michael Keller's avatar
Michael Keller committed
225
226
\section{Method}

Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
230
\FloatBarrier
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
236
        \While{$i \leq \text{Max Iterations}$ and $x_0$ not converged}
Michael Keller's avatar
Michael Keller committed
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's avatar
Michael Keller committed
245
246
\FloatBarrier
After running this algorithm repeatedly for around 24h
Michael Keller's avatar
Michael Keller committed
247
on a standard laptop we were able to generate the
Michael Keller's avatar
Michael Keller committed
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.