January 3, 2022
Open Jupyter notebook on Github
The following discussion is excerpted and adapted from my final project for MATH 87 at Tufts University, which was primarily based on a problem from the 2000 Mathematical Contest in Modeling hosted by the Consortium for Mathematics and its Applications (COMAP).
The essence of the problem and its constraints are the following: Consider an array of hexagonal cells, each containing a wireless transmission tower at its center. Each tower must be assigned exactly one integer-numbered frequency (or channel, interchangeably). If a side of a hexagonal cell has length $s$, then the assigned channels of towers within $2s$ of each other must differ by two or more. Towers within $4s$ of each other may not have the same assigned channel; the channels must differ by one or more. Variant problems include varying the minimum acceptable difference of channels, $k$, for towers within $2s$, and considering a disorganized set of towers that does not conform to a hexagonal mesh.
Figure 1: Example large hexagonal tower array
To minimize the span of a set of channel assignments, we seek to minimize the value of the maximum of the assigned channels, subject to the two sets of channel interference constraints, and using only positive integer valued channels. If the channel value of the $i^{th}$ of $t$ transmission towers is $c_i$, the optimization problem can be written as:
$$ \begin{align} \operatorname{min}\ f(c) &= max(c_1, c_2, \ldots, c_i, \ldots, c_t) \quad \text{s.t.}\\ (c_i-c_j)^2 &\geq 1^2\\ (c_i-c_k)^2 &\geq 2^2\\ c_i &\geq 1 \end{align} $$
The objective function $(1)$ constitutes a minimax objective. That is, we seek to minimize the maximum of the set of $c_i$ variables. One approach is to define a proxy variable $z$ and write additional constraints of the form $z \geq c_i$ for all $c_i$ variables. The channel distance constraints are analogous to physical or Cartesian distances. The constraint $(2)$ requires the channels for towers $i$ and $j$ that are within $4s$ distance of each other to differ by at least 1. Similarly, the constraint $(3)$ requires the channels for towers $i$ and $k$ that are within $2s$ to differ by at least 2. These constraints are called non-convex constraints because for a given $c_i$, there are multiple non-overlapping feasible regions for $c_j$. In combination with the objective function, we are left with a moderately difficult non-linear optimization problem. We can adapt an equivalent linear program instead.
The non-linear program described in system $(1-4)$ can be re-formulated as a linear program of the form:
$$ \begin{align} \operatorname{min}\ \mathbf{c}\cdot\mathbf{x} & \quad \text{s.t.} \\ \mathbf{A_{4s}}\cdot\mathbf{x} &\leq \begin{bmatrix}1 & \ldots & 1\end{bmatrix} \\ \mathbf{A_{2s}}\cdot\mathbf{x} &\leq \begin{bmatrix}1 & \ldots & 1\end{bmatrix} \\ \mathbf{A_{eq}}\cdot\mathbf{x} &= \begin{bmatrix}1 & \ldots & 1\end{bmatrix} \\ \mathbf{x} &\geq 0 \ \text{and} \ \mathbf{x} \leq 1 \end{align} $$
The variable vector $\mathbf{x}$ will have dimension equal to the product of the number of towers $t$ and available channels $k$. Conceptualize $\mathbf{x}$ as being assembled from $k$ smaller $t$-dimensional vectors. The entries of $\mathbf{x}$ should take binary values $\{0,1\}$ in $\mathbf{x^*}$ representing the optimal channel assignment. A channel is either assigned to a tower, or it is not. The sub-vector $\mathbf{x_i}$ represents the set of binary labels indicating which towers are assigned with channel $i$.
$$ \begin{aligned} \mathbf{x} &= \begin{bmatrix} \mathbf{x_1} & \mathbf{x_2} & \ldots & \mathbf{x_i} & \ldots & \mathbf{x_{k-1}} & \mathbf{x_k} \end{bmatrix}^T \quad \text{and} \\ \mathbf{x_i} &= \begin{bmatrix} x_i^{1} & x_i^{2} & \ldots & x_i^{j} & \ldots & x_i^{t-1} & x_i^{t} \end{bmatrix}^T \end{aligned} $$
To minimize the span, we need an objective function that takes a greater value with a single tower assigned to channel $i$ than when all towers can be assigned channels less than $i$. For $t$ towers and $k$ available channels, one possibility is:
$$ \begin{aligned} f(x) &= (t+1)^0 x_1^1 + (t+1)^0 x_1^2 + \ldots + (t+1)^0 x_1^{t-1} + (t+1)^0 x_1^{t} \\ &+ (t+1)^1 x_2^1 + (t+1)^1 x_2^2 + \ldots + (t+1)^1 x_2^{t-1}+ (t+1)^1 x_2^{t} \\ &\quad \vdots \\ &+ (t+1)^{k-1} x_k^1 + (t+1)^{k-1} x_k^2 + \ldots + (t+1)^{k-1} x_k^{t-1}+ (t+1)^{k-1} x_k^{t} \end{aligned} $$
Consider an example with 3 towers and 5 channels available (this is the minimum). $t=3$ and $k=5$. Recall that $x_i^j$ is the binary label for the $i^{th}$ channel at the $j^{th}$ tower.