← back home

# Under the Hood

The wig-solver chrome extension communicates with the  wig-solver API to find optimal solutions to your scheduling problems. This API, at its core, is just a program that solves set-cover-like problems, by converting them to binary integer linear programming problems and then calling scipy's milp functionality. Here's how that translation works.

### Representing the problem mathematically

Once your When Is Good poll is finished, you have a finite set $P$ of respondents and a finite set $T$ of proposed times, with an "availability relation" $R \subseteq P \times T$ (which is the data provided by your respondents). For our purposes, it will be better to think of this in a different way: each time $t \in T$ can be identified with the subset $\{p \in P : p R t\}$.

That is, the we have a set $P$ of respondents, and a set $T \subseteq 2^P$ of proposed times, where each proposed time is identified with the set of respondents who are available at that time. Then the problem of finding a minimal set of times which accommodate everyone can be phrased as

Find a set $X \subseteq T$ of minimal cardinality such that $\bigcup X = P$.

This is exactly a set-cover problem! So we can solve this in the usual way, by interpreting it as a binary integer linear programming problem.

### Linear programming

Let $P = \{p_1, \dots, p_n\}$ and $T = \{t_1, \dots, t_m\}$. We will have binary integer variables $x_1, \dots, x_m$, where each $x_i$ represents whether or not to include $t_i$ in the set $X$ ($0$ if $t_i$ should not be included and $1$ if it should). Then we wish to

Minimize $\sum_{i=1}^m x_i$ subject to
\begin{aligned}x_i \in \{0,1\} &\quad \forall i \in \{1, \dots, m\} \\ \sum_{\substack{i=1 \\ p_j \in t_i}}^m x_i \geq 1 &\quad \forall j \in \{1, \dots, n\}\end{aligned}

The objective function (which we try to minimize) is just the number of sets that we include in $X$. The first constraint schema specifies that each set is either included or not (i.e. that each variable is a binary integer), and the second constraint schema specifies that each element of $P$ is included in at least one of the elements of $X$ (i.e. that $\bigcup X = P$). Once our favorite integer linear programming solver find an optimal solution, the set $X$ that we want is just $\{t_i : i \in \{1, \dots, m\}, x_i = 1\}$. Easy enough!

This covers the operation of wig-solver in the most basic case. wig-solver also offers two other solving techniques, which we'll cover next.

### The relaxed program

wig-solver can also find solutions to the problem of "accommodate all but at most $k$ respondents". We modify the linear program from before by adding new binary integer variables $y_1, \dots, y_n$. Each $y_j$ represents whether or not $p_j$ will be included in $\bigcup X$ ($0$ if $p_j$ is included and $1$ if $p_j$ is not included). If $y_j = 1$ for some $j$, i.e. if $p_j$ does not need to appear in $\bigcup X$, then the constraint $\sum_{\substack{i=1 \\ p_j \in t_i}}^m x_i \geq 1$ should be ignored. To accomplish this, we simply replace the constraint by $y_j + \sum_{\substack{i=1 \\ p_j \in t_i}}^m x_i \geq 1$. Then the constraint is automatically satisfied if $y_j = 1$ and equivalent to the old constraint if $y_j = 0$. Finally, we add a new constraint, stating that we want $\bigcup X$ to contain all but at most $k$ of the elements of $P$. This works, but there's one small improvement to be made: we should impose a small penalty to "avoiding" an element, so that if it's possible for $\bigcup X$ to contain more elements without increasing $\lvert X \rvert$, we should prefer that solution. This requires an adjustment to the objective function: instead of minimizing $\sum_{i=1}^m x_i$, we will minimize $\sum_{i=1}^m x_i + \varepsilon \sum_{j=1}^n y_j$ for a very small positive of $\varepsilon$. $\varepsilon$ must be chosen carefully, so that it is never advantageous to use more sets in order to cover fewer elements. The most straightforward choice that works is $\varepsilon = 1/(n+1)$. With that all in place, here's the modified linear program:

Minimize $\sum_{i=1}^m x_i + \frac{1}{n+1} \sum_{j=1}^n y_j$ subject to
\begin{aligned}x_i \in \{0,1\} &\quad \forall i \in \{1, \dots, m\} \\ y_j \in \{0,1\} &\quad \forall i \in \{1, \dots, n\} \\ y_j + \sum_{\substack{i=1 \\ p_j \in t_i}}^m x_i \geq 1 &\quad \forall j \in \{1, \dots, n\} \\ \sum_{j=1}^n y_j \leq k\end{aligned}

### The transposed program

Finally, wig-solver can also find solutions to the problem of "accommodate as many respondents as possible by using at most $k$ times". We modify the original linear program, again adding variables $y_1, \dots, y_n$. This $y_j$ has the opposite meaning to the variable of the same name in the previous section: $y_j = 0$ indicates that $p_j$ is not included in $\bigcup X$ and $y_j = 1$ indicates that $p_j \in \bigcup X$. Then the objective is to maximize $\sum_{j=1}^n y_j$, with the constraint that $\sum_{i=1}^m x_i \leq k$. To impose the correct relationships between the $x_i$'s and $y_j$'s, we leverage the fact that all of these variables are binary integers. Imposing $x_i \leq y_j$ whenever $p_j \in t_i$ forces $y_j = 1$ whenever $x_i = 1$ and $p_j \in t_i$, i.e. whenever the set $t_i$ is used, then $p_j$ is included in $\bigcup X$. Additionally imposing $\sum_{\substack{i = 1 \\ p_j \in t_i}}^m x_i \geq y_j$ forces $y_j = 0$ whenever $x_i = 0$ for all $i$ such that $p_j \in t_i$. In total, this means that each $y_j = 1$ if and only $x_i = 1$ for some $i$ such that $p_j \in t_i$, which is exactly the desired relationship between the $x$'s and $y$'s. Finally, just as before, we should impose a small penalty for using more times than is really necessary. Overall, the linear program looks like this:

Maximize $\frac{-1}{m+1} \sum_{i=1}^m x_i + \sum_{j=1}^n y_j$ subject to
\begin{aligned}x_i \in \{0,1\} &\quad \forall i \in \{1, \dots, m\} \\ - y_j + \sum_{\substack{i=1 \\ p_j \in t_i}}^m x_i \geq 0 &\quad \forall j \in \{1, \dots, n\} \\ y_j - x_i \geq 0 &\quad \forall i \in \{1, \dots, m\} \forall j \in \{1, \dots, n\} \text{ s.t. } p_j \in t_i \\ \sum_{i=1}^m x_i \leq k\end{aligned}

### That's all!

That's really all wig-solver does, at least on the backend. If you have ideas for improvement or want to contribute to wig-solver in some way, issues and pull requests on github are very welcome.