examples/notebook/vendor_scheduling_sat.ipynb

{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Copyright 2010-2017 Google\n",
    "# Licensed under the Apache License, Version 2.0 (the \"License\");\n",
    "# you may not use this file except in compliance with the License.\n",
    "# You may obtain a copy of the License at\n",
    "#\n",
    "#     http://www.apache.org/licenses/LICENSE-2.0\n",
    "#\n",
    "# Unless required by applicable law or agreed to in writing, software\n",
    "# distributed under the License is distributed on an \"AS IS\" BASIS,\n",
    "# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.\n",
    "# See the License for the specific language governing permissions and\n",
    "# limitations under the License.\n",
    "\n",
    "from __future__ import absolute_import\n",
    "from __future__ import division\n",
    "from __future__ import print_function\n",
    "\n",
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "class SolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self, num_vendors, num_hours, possible_schedules,\n",
    "               selected_schedules, hours_stat, min_vendors):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__solution_count = 0\n",
    "    self.__num_vendors = num_vendors\n",
    "    self.__num_hours = num_hours\n",
    "    self.__possible_schedules = possible_schedules\n",
    "    self.__selected_schedules = selected_schedules\n",
    "    self.__hours_stat = hours_stat\n",
    "    self.__min_vendors = min_vendors\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    self.__solution_count += 1\n",
    "    print ('Solution %i: ', self.__solution_count)\n",
    "    print('  min vendors:', self.__min_vendors)\n",
    "    for i in range(self.__num_vendors):\n",
    "      print('  - vendor %i: ' % i,\n",
    "            self.__possible_schedules[self.Value(self.__selected_schedules[i])])\n",
    "    print()\n",
    "\n",
    "    for j in range(self.__num_hours):\n",
    "      print('  - # workers on day%2i: ' % j, end=' ')\n",
    "      print(self.Value(self.__hours_stat[j]), end=' ')\n",
    "      print()\n",
    "    print()\n",
    "\n",
    "  def SolutionCount(self):\n",
    "    return self.__solution_count\n",
    "\n",
    "\n",
    "# Create the model.\n",
    "model = cp_model.CpModel()\n",
    "\n",
    "#\n",
    "# data\n",
    "#\n",
    "num_vendors = 9\n",
    "num_hours = 10\n",
    "num_work_types = 1\n",
    "\n",
    "traffic = [100, 500, 100, 200, 320, 300, 200, 220, 300, 120]\n",
    "max_traffic_per_vendor = 100\n",
    "\n",
    "# Last columns are :\n",
    "#   index_of_the_schedule, sum of worked hours (per work type).\n",
    "# The index is useful for branching.\n",
    "possible_schedules = [[1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 8],\n",
    "                      [1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 4],\n",
    "                      [0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 2, 5],\n",
    "                      [0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 3, 4],\n",
    "                      [1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 4, 3],\n",
    "                      [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 5, 0]]\n",
    "\n",
    "num_possible_schedules = len(possible_schedules)\n",
    "selected_schedules = []\n",
    "vendors_stat = []\n",
    "hours_stat = []\n",
    "\n",
    "\n",
    "# Auxiliary data\n",
    "min_vendors = [t // max_traffic_per_vendor for t in traffic]\n",
    "all_vendors = range(num_vendors)\n",
    "all_hours = range(num_hours)\n",
    "\n",
    "#\n",
    "# declare variables\n",
    "#\n",
    "x = {}\n",
    "\n",
    "for v in all_vendors:\n",
    "  tmp = []\n",
    "  for h in all_hours:\n",
    "    x[v, h] = model.NewIntVar(0, num_work_types, 'x[%i,%i]' % (v, h))\n",
    "    tmp.append(x[v, h])\n",
    "  selected_schedule = model.NewIntVar(0, num_possible_schedules - 1,\n",
    "                                      's[%i]' % v)\n",
    "  hours = model.NewIntVar(0, num_hours, 'h[%i]' % v)\n",
    "  selected_schedules.append(selected_schedule)\n",
    "  vendors_stat.append(hours)\n",
    "  tmp.append(selected_schedule)\n",
    "  tmp.append(hours)\n",
    "\n",
    "  model.AddAllowedAssignments(tmp, possible_schedules)\n",
    "\n",
    "#\n",
    "# Statistics and constraints for each hour\n",
    "#\n",
    "for h in all_hours:\n",
    "  workers = model.NewIntVar(0, 1000, 'workers[%i]' %h)\n",
    "  model.Add(workers == sum(x[v, h] for v in all_vendors))\n",
    "  hours_stat.append(workers)\n",
    "  model.Add(workers * max_traffic_per_vendor >= traffic[h])\n",
    "\n",
    "#\n",
    "# Redundant constraint: sort selected_schedules\n",
    "#\n",
    "for v in range(num_vendors - 1):\n",
    "  model.Add(selected_schedules[v] <= selected_schedules[v + 1])\n",
    "\n",
    "# Solve model.\n",
    "solver = cp_model.CpSolver()\n",
    "solution_printer = SolutionPrinter(num_vendors, num_hours, possible_schedules,\n",
    "                                   selected_schedules, hours_stat,\n",
    "                                   min_vendors)\n",
    "status = solver.SearchForAllSolutions(model, solution_printer)\n",
    "print('Status = %s' % solver.StatusName(status))\n",
    "\n",
    "print('Statistics')\n",
    "print('  - conflicts : %i' % solver.NumConflicts())\n",
    "print('  - branches  : %i' % solver.NumBranches())\n",
    "print('  - wall time : %f s' % solver.WallTime())\n",
    "print('  - number of solutions found: %i' % solution_printer.SolutionCount())\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}