4 Inner workings of wassign
4.1 Overview
The algorithm is based on shotgun hill climbing. More details about each step are found under the respective section:
Perform Critical Set Analysis: This step is optional (and is only performed at the very beginning), but the results of the critical set analysis are used in the scheduling as well as the assignment solver to drastically decrease the time it takes for good solutions to be found.
Solving the scheduling: Find a possible scheduling using a randomized depth-first search.
Solving the assignment: Find the best possible assignment for the given scheduling by constructing a corresponding linear optimization or (depending on the given extra constraints) mixed integer programming problem instance and solving it using an MIP solver.
Performing hill climbing: Find a “neighbor scheduling” of the given scheduling (by moving a single choice to another slot or by applying a randomized swap perturbation) and solve the assignment again. Repeat this until no explored neighbor improves the current solution (this is the hill climbing part).
Performing shotgun hill climbing: Do the above again and again until the timeout is reached (this is the shotgun part). The best solution found by then is the output of the program.
4.2 Some notation and a word on preferences
4.2.1 Common notation used throughout this section
This part of the manual is rather theory-heavy, so we have to introduce some common notation that is used from here onwards:
4.2.1.1 Notation regarding the input
\(\mathbb{S}\), \(\mathbb{W}\) and \(\mathbb{P}\) are the non-empty sets of slots, choices and choosers respectively.
\(\min(w)\in\mathbb{N}\) and \(\max(w)\in\mathbb{N}\) are the minimum and maximum number of choosers of a choice \(w\in\mathbb{W}\). Generally, \(0<\min(w)\leq\max(w)\).
\(\varphi_p(w)\in\mathbb{N}\) is the preference given by a chooser \(p\in\mathbb{P}\) to the choice \(w\). We oftentimes use \(\varphi_p=\left[\varphi_p(w_1), \varphi_p(w_2), ..., \varphi_p(w_{|\mathbb{W}|})\right]\) as an abbreviation for the “preference vector” of chooser \(p\) (with respect to an “obvious” ordering of \(\mathbb{W}=\left\{w_1,...,w_{|\mathbb{W}|}\right\}\)).
\(\Phi\) is the set of all preferences that are given by at least one chooser to at least one choice, so \[\Phi=\bigcup_{p\in\mathbb{P}}\left\{\varphi_p(w)\mid w\in\mathbb{W}\right\}\text{ .}\]
4.2.1.2 Notation regarding the solutions
A scheduling (generally called \(\mathcal{S}\)) is a mapping \(\mathcal{S}:\mathbb{W}\to\mathbb{S}\cup\{\bot\}\) where \(\mathcal{S}(w)=\bot\) means that the optional choice \(w\) is not scheduled. More on that in the the respective section.
An assignment (generally called \(\mathcal{A}\)) is a mapping \(\mathcal{A}:\mathbb{P}\times\mathbb{S}\to\mathbb{W}\) (which means that a chooser \(p\) was assigned to the choice \(\mathcal{A}(p, s)\) in slot \(s\)). More on that in the respective section.
A solution (generally \(\mathcal{L}\)) is a pair \(\mathcal{L}=(\mathcal{S}_\mathcal{L},\mathcal{A}_\mathcal{L})\) of a scheduling and an assignment (that is based on \(\mathcal{S}_\mathcal{L}\)). We call \(\mathbb{L}\) the set of all solutions.
\(\varphi_\max(\mathcal{L})\) is the maximum preference that a chooser \(c\) has given to a choice \(w\) where \(c\) was assigned to \(w\). It is defined as \[\varphi_\max(\mathcal{L})=\max\left\{\varphi_p(w)|p\in\mathbb{P},w\in\mathbb{W}\wedge \exists s\in\mathbb{S}:\mathcal{A}_\mathcal{L}(p,s)=w\right\}\text{ .}\]
A \(\varphi\)-solution is a solution \(\mathcal{L}\) with \(\varphi_\max(\mathcal{L})=\varphi\).
4.2.2 Preferences are mirrored
It is very important to note that throughout this section, preferences are “mirrored”, meaning a lower preference given by a chooser to a choice means that the chooser “likes” the choice more. This is because
- The formula used to score solutions does not work the other way around, and therefore
- the program also handles preferences this way (they are converted after the input is read).
So, for example, if a chooser has the preferences \[100, 50, 0, 70, 30, 22\] given in the input, they will be converted to \[0, 50, 100, 30, 70, 78\] assuming that 100 is the maximum preference given in the whole input.
4.3 Solving schedulings
4.3.1 The problem
When we want to compute a scheduling, we want to assign each choice either one of the slots available or leave it unscheduled if it is optional. Given a scheduling \(\mathcal{S}\), \(\mathcal{S}(c)=s\) means that the choice \(c\) was assigned to the slot \(s\), while \(\mathcal{S}(c)=\bot\) means that it is omitted entirely. We also define \(\mathcal{S}^{-1}(s)=\left\{w\mid \mathcal{S}(w)=s\right\}\) as the inverse scheduling (the set of all choices that are scheduled to be in slot \(s\)).
This scheduling \(\mathcal{S}\) has to adhere to some rules because we want to also calculate an assignment based on the scheduling:
For every slot, the sum of the minima and maxima of the choices scheduled into that slot have to allow for the number of choosers, so \[\sum_{w\in\mathcal{S}^{-1}(s)}\min(w) \,\leq \,|\mathbb{P}|\, \leq \sum_{w\in\mathcal{S}^{-1}(s)}\max(w)\] has to hold for each slot \(s\), because else it would be impossible to assign every chooser to a choice in a slot where this constraint is violated.
Additional scheduling constraints from the input have to be satisfied.
Ideally, we also want to get schedulings that allow for a better assignment solution. We use critical set analysis as a heuristic for this.
Because of the first requirement (sum of minima and maxima), this problem is NP-hard (proof).
4.3.2 Algorithm
Fortunately, despite the problem being NP-hard, it generally isn’t hard at all to find valid schedulings for real-world input data.
Because of this, valid schedulings are generated using a randomized (meaning solutions are visited in a semi-randomized order) depth-first backtracking search. A single backtracking step consists of deciding the slot of a single choice; for optional choices, the solver may also leave the choice unscheduled.
There are multiple heuristics at play to improve the performance of the scheduling solver.
Heuristic for choice order: The order in which choices are handled by the solver is determined by the number of scheduling constraints that apply to the single choices. Choices with the most constraints are handled first. Apart from that, the order of choices is random.
Heuristic for set order: Given the current partial solution \(\mathcal{S}_p\), which slots are tried first in the backtracking is determined by \(\sum_{w\in\mathcal{S}^{-1}_p(s)}\max(w)\) (so basically by how “full” the slot \(s\) already is in terms of choice maxima). Slots with a lower value are tried first.
Critical set analysis: Critical set analysis is used by trying to satisfy all critical sets for a set preference level \(p\) until a timeout is reached. If the timeout is reached without finding a valid solution, \(p\) is raised to the next level (so all critical sets with a preference of \(p\) are discarded), and the process is repeated until a solution is found.
4.4 Solving assignments
4.4.1 The problem
When we want to compute an assignment \(\mathcal{A}\) based on a given scheduling \(\mathcal{S}\), we want to assign each chooser to exactly one choice per slot (so for every pair of a slot \(s\) and a chooser \(p\), there is exactly one choice \(\mathcal{A}(s, p)\)).
We also want the resulting solution \(\mathcal{L}=(\mathcal{S}, \mathcal{A})\) to be the “best” one for the given scheduling, but we first have to define a metric for how “good” a solution is in order to be able to compare it to other solutions.
4.4.2 Solution scoring
We define a scoring function \(F:\mathbb{L}\to\mathbb{R}^2\) as follows
\[F(\mathcal{L})=\left(\varphi_\max(\mathcal{L}), \sum_{s\in\mathbb{S},p\in\mathbb{P}} \varphi_p\left(\mathcal{A}_\mathcal{L}(s,p)\right)^{\gamma}\right)\]
where \(\gamma\in\mathbb{R}^+\) is the so-called preference exponent that can be chosen freely and affects which solutions are favored over others. It can be thought of as the “fairness parameter”. For more information on this parameter see the respective section in the manual.
We use this function to assign a score to each solution, where lower scores (defined by the usual order relation \(<\) over \(\mathbb{R}^2\)) are assigned to “better” solutions.
Note that we have a scoring function with two components, the first one being \(\varphi_\max(\mathcal{L})\). This means that a solution \(\mathcal{L}_1\) is always “better” than a solution \(\mathcal{L}_2\) if \(\varphi_\max(\mathcal{L}_1)<\varphi_\max(\mathcal{L}_2)\).
We may also look at the two components of the scoring function separately. We then call them the major and minor term \(F_\textrm{maj}\) and \(F_\min\) of \(F\), so \(F(\mathcal{L})=\left(F_\textrm{maj}(\mathcal{L}), F_\min(\mathcal{L})\right)\).
In the Rust implementation, these terms are evaluated in two different places:
- The major term is exactly the maximum mirrored preference that appears in the finished assignment.
- The minor term is the normalized sum of \(\varphi^\gamma\) over the finished assignment.
During assignment solving, however, the flow model uses edge costs of \((\varphi+ 1)^\gamma\) for admissible chooser-to-choice edges. This shifts all feasible edge costs away from zero without changing the ordering of assignments that stay within the same major preference bound.
4.4.3 Algorithm
4.4.3.1 Minimum-cost flow network
We calculate the optimal assignment for a given scheduling by modelling the problem as a minimum-cost flow problem instance like in this example with 2 slots, 3 choices and 4 choosers and a scheduling \(\mathcal{S}^{-1}(s_1)=\{w_1, w_2\}\), \(\mathcal{S}^{-1}(s_2)=\{w_3\}\):
Or more formally: Given a scheduling \(\mathcal{S}\), we can construct a minimum-cost flow network \(N=(V,E,z,c,a)\) with
- \(V=\mathbb{S}\cup\mathbb{W}\cup\left\{q^p_s\mid
p\in\mathbb{P},s\in\mathbb{S}\right\}\) with a supply function
\(z:V\to\mathbb{Z}\) having the
following values:
- \(z\left(q^p_s\right)=1\).
- \(z(w)=-\min(w)\).
- \(z(s)=-|\mathbb{P}|+\sum_{w\in\mathcal{S}^{-1}(s)}\min(w)\).
- \(E=\{(w,s)\mid
\mathcal{S}(w)=s\}\cup\left\{\left(q^p_s, w\right)\mid\mathcal{S}(w)=s
\wedge q\in\mathbb{P}\right\}\) with a capacity function \(c:E\to\mathbb{N}\) and a cost function
\(a:E\to\mathbb{N}\) having the
following values:
- \(c(w,s)=\max(w)-\min(w)\)
- \(a(w,s)=0\).
- \(c(q^p_s, w)=1\).
- \(a(q^p_s, w)=\left(\varphi_p(w)+1\right)^\gamma\).
The optimal flow \(f\) of \(N\) then is also directly the optimal assignment \(\mathcal{A}\) with the following conversion: \[f(q^p_s, w)=1 \Leftrightarrow \mathcal{A}(p, s) = w \text{ .}\] Note that the implementation models this network as an integer linear program and solves it with an MIP backend even in the plain flow case, so integer assignments are enforced directly by the solver model.
Furthermore, because how we defined our edge costs, the total cost of the flow is a monotone proxy for the minor score \(F_\min((\mathcal{S}, \mathcal{A}))\) of the resulting solution inside a fixed major preference limit.
4.4.3.2 Handling additional assignment constraints
The implementation handles additional assignment constraints in two ways:
- Some constraints directly block chooser-to-choice edges before the
model is solved. For example,
chooser("X").choices.contains_not(choice("Y"))removes all corresponding assignment edges. - Equality-style assignment constraints are encoded as edge groups. Each group is controlled by a binary switch variable that forces all grouped edges to act together.
This is used both for chooser-equality constraints and for dependent-choice groups induced by the constraint system. The result is an integer programming model that stays close to the flow formulation while still supporting the extra combinatorial restrictions.
4.4.3.3 Binary search through preference levels
So far, we are only optimizing by the minor score \(F_\min\). In order to find the optimal solution by \(F\), we just do binary search to find the minimum \(F_\textrm{maj}\) for which there exists a solution.
4.5 Critical set analysis
The most important (and most computationally expensive) heuristic used throughout wassign is called critical set analysis. It is computed once at the start of the computation and its result is a set \(\mathbb{C}\) of so called critical sets.
4.5.1 Definition
4.5.1.1 Critical set, CSA, \(\varphi\)-relevant CSA
A critical set \(C\) is a set is a pair \(C=(\varphi_C, W_C)\) with the following properties:
\(\varphi_C\in\Phi\) and \(W_C\subseteq\mathbb{W}\),
There exists a chooser \(p\in\mathbb{P}\) for which \(W_C=\left\{w\mid \varphi_p(w)\leq\varphi_C\right\}\) holds true.
The critical set analysis (in short CSA) \(\mathbb{C}=\left\{C_1, C_2, ..., C_{|\mathbb{C}|}\right\}\) is the set of all critical sets.
We further call \(\mathbb{C}(\varphi)=\left\{C\in\mathbb{C}\mid \varphi_C=\varphi\right\}\) the \(\varphi\)-relevant critical set analysis (\(\varphi\)-relevant CSA).
Example: Given slots \(\mathbb{S}=\{s_1,s_2,s_3\}\), choices \(\mathbb{W}=\{a, b, c, d, e, f\}\) and a single chooser \(\mathbb{P}=\{p\}\) with preferences \(\varphi_p=\left[100, 50, 0, 90, 70, 100\right]\), all valid critical sets would be \[C_1=(100, \{a, b, c, d, e, f\}), \quad C_2=(90, \{b, c, d, e\}),\] \[C_3=(70, \{b, c, e\}), \quad C_4=(50, \{b, c\}), \quad C_5=(0, \{c\})\text{ .}\]
4.5.1.2 Satisfying critical sets
Given a scheduling \(\mathcal{S}\), we call a critical set \(C\) satisfied if \[\bigcup_{w\in C}\left\{\mathcal{S}(w)\right\} = \mathbb{S}\text{ .}\]
Or in plain terms: A critical set is satisfied by a scheduling if, in this scheduling, every slot contains at least one choice in the critical set.
We can then use critical sets as a heuristic for how “good” assignments based on a given scheduling can be: If \(\mathcal{S}\) does not satisfy all critical sets of \(\mathbb{C}(\varphi)\), there can not be a solution based on \(\mathcal{S}\) that has a maximum preference of \(\varphi\) or lower (proof).
4.5.2 Preference bound
A useful piece of information we can immediately get out of the critical sets is a lower bound of the maximum preference a solution can have. We call this bound \(\overline{\varphi}\) the preference bound; it is defined as \[\overline{\varphi}=\min\left\{\varphi_C\mid C\in\mathbb{C}\wedge |C|<|\mathbb{S}|\right\}\text{ .}\] Or in plain words: If a critical set has fewer elements than there are slots in the input, this critical set can not be satisfied by any scheduling, and therefore there can not be any solution with a maximum preference lower than \(\overline{\varphi}\).
4.5.3 Simplifying critical sets
We can eliminate most of the critical sets in a CSA by the following observation: Given two critical sets \(C_1=(\varphi_1, W_1)\) and \(C_2=(\varphi_2, W_2)\), if \(\varphi_1\leq\varphi_2\) and \(W_1\supseteq W_2\) then all schedulings satisfying \(C_1\) also satisfy \(C_2\). We say that \(C_1\) is covered by \(C_2\).
We can therefore discard any critical sets that are already covered by another critical set; we then just have to alter our definition of \(\varphi\)-relevant critical sets to include all critical sets that have the same or greater preference: \[\mathbb{C}(\varphi)=\left\{C\in\mathbb{C}\mid\varphi_C\geq\varphi\right\} \text{ .}\]
Note: If we need \(\mathbb{C}(\varphi)\) e.g. in the scheduling solver, we can also discard all critical sets that are simply superset of another critical set in \(\mathbb{C}(\varphi)\).
4.6 Hill climbing
So far, we only optimize the solution for a given scheduling. In order to find a locally optimal scheduling (and the corresponding optimal assignment), we first find any valid scheduling \(S\) (using the scheduling solving algorithm as described above) and then inspect a bounded set of neighbor schedulings. These neighbors are generated by moving a single choice to another slot and, in the current Rust implementation, also by random swap-style perturbations between multiple choices.
Because the number of neighbors can be very large (and solving the assignment is quite expensive), only a bounded number of feasible neighbors are explored in each iteration. If any explored neighbor improves the score, the best improving neighbor becomes the next current solution; otherwise hill climbing stops at the current local optimum.
4.6.1 Shotgun hill climbing
We now optimize to a local optimum. To find the global optimum (or at least a very good local one), we simply repeat the hill climbing process over and over and choose the best solution found after a certain timeout; this is also called shotgun hill climbing or random-restart hill climbing.
This (very simple) approach has three main advantages over other optimization methods:
- It is very easy to implement,
- It is trivial to parallelize,
- It is quite effective.