problem-statement.tex

\chapter{Problem Statement}

\section{Integer Version}

We are given four inputs:
\begin{enumerate}
    \item The field dimensions, denoted as $X$ for the number of pixels
    on the x-axis and $Y$ correspondingly. Both $X, Y \in \N$.
    \item The types of crop we would like to plant. We let
    $C\in \N$ denote the number of different crop types we would
    like to plant and $\Cps := \{c_1, \cdots, c_{C}\}$
    as the set of all crops.
    \item A function $R: \Cps^2 \to [-1, 1]$ that measures the
    synergy between two crops. The higher the value of
    $R(c_a, c_b)$, the more crop $c_a$ likes $c_b$.
    \item A probability distribution $D$ over our crops $\Cps$
    that tells us how many pixels of the field should
    contain a certain crop. $D$ should satisfy
    $D(c) \cdot X \cdot Y \in \N \quad \forall c \in \Cps$.
\end{enumerate}
Further let us define a neighborhood function that gives
us all the neighboring pixels of a given pixel:
\begin{displaymath}
    N((x, y)) = \{(a, b) \in \N^2 \ | \ a < X \land b < Y \land \abs{a - x} \leq 1 \land  \abs{b - y} \leq 1 \land (a, b) \neq (x, y) \}
\end{displaymath}
and we are looking for a matrix $F \in \Cps^{X \times Y}$
that maximizes the following score function:
\begin{displaymath}
    S(F, R) = \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} \sum_{n \in N((i, j))} R(F_{(i, j)}, F_n)
\end{displaymath}
where we also fulfill the distribution constraint:
\begin{align*}
    I((i, j), c) &= \begin{cases}
        1 & F_{(i, j)} = c\\
        0 & otherwise.
    \end{cases}\\
    \forall c \in \Cps : D(c) \cdot X \cdot Y &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} I((i, j), c)
\end{align*}

\section{Fractional Version}

We define the fractional version of pixel farming
analogously to the integer version
with the following exception: Instead of searching
for a Field $F \in \Cps^{X \times Y}$, we search for
an $F' \in \R_+^{C \times X \times Y}$. The idea
is that every pixel can contain not only a single
crop, but any combination of crops. To this end,
we introduce $C$ variables for every pixel to denote
the amount of each crop a pixel contains. For example,
a pixel could contain half of a carrot, a quarter
of an onion, and a quarter of broccoli.

We stress that we are interested in this version
of the pixel farming problem not for its practical
applications but rather because it enables us to
utilize more traditional methods for exploring
large search spaces.

We define an analogous score function:
\begin{align*}
    S(F', R) &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} \sum_{n \in N((i, j))} \sum_{c_i \in \Cps} \sum_{c_j \in \Cps} R(c_i, c_j) \cdot F_{(i, j)}^{c_i} \cdot F_{n}^{c_j}
\end{align*}
and solutions must fulfill a similar distribution constraint:
\begin{align*}
    \forall c \in \Cps : D(c) \cdot X \cdot Y &= \sum_{i = 0}^{X-1} \sum_{j = 0}^{Y-1} F_{(i, j)}^c
\end{align*}