{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## OR Tools\n",
    "- 설치\n",
    "    ```\n",
    "    pip3 install ortools\n",
    "    ```\n",
    "- [문서](https://developers.google.com/optimization/introduction/python)\n",
    "- [예제 코드 Github](https://github.com/google/or-tools/tree/stable/examples/notebook)\n",
    "- 사용 방법\n",
    "    - 변수 생성\n",
    "    - 제약조건 정의\n",
    "    - 목적 함수 정의\n",
    "    - Solver 실행\n",
    "    - <변제목솔>\n",
    "- 흠 자꾸 죽음...\n",
    "    - Solver에서 변수 2번째 할당할 때 죽네\n",
    "- OR Tools Solver 자체는 어렵지 않은 느낌, 수식을 코드화할 수 있느냐가 관건일 듯\n",
    "- [Scipy의 Optimization](https://docs.scipy.org/doc/scipy/reference/tutorial/optimize.html)도 있음"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.linear_solver import pywraplp"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$$x + y$$\n",
    "$$0 \\leq x \\leq 1$$\n",
    "$$0 \\leq y \\leq 2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- solver 객체 생성"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "solver = pywraplp.Solver('SolveSimpleSystem',\n",
    "                       pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ortools.linear_solver.pywraplp.Solver"
      ]
     },
     "execution_count": 3,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(solver)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['ABNORMAL',\n",
       " 'AT_LOWER_BOUND',\n",
       " 'AT_UPPER_BOUND',\n",
       " 'Add',\n",
       " 'BASIC',\n",
       " 'BOP_INTEGER_PROGRAMMING',\n",
       " 'BoolVar',\n",
       " 'CBC_MIXED_INTEGER_PROGRAMMING',\n",
       " 'CLP_LINEAR_PROGRAMMING',\n",
       " 'Clear',\n",
       " 'ComputeConstraintActivities',\n",
       " 'ComputeExactConditionNumber',\n",
       " 'Constraint',\n",
       " 'EnableOutput',\n",
       " 'ExportModelAsLpFormat',\n",
       " 'ExportModelAsMpsFormat',\n",
       " 'FEASIBLE',\n",
       " 'FIXED_VALUE',\n",
       " 'FREE',\n",
       " 'GLOP_LINEAR_PROGRAMMING',\n",
       " 'INFEASIBLE',\n",
       " 'Infinity',\n",
       " 'IntVar',\n",
       " 'InterruptSolve',\n",
       " 'Iterations',\n",
       " 'LoadModelFromProto',\n",
       " 'LookupConstraint',\n",
       " 'LookupVariable',\n",
       " 'Maximize',\n",
       " 'Minimize',\n",
       " 'NOT_SOLVED',\n",
       " 'NumConstraints',\n",
       " 'NumVar',\n",
       " 'NumVariables',\n",
       " 'OPTIMAL',\n",
       " 'Objective',\n",
       " 'RowConstraint',\n",
       " 'SetSolverSpecificParametersAsString',\n",
       " 'SetTimeLimit',\n",
       " 'Solve',\n",
       " 'Sum',\n",
       " 'SupportsProblemType',\n",
       " 'SuppressOutput',\n",
       " 'UNBOUNDED',\n",
       " 'VerifySolution',\n",
       " 'WallTime',\n",
       " '__class__',\n",
       " '__del__',\n",
       " '__delattr__',\n",
       " '__dict__',\n",
       " '__dir__',\n",
       " '__doc__',\n",
       " '__eq__',\n",
       " '__format__',\n",
       " '__ge__',\n",
       " '__getattr__',\n",
       " '__getattribute__',\n",
       " '__gt__',\n",
       " '__hash__',\n",
       " '__init__',\n",
       " '__init_subclass__',\n",
       " '__le__',\n",
       " '__lt__',\n",
       " '__module__',\n",
       " '__ne__',\n",
       " '__new__',\n",
       " '__reduce__',\n",
       " '__reduce_ex__',\n",
       " '__repr__',\n",
       " '__setattr__',\n",
       " '__sizeof__',\n",
       " '__str__',\n",
       " '__subclasshook__',\n",
       " '__swig_destroy__',\n",
       " '__swig_getmethods__',\n",
       " '__swig_setmethods__',\n",
       " '__weakref__',\n",
       " 'infinity',\n",
       " 'iterations',\n",
       " 'nodes',\n",
       " 'set_time_limit',\n",
       " 'this',\n",
       " 'wall_time']"
      ]
     },
     "execution_count": 4,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dir(solver)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "solver.NumVar(Lower Bound, Upper Bound, 변수 이름)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = solver.NumVar(0, 1, 'x')\n",
    "y = solver.NumVar(0, 2, 'y')"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- solver.NumVar(lb:'double', ub:'double', name:'std::string const &')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ortools.linear_solver.pywraplp.Variable"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(y)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 7,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['Integer',\n",
       " 'Lb',\n",
       " 'ReducedCost',\n",
       " 'SetLb',\n",
       " 'SetUb',\n",
       " 'SolutionValue',\n",
       " 'Ub',\n",
       " '__add__',\n",
       " '__class__',\n",
       " '__del__',\n",
       " '__delattr__',\n",
       " '__dict__',\n",
       " '__dir__',\n",
       " '__div__',\n",
       " '__doc__',\n",
       " '__eq__',\n",
       " '__format__',\n",
       " '__ge__',\n",
       " '__getattr__',\n",
       " '__getattribute__',\n",
       " '__gt__',\n",
       " '__hash__',\n",
       " '__init__',\n",
       " '__init_subclass__',\n",
       " '__le__',\n",
       " '__lt__',\n",
       " '__module__',\n",
       " '__mul__',\n",
       " '__ne__',\n",
       " '__neg__',\n",
       " '__new__',\n",
       " '__radd__',\n",
       " '__reduce__',\n",
       " '__reduce_ex__',\n",
       " '__repr__',\n",
       " '__rmul__',\n",
       " '__rsub__',\n",
       " '__setattr__',\n",
       " '__sizeof__',\n",
       " '__str__',\n",
       " '__sub__',\n",
       " '__subclasshook__',\n",
       " '__swig_destroy__',\n",
       " '__swig_getmethods__',\n",
       " '__swig_setmethods__',\n",
       " '__truediv__',\n",
       " '__weakref__',\n",
       " 'basis_status',\n",
       " 'index',\n",
       " 'integer',\n",
       " 'lb',\n",
       " 'name',\n",
       " 'reduced_cost',\n",
       " 'solution_value',\n",
       " 'this',\n",
       " 'ub']"
      ]
     },
     "execution_count": 8,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dir(x)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 목적 함수 생성"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective = solver.Objective()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "['AddOffset',\n",
       " 'BestBound',\n",
       " 'Clear',\n",
       " 'GetCoefficient',\n",
       " 'Offset',\n",
       " 'SetCoefficient',\n",
       " 'SetMaximization',\n",
       " 'SetMinimization',\n",
       " 'SetOffset',\n",
       " 'SetOptimizationDirection',\n",
       " 'Value',\n",
       " '__class__',\n",
       " '__del__',\n",
       " '__delattr__',\n",
       " '__dict__',\n",
       " '__dir__',\n",
       " '__doc__',\n",
       " '__eq__',\n",
       " '__format__',\n",
       " '__ge__',\n",
       " '__getattr__',\n",
       " '__getattribute__',\n",
       " '__gt__',\n",
       " '__hash__',\n",
       " '__init__',\n",
       " '__init_subclass__',\n",
       " '__le__',\n",
       " '__lt__',\n",
       " '__module__',\n",
       " '__ne__',\n",
       " '__new__',\n",
       " '__reduce__',\n",
       " '__reduce_ex__',\n",
       " '__repr__',\n",
       " '__setattr__',\n",
       " '__sizeof__',\n",
       " '__str__',\n",
       " '__subclasshook__',\n",
       " '__swig_destroy__',\n",
       " '__swig_getmethods__',\n",
       " '__swig_setmethods__',\n",
       " '__weakref__',\n",
       " 'maximization',\n",
       " 'minimization',\n",
       " 'offset',\n",
       " 'this']"
      ]
     },
     "execution_count": 10,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "dir(objective)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- SetCoefficient : 계수 설정"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective.SetCoefficient(x, 1)\n",
    "objective.SetCoefficient(y, 1)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "SetMaximization() : 최대화"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 12,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective.SetMaximization()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 해풀기"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solution:\n",
      "x =  1.0\n",
      "y =  2.0\n"
     ]
    }
   ],
   "source": [
    "solver.Solve()\n",
    "print('Solution:')\n",
    "print('x = ', x.solution_value())\n",
    "print('y = ', y.solution_value())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 19,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "ortools.linear_solver.pywraplp.Solver"
      ]
     },
     "execution_count": 19,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "type(solver)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 20,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "x"
      ]
     },
     "execution_count": 20,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 21,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "1.0"
      ]
     },
     "execution_count": 21,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "x.solution_value()"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Linear Optimization\n",
    "- Maximize $$3x+4y$$\n",
    "\n",
    "- 제약조건\n",
    "$$x+2y \\leq 14$$\n",
    "$$3x-y \\geq 0$$\n",
    "$$x-y \\leq 2$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 변제목솔"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [],
   "source": [
    "# Constraint 1: x + 2y <= 14\n",
    "contraint1 = solver.Constraint(-solver.infinity(), 14)\n",
    "contraint1.SetCoefficient(x, 1)\n",
    "contraint1.SetCoefficient(y, 2)\n",
    "\n",
    "# Constraint 2: 3x - y >= 0\n",
    "contraint2 = solver.Constraint(0, solver.infinity())\n",
    "contraint2.SetCoefficient(x, 3)\n",
    "contraint2.SetCoefficient(y, -1)\n",
    "\n",
    "#  Constraint 3: x - y <= 2\n",
    "contraint3 = solver.Constraint(-solver.infinity(), 2)\n",
    "contraint3.SetCoefficient(x, 1)\n",
    "contraint3.SetCoefficient(y, -1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective = solver.Objective()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 13,
   "metadata": {},
   "outputs": [],
   "source": [
    "objective.SetCoefficient(x, 3)\n",
    "objective.SetCoefficient(y, 4)\n",
    "objective.SetMaximization()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0"
      ]
     },
     "execution_count": 14,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "solver.Solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 15,
   "metadata": {},
   "outputs": [],
   "source": [
    "opt_solution = 3 * x.solution_value() + 4 * y.solution_value()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 27,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Number of variables = 2\n",
      "Number of constraints = 4\n",
      "Solution:\n",
      "x =  6\n",
      "y =  4\n",
      "Optimal objective value = 34\n"
     ]
    }
   ],
   "source": [
    "print('Number of variables =', solver.NumVariables())\n",
    "print('Number of constraints =', solver.NumConstraints())\n",
    "# The value of each variable in the solution.\n",
    "print('Solution:')\n",
    "print('x = ', round(x.solution_value())) # 부동소수점 처리하기 위해 round\n",
    "print('y = ', round(y.solution_value())) \n",
    "# The objective value of the solution.\n",
    "print('Optimal objective value =', round(opt_solution))"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 부동소수점.. 5.9999, 3.999 이런식으로 나와서 round 처리"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 29,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Solving\n",
      "\n",
      "status 2\n",
      "Branches 105\n",
      "Conflicts 0\n",
      "WallTime 0.004366168\n"
     ]
    }
   ],
   "source": [
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "class SchoolSchedulingProblem(object):\n",
    "    def __init__(self, subjects, teachers, curriculum, specialties,\n",
    "                 working_days, periods, levels, sections, teacher_work_hours):\n",
    "        self.subjects = subjects\n",
    "        self.teachers = teachers\n",
    "        self.curriculum = curriculum\n",
    "        self.specialties = specialties\n",
    "        self.working_days = working_days\n",
    "        self.periods = periods\n",
    "        self.levels = levels\n",
    "        self.sections = sections\n",
    "        self.teacher_work_hours = teacher_work_hours\n",
    "\n",
    "\n",
    "class SchoolSchedulingSatSolver(object):\n",
    "    def __init__(self, problem):\n",
    "        # Problem\n",
    "        self.problem = problem\n",
    "\n",
    "        # Utilities\n",
    "        self.timeslots = [\n",
    "            '{0:10} {1:6}'.format(x, y) for x in problem.working_days\n",
    "            for y in problem.periods\n",
    "        ]\n",
    "        self.num_days = len(problem.working_days)\n",
    "        self.num_periods = len(problem.periods)\n",
    "        self.num_slots = len(self.timeslots)\n",
    "        self.num_teachers = len(problem.teachers)\n",
    "        self.num_subjects = len(problem.subjects)\n",
    "        self.num_levels = len(problem.levels)\n",
    "        self.num_sections = len(problem.sections)\n",
    "        self.courses = [\n",
    "            x * self.num_levels + y for x in problem.levels\n",
    "            for y in problem.sections\n",
    "        ]\n",
    "        self.num_courses = self.num_levels * self.num_sections\n",
    "\n",
    "        all_courses = range(self.num_courses)\n",
    "        all_teachers = range(self.num_teachers)\n",
    "        all_slots = range(self.num_slots)\n",
    "        all_sections = range(self.num_sections)\n",
    "        all_subjects = range(self.num_subjects)\n",
    "        all_levels = range(self.num_levels)\n",
    "\n",
    "        self.model = cp_model.CpModel()\n",
    "\n",
    "        self.assignment = {}\n",
    "        for c in all_courses:\n",
    "            for s in all_subjects:\n",
    "                for t in all_teachers:\n",
    "                    for slot in all_slots:\n",
    "                        if t in self.problem.specialties[s]:\n",
    "                            name = 'C:{%i} S:{%i} T:{%i} Slot:{%i}' % (c, s, t,\n",
    "                                                                       slot)\n",
    "                            self.assignment[c, s, t,\n",
    "                                            slot] = self.model.NewBoolVar(name)\n",
    "                        else:\n",
    "                            name = 'NO DISP C:{%i} S:{%i} T:{%i} Slot:{%i}' % (\n",
    "                                c, s, t, slot)\n",
    "                            self.assignment[c, s, t,\n",
    "                                            slot] = self.model.NewIntVar(\n",
    "                                                0, 0, name)\n",
    "\n",
    "        # Constraints\n",
    "\n",
    "        # Each course must have the quantity of classes specified in the curriculum\n",
    "        for level in all_levels:\n",
    "            for section in all_sections:\n",
    "                course = level * self.num_sections + section\n",
    "                for subject in all_subjects:\n",
    "                    required_slots = self.problem.curriculum[\n",
    "                        self.problem.levels[level], self.problem.subjects[\n",
    "                            subject]]\n",
    "                    self.model.Add(\n",
    "                        sum(self.assignment[course, subject, teacher, slot]\n",
    "                            for slot in all_slots\n",
    "                            for teacher in all_teachers) == required_slots)\n",
    "\n",
    "        # Teacher can do at most one class at a time\n",
    "        for teacher in all_teachers:\n",
    "            for slot in all_slots:\n",
    "                self.model.Add(\n",
    "                    sum([\n",
    "                        self.assignment[c, s, teacher, slot]\n",
    "                        for c in all_courses for s in all_subjects\n",
    "                    ]) <= 1)\n",
    "\n",
    "        # Maximum work hours for each teacher\n",
    "        for teacher in all_teachers:\n",
    "            self.model.Add(\n",
    "                sum([\n",
    "                    self.assignment[c, s, teacher, slot] for c in all_courses\n",
    "                    for s in all_subjects for slot in all_slots\n",
    "                ]) <= self.problem.teacher_work_hours[teacher])\n",
    "\n",
    "        # Teacher makes all the classes of a subject's course\n",
    "        teacher_courses = {}\n",
    "        for level in all_levels:\n",
    "            for section in all_sections:\n",
    "                course = level * self.num_sections + section\n",
    "                for subject in all_subjects:\n",
    "                    for t in all_teachers:\n",
    "                        name = 'C:{%i} S:{%i} T:{%i}' % (course, subject,\n",
    "                                                         teacher)\n",
    "                        teacher_courses[course, subject,\n",
    "                                        t] = self.model.NewBoolVar(name)\n",
    "                        temp_array = [\n",
    "                            self.assignment[course, subject, t, slot]\n",
    "                            for slot in all_slots\n",
    "                        ]\n",
    "                        self.model.AddMaxEquality(\n",
    "                            teacher_courses[course, subject, t], temp_array)\n",
    "                    self.model.Add(\n",
    "                        sum(teacher_courses[course, subject, t]\n",
    "                            for t in all_teachers) == 1)\n",
    "\n",
    "    def solve(self):\n",
    "        print('Solving')\n",
    "        solver = cp_model.CpSolver()\n",
    "        solution_printer = SchoolSchedulingSatSolutionPrinter()\n",
    "        status = solver.Solve(self.model)\n",
    "        print()\n",
    "        print('status', status)\n",
    "        print('Branches', solver.NumBranches())\n",
    "        print('Conflicts', solver.NumConflicts())\n",
    "        print('WallTime', solver.WallTime())\n",
    "\n",
    "\n",
    "class SchoolSchedulingSatSolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "    def __init__(self):\n",
    "        cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "        self.__solution_count = 0\n",
    "\n",
    "    def OnSolutionCallback(self):\n",
    "        print('Found Solution!')\n",
    "\n",
    "\n",
    "# DATA\n",
    "subjects = ['English', 'Math', 'History']\n",
    "levels = ['1-', '2-', '3-']\n",
    "sections = ['A']\n",
    "teachers = ['Mario', 'Elvis', 'Donald', 'Ian']\n",
    "teachers_work_hours = [18, 12, 12, 18]\n",
    "working_days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']\n",
    "periods = ['08:00-09:30', '09:45-11:15', '11:30-13:00']\n",
    "curriculum = {\n",
    "    ('1-', 'English'): 3,\n",
    "    ('1-', 'Math'): 3,\n",
    "    ('1-', 'History'): 2,\n",
    "    ('2-', 'English'): 4,\n",
    "    ('2-', 'Math'): 2,\n",
    "    ('2-', 'History'): 2,\n",
    "    ('3-', 'English'): 2,\n",
    "    ('3-', 'Math'): 4,\n",
    "    ('3-', 'History'): 2\n",
    "}\n",
    "\n",
    "# Subject -> List of teachers who can teach it\n",
    "specialties_idx_inverse = [\n",
    "    [1, 3],  # English   -> Elvis & Ian\n",
    "    [0, 3],  # Math      -> Mario & Ian\n",
    "    [2, 3]  # History   -> Donald & Ian\n",
    "]\n",
    "\n",
    "problem = SchoolSchedulingProblem(\n",
    "    subjects, teachers, curriculum, specialties_idx_inverse, working_days,\n",
    "    periods, levels, sections, teachers_work_hours)\n",
    "solver = SchoolSchedulingSatSolver(problem)\n",
    "solver.solve()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [],
   "source": [
    "from ortools.sat.python import cp_model\n",
    "\n",
    "\n",
    "def schedule():\n",
    "\n",
    "    # Input data.\n",
    "    positions = [\n",
    "        1, 2, 8, 10, 5, 3, 4, 3, 6, 6, 4, 5, 4, 3, 4, 4, 3, 4, 2, 1, 0, 0, 0,\n",
    "        0, 1, 2, 9, 9, 4, 3, 4, 3, 5, 4, 5, 2, 5, 6, 6, 7, 4, 2, 1, 0, 0, 0, 0,\n",
    "        0, 0, 2, 7, 6, 5, 2, 4, 4, 6, 6, 4, 5, 5, 5, 7, 5, 4, 4, 2, 3, 1, 0, 0,\n",
    "        0, 1, 2, 9, 7, 2, 2, 4, 2, 4, 5, 3, 2, 6, 7, 5, 6, 4, 4, 2, 1, 0, 0, 0,\n",
    "        0, 2, 2, 8, 8, 6, 3, 3, 3, 10, 9, 6, 3, 3, 4, 5, 4, 5, 4, 2, 1, 0, 0,\n",
    "        0, 0, 1, 2, 9, 5, 5, 4, 5, 2, 5, 7, 5, 3, 4, 8, 4, 4, 2, 3, 1, 0, 0, 0,\n",
    "        0, 0, 1, 2, 10, 5, 5, 4, 5, 2, 4, 6, 7, 4, 4, 5, 4, 4, 3, 3, 2, 1, 0,\n",
    "        0, 0, 0\n",
    "    ]\n",
    "\n",
    "    possible_shifts = [[\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 40\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 40\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        2, 40\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        3, 40\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        4, 0\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        5, 16\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        6, 16\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        7, 16\n",
    "    ], [\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,\n",
    "        8, 40\n",
    "    ]]\n",
    "\n",
    "    # Useful numbers.\n",
    "    num_slots = len(positions)\n",
    "    all_slots = range(num_slots)\n",
    "\n",
    "    num_shifts = len(possible_shifts)\n",
    "    all_shifts = range(num_shifts)\n",
    "\n",
    "    min_number_of_workers = [5 * x for x in positions]\n",
    "    num_workers = 300\n",
    "\n",
    "    # Model the problem.\n",
    "    model = cp_model.CpModel()\n",
    "\n",
    "    workers_per_shift = [\n",
    "        model.NewIntVar(0, num_workers, 'shift[%i]' % i) for i in all_shifts\n",
    "    ]\n",
    "\n",
    "    # Satisfy min requirements.\n",
    "    for slot in all_slots:\n",
    "        model.Add(\n",
    "            sum(workers_per_shift[shift] * possible_shifts[shift][slot]\n",
    "                for shift in all_shifts) >= min_number_of_workers[slot])\n",
    "\n",
    "    # Create the objective variable.\n",
    "    objective = model.NewIntVar(0, num_workers, 'objective')\n",
    "\n",
    "    # Link the objective.\n",
    "    model.Add(sum(workers_per_shift) == objective)\n",
    "\n",
    "    # Minimize.\n",
    "    model.Minimize(objective)\n",
    "\n",
    "    solver = cp_model.CpSolver()\n",
    "    status = solver.Solve(model)\n",
    "\n",
    "    if status == cp_model.OPTIMAL:\n",
    "        print('Objective value = %i' % solver.ObjectiveValue())\n",
    "\n",
    "    print('Statistics')\n",
    "    print('  - conflicts : %i' % solver.NumConflicts())\n",
    "    print('  - branches  : %i' % solver.NumBranches())\n",
    "    print('  - wall time : %f ms' % solver.WallTime())"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 38,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Objective value = 215\n",
      "Statistics\n",
      "  - conflicts : 0\n",
      "  - branches  : 8\n",
      "  - wall time : 0.000328 ms\n"
     ]
    }
   ],
   "source": [
    "schedule()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.5"
  },
  "varInspector": {
   "cols": {
    "lenName": 16,
    "lenType": 16,
    "lenVar": 40
   },
   "kernels_config": {
    "python": {
     "delete_cmd_postfix": "",
     "delete_cmd_prefix": "del ",
     "library": "var_list.py",
     "varRefreshCmd": "print(var_dic_list())"
    },
    "r": {
     "delete_cmd_postfix": ") ",
     "delete_cmd_prefix": "rm(",
     "library": "var_list.r",
     "varRefreshCmd": "cat(var_dic_list()) "
    }
   },
   "types_to_exclude": [
    "module",
    "function",
    "builtin_function_or_method",
    "instance",
    "_Feature"
   ],
   "window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}