{"id":349,"date":"2021-03-05T23:08:00","date_gmt":"2021-03-05T23:08:00","guid":{"rendered":"http:\/\/rainforestqa.com\/discrete-optimization-for-on-call-scheduling\/"},"modified":"2023-02-15T00:08:15","modified_gmt":"2023-02-15T00:08:15","slug":"discrete-optimization-for-on-call-scheduling","status":"publish","type":"post","link":"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling","title":{"rendered":"Discrete optimization for on-call scheduling"},"content":{"rendered":"\n<p>The engineering team of <a id=\"\" href=\"https:\/\/www.rainforestqa.com\/\">RainforestQA (YC S12)<\/a> is remote and distributed around the globe, with developers in America, Europe, and Asia. We\u2019re using PagerDuty to assign developers on-call and for contacting\/escalating people in case of incidents.<\/p>\n\n\n\n<p>Our working hours cover almost all time-zones, about 22 hours from full time-zone coverage. Yet for distributing our on-call schedule, we were unhappy with PagerDuty\u2019s standard daily rotation. For a distributed team, why does somebody need to be on-call at night when other team members are working right now?<\/p>\n\n\n\n<p><a id=\"\" href=\"https:\/\/community.pagerduty.com\/forum\/t\/follow-the-sun-schedules\/284\" target=\"_blank\" rel=\"noopener\">Follow the sun scheduling from PagerDuty<\/a> which is their solution for distributed teams didn\u2019t work for us because it assumes you can group people by blocks of time that don\u2019t overlap. This didn\u2019t work for us because we have many people with many different working times.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_83 counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<div class=\"ez-toc-title-container\">\n<p class=\"ez-toc-title\" style=\"cursor:inherit\">Contents<\/p>\n<span class=\"ez-toc-title-toggle\"><a href=\"#\" class=\"ez-toc-pull-right ez-toc-btn ez-toc-btn-xs ez-toc-btn-default ez-toc-toggle\" aria-label=\"Toggle Table of Content\"><span class=\"ez-toc-js-icon-con\"><span class=\"\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #999;color:#999\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #999;color:#999\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/span><\/a><\/span><\/div>\n<nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#The_Tyrant\" >The Tyrant<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#What_is_Discrete_Optimization\" >What is Discrete Optimization<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#Building_our_first_on-call_schedule_model\" >Building our first on-call schedule model<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#Working_with_optional_variable\" >Working with optional variable<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#Choosing_a_solver\" >Choosing a solver<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-6\" href=\"https:\/\/www.rainforestqa.com\/blog\/discrete-optimization-for-on-call-scheduling\/#Learning_materials\" >Learning materials<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"The_Tyrant\"><\/span>The Tyrant<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>In 2017 we started an internal project called Tyrant to <strong id=\"\">automatically solve this problem of fairly managing on-call scheduling across time-zones<\/strong>.<\/p>\n\n\n\n<p>Originally the project was developed in Ruby with a few\u00a0<code>for<\/code>\u00a0loops and a bunch of\u00a0<code>if<\/code>\u00a0statements. But it didn\u2019t distribute on-call time fairly, it was hard to update the algorithm, and it wasn\u2019t flexible enough. Also, we were interested in applying discrete optimization in production for much harder problems and so we decided to start deploying discrete optimization to our on-call scheduling problem first so we could learn more.<\/p>\n\n\n\n<p>Finally, in 2019 during a hackathon session in Kuala Lumpur we created the latest version of Tyrant which used discrete optimization.<\/p>\n\n\n\n<p>Tyrant runs as a cron job every Saturday. It gets the working hour preferences of the developers, builds the on-call schedules, pushes them to PagerDuty, then emails the schedule to everyone.<\/p>\n\n\n\n<p>This blog post is an introduction to discrete optimization for building the kind of on-call schedule we needed.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/uploads-ssl.webflow.com\/60da68c37e5767dfb65004c0\/61f1d6d74c1e96481497439b_schedule_after-min.png\" alt=\"\"\/><\/figure>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"What_is_Discrete_Optimization\"><\/span>What is Discrete Optimization<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Discrete optimization is the selection of a best element (answer) with regard to some criterion, and where some of the variables are restricted to be discrete (the number of permitted values is either finite or countably infinite).<\/p>\n\n\n\n<p>I had used discrete optimization in hobby projects and for programming challenges. But for a long time I couldn\u2019t find a use case at work; every time I had a project that was solvable through discrete optimization the naive algorithms were better because they got a good enough result faster and without the complexity of adding a discrete optimization system.<\/p>\n\n\n\n<p>Tyrant is a completely different story. As it creates the schedule only once per week, speed isn\u2019t important &#8211; the quality of the result is.<\/p>\n\n\n\n<p>Tyrant\u2019s core is implemented in <a id=\"\" href=\"https:\/\/www.minizinc.org\/\" target=\"_blank\" rel=\"noopener\">MiniZinc<\/a>. MiniZinc is a high-level modelling language and compiler. MiniZinc compiles into FlatZinc, a low-level language that is understood by a wide range of discrete optimization solvers. For us it means faster development, self-explanatory model, and ability to switch solvers.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Introduction to MiniZinc<\/h3>\n\n\n\n<p>Let\u2019s explore a simple problem to familiarize ourselves with the basic MiniZinc syntax. Imagine you run a small car factory named \u201cminiTesla\u201d. You have 100 lithium batteries, and 190000 kilograms of metal. Building a \u201cCybertruck\u201d requires 1 battery and 2500 kg of metal, while building \u201cModel3\u201d requires also 1 battery but only 1500 kg of metal. If you can sell a \u201cCybertruck\u201d for $40k and \u201cModel3\u201d for $35k you\u2019d like to know how many of each vehicle to produce to maximize your profits.<\/p>\n\n\n\n<p><code>profit<\/code>\u00a0is our objective. It\u2019s the variable in our case (or could be expression) which we\u2019re trying maximize or minimize.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int: total_nb_battery = 100;  % fixed input parameter\nint: total_kg_metal = 190000; % fixed input parameter\n\n% variable, possible number of different cars\nvar 0..total_nb_battery: nb_cybertruck;\nvar 0..total_nb_battery: nb_model3;\n\nvar int: profit = nb_cybertruck * 40000 + nb_model3 * 35000;\n\n% limit total number of kilograms\nconstraint nb_cybertruck * 2500 + nb_model3 * 1500 &lt;= total_kg_metal;\n% limit total number of batteries\nconstraint nb_cybertruck + nb_model3 &lt;= total_nb_battery;\n\n% Find the value of the variables that makes the most money!\nsolve maximize profit;<\/code><\/pre>\n\n\n\n<p>\u200d<a id=\"\" href=\"https:\/\/play.disopt.com\/s\/o2kG5YpEOWmAX10q\" target=\"_blank\" rel=\"noopener\">miniTesla example in MiniZinc playground<\/a><\/p>\n\n\n\n<p>The amount of words to describe the problem in English would be about the same as in MiniZinc. The code is self-explanatory even without knowing a lot about the syntax.<\/p>\n\n\n\n<p>There\u2019s a few nuances:<\/p>\n\n\n\n<ul class=\"wp-block-list\">\n<li><code>int<\/code>&nbsp;(first 2 lines) fixed integer variables &#8211; value should be defined<\/li>\n\n\n\n<li><code>var int<\/code>&nbsp;unfixed integer variable &#8211; MiniZinc figures out the value later<\/li>\n\n\n\n<li><code>constraint<\/code>\u00a0some expression that should be true<\/li>\n<\/ul>\n\n\n\n<p>The line:\u00a0<code>var 0..total_nb_battery: nb_model3;<\/code>\u00a0says variable\u00a0<code>nb_model3<\/code>\u00a0should be an integer from 0 to\u00a0<code>total_nb_battery<\/code>. This could be written as:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>var int: nb_model3;\nconstraint nb_model3 &gt;= 0;\nconstraint nb_model3 &lt;= total_nb_battery;<\/code><\/pre>\n\n\n\n<p>The last line\u00a0<code>solve maximize profit<\/code>\u00a0tells MiniZinc what to optimize.<\/p>\n\n\n\n<p>If you have minizinc installed locally, you can solve the model with the command&nbsp;<code>minizinc minitesla.mzn --output-objective<\/code>&nbsp;and it should tell you how many cars to build in order to reach the maximized profit of $3.7M:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>nb_cybertruck = 40;\nnb_model3 = 60;\n_objective = 3700000;\n----------\n==========<\/code><\/pre>\n\n\n\n<p><code>---<\/code>\u00a0means it found a solution,\u00a0<code>===<\/code>\u00a0means it found the optimal solution.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">With a data file<\/h3>\n\n\n\n<p>To reuse the model we can split it into 2 separate files: a file for the model and a file for the data. In the model file we have variable definition without values like this:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int: total_nb_battery; \nint: total_kg_metal;<\/code><\/pre>\n\n\n\n<p>And the data file&nbsp;<code>minitesla.dzn<\/code>&nbsp;gives values for the model variables:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>total_nb_battery = 100;\ntotal_kg_metal = 190000;<\/code><\/pre>\n\n\n\n<p>Command to run model with the separate data file:\u00a0<code>minizinc minitesla.mzn minitesla.dzn<\/code>\u00a0(BTW, the file extension is matters to MiniZinc &#8211; don\u2019t change it!)<\/p>\n\n\n\n<p><a id=\"\" href=\"https:\/\/github.com\/skrypka\/minizinc_workshop\/tree\/master\/hello2\" target=\"_blank\" rel=\"noopener\">Source code of hello world with data file<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Building_our_first_on-call_schedule_model\"><\/span>Building our first on-call schedule model<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Now we\u2019re prepared to build our first simple on-call scheduling model. For input, the model takes developers preferences (does developer X want to be on-call at hour Y). The output: assign a developer to every hour next week. The final assignment should follow only one constraint: assign a developer to an hour according to their preferences.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Data Structures of scheduling model<\/h3>\n\n\n\n<p>Niklaus Wirth wrote the famous book <a id=\"\" href=\"https:\/\/en.wikipedia.org\/wiki\/Algorithms_+_Data_Structures_=_Programs\" target=\"_blank\" rel=\"noopener\">Algorithms + Data Structures = Programs<\/a>. For discrete optimization modeling, MiniZinc does Algorithms for us, so we only need to worry about the Data Structures part. For this problem we have 2 core data structures to define: the Input and the Output.<\/p>\n\n\n\n<p>For output we use an array <strong id=\"\">assignment<\/strong> which records which developer is on-call for every hour in the week and so has a size of 168 elements (because there are 7 days \u00d7 24 hours in a week).<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>int: nb_developers;\nset of int: HOURS = 1..168;\nset of int: DEVELOPERS = 1..nb_developers;\n\narray&#91;HOURS] of var DEVELOPERS: assignment;<\/code><\/pre>\n\n\n\n<p>Besides <strong id=\"\">array<\/strong>, we\u2019ve introduced <strong id=\"\">set of int <\/strong>which is an enumeration of the numbers from start to end inclusive. MiniZinc arrays have named indexes. In our example <strong id=\"\">assignment<\/strong> has named indexes based on the range <strong id=\"\">HOURS<\/strong> (1..168). The statement <strong id=\"\">array[HOURS] of var DEVELOPERS: assignment = [7, 8, 9, &#8230;] <\/strong>therefore means developer 7 will be on-call at hour 1 (the first index of <strong id=\"\">HOURS<\/strong> range).<\/p>\n\n\n\n<p>We\u2019ll make the input data a multi-dimensional array, with size <strong id=\"\">DEVELOPERS<\/strong> \u00d7 <strong id=\"\">HOURS<\/strong>. This represents the mapping of developer and an hour to an integer in the set { 0, 1 }. Where a 1 means a developer is available for on-call.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>array&#91;DEVELOPERS, HOURS] of 0..1: working_hours;<\/code><\/pre>\n\n\n\n<p>Example of a data file (notice how rows separated with<strong id=\"\"> | <\/strong>symbol):<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>nb_developers = 3;\n\nworking_hours = &#91;|\n0, 0, 1, ..., 0 |\n0, 1, 1, ..., 0 |\n1, 0, 0, ..., 1 |];<\/code><\/pre>\n\n\n\n<p>One note about <strong id=\"\">nb_developers<\/strong>. Theoretically we could get the value of <strong id=\"\">nb_developers<\/strong> from <strong id=\"\">working_hours<\/strong>, but in practice it\u2019s a chicken and egg problem and MiniZinc has to be told <strong id=\"\">nb_developers<\/strong> to enumerate properly over <strong id=\"\">working_hours<\/strong> array.<\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Constraint and objective<\/h3>\n\n\n\n<p>We\u2019re going to add our first constraint now: if a developer is not available at some hour in working_hours array, then we should not assign them to be on-call.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>constraint forall(hour in HOURS, developer in DEVELOPERS)(\n    working_hours&#91;developer, hour] = 0 -> assignment&#91;hour] != developer\n);<\/code><\/pre>\n\n\n\n<p><strong id=\"\">-><\/strong> means implication. For me it was easier to understand by thinking it as being equivalent to this pseudocode:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>if working_hours&#91;developer, hour] == 0:\n    add_constraint(assignment&#91;hour] != developer)<\/code><\/pre>\n\n\n\n<p>Unlike the miniTesla example, here we don\u2019t need optimization, as we don\u2019t have an expression to optimize. Instead, we simply ask MiniZinc to satisfy all the constraints:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>solve satisfy;<\/code><\/pre>\n\n\n\n<p>If you run it then a solution will be available in a few milliseconds.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>assignment = array1d(1..168, &#91;1, 1, 1, ..., 1]);\n----------<\/code><\/pre>\n\n\n\n<p>The solution says it\u2019s not so much fun to be the first developer.<\/p>\n\n\n\n<p><a id=\"\" href=\"https:\/\/play.disopt.com\/s\/nZkaEjmV51brz1Bw\" target=\"_blank\" rel=\"noopener\">First unfair model in MiniZinc Playground<\/a> or <a id=\"\" href=\"https:\/\/github.com\/skrypka\/minizinc_workshop\/tree\/master\/oncall1\" target=\"_blank\" rel=\"noopener\">on GitHub<\/a><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Fairness<\/h3>\n\n\n\n<p>Let\u2019s add fairness to the model. We\u2019re going to define fairness as the total on-call hours for each developer should be as similar as possible. To make life easier later we can create an intermediate array total_hours, which holds the numbers of on-call hours for every developer.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>array&#91;DEVELOPERS] of var int: total_hours = &#91;\n    sum( &#91;assignment&#91;h]=developer | hour in HOURS ] )\n    | developer in DEVELOPERS\n];<\/code><\/pre>\n\n\n\n<p>Here we can see new syntax, a list comprehension. We iterate for every developer, and in the inner list comprehension, calculate the actual number of working hours.<\/p>\n\n\n\n<p>To solve for fairness, we need an expression to convert <strong id=\"\">total_hours<\/strong> to a single number so different solutions can be compared. One option is <strong id=\"\">min-max<\/strong>:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>solve minimize max(total_hours) - min(total_hours);<\/code><\/pre>\n\n\n\n<p>The minimal possible objective expression is 0 when all developers has equal total on-call hours per week. The expression is provably correct but in practice it\u2019s pretty slow with default miniZinc optimizer, as the approach it takes is to first assign the first developer to all hours as initial solution and then try to improve it.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/uploads-ssl.webflow.com\/60da68c37e5767dfb65004c0\/61f1d6d7ca97aa173292ce7c_oncall2-slow.gif\" alt=\"slow min max optimization\"\/><figcaption class=\"wp-element-caption\">(Notice how slowly the objective value decreases and how not optimally we search in problem space)<\/figcaption><\/figure>\n\n\n\n<p>One option to improve performance is to tell MiniZinc to select developers randomly during search with search annotation. You can read more about this in the <a id=\"\" href=\"https:\/\/www.minizinc.org\/doc-2.4.3\/en\/mzn_search.html\" target=\"_blank\" rel=\"noopener\">MiniZinc tutorial<\/a>, here we\u2019ll focus on another solution.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>solve :: int_search(assignment, first_fail, indomain_random)\n      minimize max(total_hours) - min(total_hours);<\/code><\/pre>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/uploads-ssl.webflow.com\/60da68c37e5767dfb65004c0\/61f1d6d77de6eac32e16ccd5_oncall2-fast.gif\" alt=\"fast min max optimization\"\/><\/figure>\n\n\n\n<p><a id=\"\" href=\"https:\/\/play.disopt.com\/s\/0QK7BPpo1Lm1qvLJ\" target=\"_blank\" rel=\"noopener\">Min-max model in MiniZinc Playground<\/a> or <a id=\"\" href=\"https:\/\/github.com\/skrypka\/minizinc_workshop\/tree\/master\/oncall2\" target=\"_blank\" rel=\"noopener\">on GitHub<\/a><\/p>\n\n\n\n<h3 class=\"wp-block-heading\">Even fairer fairness<\/h3>\n\n\n\n<p>The min-max objective is simple to define, but unfortunately, in some edge cases, it will not work. Minimum and maximum create boundaries and the algorithm will try to push them together as much as possible. But imagine if minimum and maximum boundaries stack at some values because some constraint, in such case min-max objective will NOT even try to optimize developers between boundaries.<\/p>\n\n\n\n<p>Example: we have 4 developers and fair distribution of on-call hours would be 42 total hours per week for everyone [42,42,42,42], objective here equals to 0 because maximum and minimum are the same. Let\u2019s assume we have only 1 developer in Asia timezone, so only she could cover some number of hours (let\u2019s say 84). Now fair distribution would look like [84,28,28,28]. The model cannot decrease maximum but still assigns to all other developers equal number of hours. So far so good\u2026 but one developer is spending a week in Bahamas without internet. Now min(total_hours) equals to 0. So distributions [84,84,0,0] and [84,42,42,0] have the same objective equal to 84 but different fairness. Our objective does not represent fairness anymore.<\/p>\n\n\n\n<p>Instead, we can use more complicated objective expression that measures the difference between all combinations of DEVELOPERS:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>var int: absolute_diff = sum(developer1 in DEVELOPERS, developer2 in DEVELOPERS where developer1 > developer2)(\n     abs(total_hours&#91;developer1] - total_hours&#91;developer2])\n);<\/code><\/pre>\n\n\n\n<p>Again there is new syntax, but it\u2019s slightly different list comprehension with an aggregation function on top. We iterate for all unique DEVELOPERS pairs and for each pair, calculate the absolute difference. As the last step, we sum all such differences.<\/p>\n\n\n\n<p>Only one line left, to ask to minimize the sum of absolute differences:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>solve minimize absolute_diff;<\/code><\/pre>\n\n\n\n<p><a id=\"\" href=\"https:\/\/play.disopt.com\/s\/R7vPBgdao7b2XMkq\" target=\"_blank\" rel=\"noopener\">Model with absolute difference objective in MiniZinc Playground<\/a> or <a id=\"\" href=\"https:\/\/github.com\/skrypka\/minizinc_workshop\/tree\/master\/oncall3\" target=\"_blank\" rel=\"noopener\">on GitHub<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Working_with_optional_variable\"><\/span>Working with optional variable<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>What happens if no developers can cover some hours? Remember that assignment is defined as <strong id=\"\">array[HOURS] of var DEVELOPERS: assignment;<\/strong> it <strong id=\"\">requires<\/strong> a developer for every hour, otherwise MiniZinc will report an error:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>  WARNING: model inconsistency detected\n=====UNSATISFIABLE=====<\/code><\/pre>\n\n\n\n<p>The solution is to allow some values to have a <strong id=\"\">nil<\/strong> value. MiniZinc natively supports <a id=\"\" href=\"https:\/\/www.minizinc.org\/doc-2.4.3\/en\/optiontypes.html\" target=\"_blank\" rel=\"noopener\">optional types<\/a>, but I prefer to use 0 to represent optional value (because some solvers don\u2019t have optional type; plus for future performance optimization I prefer model the problem as low-level as possible).<\/p>\n\n\n\n<p>We need define a new range <strong id=\"\">DEVELOPERS0<\/strong> which includes an extra 0, and use it as a possible values of <strong id=\"\">assignment<\/strong> array for every hour.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>set of int: DEVELOPERS0 = 0..nb_developers;\narray&#91;HOURS] of var DEVELOPERS0: assignment;<\/code><\/pre>\n\n\n\n<p>This actually is not enough. The objective tries to minimize the difference, and the easiest optimal result is to set all on-call hours to 0, so the objective will be 0 too. Instant optimal solution\u2026<\/p>\n\n\n\n<p>One way to fix this is to add a constraint: if somebody is available at some hour, then an hour should not be 0.<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>% calculate if developer available at specific hour\narray&#91;HOURS] of var int: is_developer_available = &#91;\n    max( &#91;working_hours&#91;developer, hour] | developer in DEVELOPERS] )\n    | hour in HOURS\n];\n\n% always assign someone if there is someone available\nconstraint forall(hour in HOURS)(\n    is_developer_available&#91;hour] = 1 -> assignment&#91;hour] != 0\n);<\/code><\/pre>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Choosing_a_solver\"><\/span>Choosing a solver<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Another complexity with discrete optimization is that you should understand what type of solver will be used before writing the model. By default, MiniZinc uses <a id=\"\" href=\"https:\/\/www.gecode.org\/\" target=\"_blank\" rel=\"noopener\">Gecode<\/a> which is a smart depth-first search. It\u2019s good enough for many models, but not for this one. Here decision tree is wide and our objective function cannot direct the search of Gecode.<\/p>\n\n\n\n<p>Instead, from the beginning, I specifically optimized the model for Mixed Integer Programming. By optimize, I mean I tried to use boolean variables and array representation instead of sets. On the command line, we need to specify the solver to use. I use Coin-bc, a great open-sourced mixed integer programming solver included by default in MiniZinc:<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>minizinc oncall.mzn oncall.dzn --all-solutions --output-objective --solver Coin-bc<\/code><\/pre>\n\n\n\n<p>Coin-bc returns the result faster for the model and in many cases proves optimal solution.<\/p>\n\n\n\n<figure class=\"wp-block-image\"><img decoding=\"async\" src=\"https:\/\/uploads-ssl.webflow.com\/60da68c37e5767dfb65004c0\/61f1d6d717a0b17dc7fe30d5_oncall4.gif\" alt=\"final model with mixed integer programming solver\"\/><\/figure>\n\n\n\n<p>Notice how Gecode solver finds an optimal solution in a few seconds, and then still tries to improve. Coin-bc finds the solution slightly faster and proves optimality. This doesn\u2019t mean that Coin-bc is better than Gecode &#8211; both have strengths and weaknesses. To properly explain the difference we need to dig into constraint-based algorithms(Gecode) and mixed integer programming(Coin-bc) first, and it\u2019s too much for this article. We actually use both in production. Gecode finds first initial solution, then Coin-bc optimizes it.<\/p>\n\n\n\n<p><a id=\"\" href=\"https:\/\/play.disopt.com\/s\/werB0ap1MKpkxvZQ\" target=\"_blank\" rel=\"noopener\">Model with absolute difference objective in MiniZinc Playground (Playground only supports Gecode solver)<\/a> or <a id=\"\" href=\"https:\/\/github.com\/skrypka\/minizinc_workshop\/tree\/master\/oncall4\" target=\"_blank\" rel=\"noopener\">on GitHub<\/a><\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Learning_materials\"><\/span>Learning materials<span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>I found online course <a id=\"\" href=\"https:\/\/www.coursera.org\/learn\/discrete-optimization\" target=\"_blank\" rel=\"noopener\">Discrete Optimization<\/a> at the right time for me. I took time off between 2 jobs and was going to just spend a few hours to watch the course, but the leaderboard made some adjustment. I spent about 2 months full-time on solving the problems, and eventually I managed get an A on all of them. The hardest and most rewarding course in my life. Thanks to Prof. Pascal Van Hentenryck and Dr. Carleton Coffrin!<\/p>\n\n\n\n<p>To start in this field, I\u2019d suggest 4 online courses in order:<\/p>\n\n\n\n<ol class=\"wp-block-list\">\n<li><a id=\"\" href=\"https:\/\/www.coursera.org\/learn\/discrete-optimization\" target=\"_blank\" rel=\"noopener\">Discrete Optimization<\/a> from Prof. Pascal Van Hentenryck and Dr. Carleton Coffrin.<\/li>\n\n\n\n<li><a id=\"\" href=\"https:\/\/www.coursera.org\/learn\/basic-modeling\" target=\"_blank\" rel=\"noopener\">Basic Modeling for Discrete Optimization<\/a> from Prof. Peter James Stuckey and Prof. Jimmy Ho Man Lee.<\/li>\n\n\n\n<li><a id=\"\" href=\"https:\/\/www.coursera.org\/learn\/advanced-modeling\" target=\"_blank\" rel=\"noopener\">Advanced Modeling for Discrete Optimization<\/a> from Prof. Peter James Stuckey and Prof. Jimmy Ho Man Lee.<\/li>\n\n\n\n<li><a id=\"\" href=\"https:\/\/www.coursera.org\/learn\/solving-algorithms-discrete-optimization\" target=\"_blank\" rel=\"noopener\">Solving Algorithms for Discrete Optimization<\/a> from Prof. Peter James Stuckey and Prof. Jimmy Ho Man Lee.<\/li>\n<\/ol>\n\n\n\n<p>Don\u2019t forget to check out the full <a href=\"https:\/\/www.minizinc.org\/doc-2.6.4\/en\/part_2_tutorial.html\" target=\"_blank\" rel=\"noopener\">MiniZinc tutorial<\/a>. It covers basic syntax upto advanced topics like search annotation, best modelling practices, and so on with many examples.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>The engineering team of RainforestQA (YC S12) is remote and distributed around the globe, with developers in America, Europe, and Asia. We\u2019re using PagerDuty to assign developers on-call and for contacting\/escalating people in case of incidents. Our working hours cover almost all time-zones, about 22 hours from full time-zone coverage. Yet for distributing our on-call [&hellip;]<\/p>\n","protected":false},"author":4,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"_acf_changed":false,"content-type":"","inline_featured_image":false,"footnotes":""},"categories":[6],"tags":[],"class_list":["post-349","post","type-post","status-publish","format-standard","hentry","category-engineering"],"acf":[],"_links":{"self":[{"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/posts\/349","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/users\/4"}],"replies":[{"embeddable":true,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/comments?post=349"}],"version-history":[{"count":7,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/posts\/349\/revisions"}],"predecessor-version":[{"id":1057,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/posts\/349\/revisions\/1057"}],"wp:attachment":[{"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/media?parent=349"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/categories?post=349"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.rainforestqa.com\/blog\/wp-json\/wp\/v2\/tags?post=349"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}