← 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.