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.
Perfoming hill climbing: Find a “neighbor scheduling” of the given scheduling (by moving a single event to another slot, if possible) and solve the assignment again. Repeat this until the solution of the neighbor scheduling is worse than the one before (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}\) (which means that a choice \(w\) was scheduled to slot \(\mathcal{S}(w)\) in a given scheduling). 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 forumla 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 of the choices one of the slots available. Given a scheduling \(\mathcal{S}\), \(\mathcal{S}(c)=s\) means that the choice \(c\) was assigned to the slot \(s\). 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:
The sum of the minima and maxima of all choices in a 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 constraints that are present in 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.
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 resultion 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 choosen freely and affects which solutions are favored over others. It can be thought of as the “fairness paramter”. 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)\).
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)=\varphi_p(w)^\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 due to the flow integrality theorem, the resulting optimal flow is guaranteed to have integer flow values for every edge.
Furthermore, because how we defined our edge costs, the total cost of the flow is also the minor score \(F_\min((\mathcal{S}, \mathcal{A}))\) of the resulting solution.
4.4.3.2 Handling inter-edge constraints
To model many kinds of additional assignment constraints one may want the solution to adhere to, we need to expand the standard model of a minimum-cost flow problem by what we from here on call the set of edge implications \(I\subseteq E^2\) that have the following semantics: \[ (u,v)\in I \Leftrightarrow f(u)\leq f(v) \] So, if \((u,v)\in I\), a flow of \(f(u)=1\) implies a flow of \(f(v)=1\) on the other edge.
Because such a modified network \(N=(V,E,I,z,c,a)\) is not a regular minimu-cost flow instance when \(I\neq\emptyset\) and we have to make sure that the flow we are computing still is integer, we are going to translate the network into an mixed integer programming instance (where each edge is a variable and constraints are based on flow conservation in flow networks) and solve it using a general MIP solver instead.
4.4.3.3 Implication graph
Because we gave to make sure that the flow we are calculating still consists of integer values when \(I\) is not empty, we have to declare some variables in our MIP problem as integer variables. The naive approach to this would be to simply make every variable an integer variable, but because integer variables are the main hurdle for finding solutions to an MIP problem fast, we generally want to minimize the number of integer variables we have to introduce.
To find out which variables we need to make integer we can view the pair \((E, I)\) as a directed graph (called the implication graph). Note that the edges of the flow network (or equivalently the variables of the respective MIP instance) are the vertices of the implication graph and every implication is a directed edge. To avoid confusion, we will from now on call the vertices of the implication graph \(variables\) and the edges \(implications\).
We then can calculate which variables we need to declare as integer variables so that the whole optimal flow stays integer in a two-step process.
The first step becomes obvious if we observe that all variables in a strongly connected components (abbreviated as SCC) of the implication graph have to have the same value (proof). This means that for every SCC, we have to make one arbitrary variable in the SCC an integer variable in order for every variable in the SCC to become integer too. Let the set of these variables be \(D_1\).
The second step is based on the observation that for an implication \((u,v)\), it is sufficient that either \(v\) or \(w\) are integer variables (because then the implication becomes a normal integer constraint in each subproblem inside the branch-and-cut process of the MIP solver which does not violate the prerequisites of the integrality theorem). To use this fact, we just have to look at the remaining implication graph \((E', I')\) where we removed
- all variables (and incident implications) that were part of a SCC (because we already have “dealt” with them in the first step) and in turn
- all variables with degree zero, because they either
- are not affected by any implications to begin with or
- they were adjacent to one or more SCCs in the original implication graph (so such particular variable \(v\) is only affected by some implications \(v\leq w\) or \(v\geq w\) where \(w\) is already guaranteed to be integer).
We then calculate a dominating set \(D_2\) of \((E', I')\). Because finding the minimal dominating set is an NP-hard problem we can resort to a simple greedy algorithm.
This whole process gives us a set of variables \(D=D_1\cup D_2\) that we have to declare as integer variables in order for the optimal flow to be also integer.
4.4.3.4 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 perform first-choice hill climbing by first finding any valid scheduling \(S\) (using the scheduling solving algorithm as described above) and then modifying this scheduling by moving a single event to a different slot (we call this scheduling a neighbor of \(S\)) until we can not find any neighbors of \(S\) that has a better solution than \(S\) itself.
Because the number of neighbors can be very large (and solving the assignment is quite expensive), we limit the number of neighbors that get considered as the next step.
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.