{
 "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 print_function\n",
    "\n",
    "import argparse\n",
    "from collections import defaultdict\n",
    "from ortools.sat.python import cp_model\n",
    "from ortools.data import rcpsp_pb2\n",
    "from ortools.data import pywraprcpsp\n",
    "import time\n",
    "\n",
    "parser = argparse.ArgumentParser()\n",
    "\n",
    "parser.add_argument(\n",
    "    '--input', default='', help='Input file to parse and solve.')\n",
    "parser.add_argument(\n",
    "    '--output_proto',\n",
    "    default='',\n",
    "    help='Output file to write the cp_model proto to.')\n",
    "\n",
    "\n",
    "class SolutionPrinter(cp_model.CpSolverSolutionCallback):\n",
    "  \"\"\"Print intermediate solutions.\"\"\"\n",
    "\n",
    "  def __init__(self):\n",
    "    cp_model.CpSolverSolutionCallback.__init__(self)\n",
    "    self.__solution_count = 0\n",
    "    self.__start_time = time.time()\n",
    "\n",
    "  def OnSolutionCallback(self):\n",
    "    current_time = time.time()\n",
    "    objective = self.ObjectiveValue()\n",
    "    print('Solution %i, time = %f s, objective = %i' %\n",
    "          (self.__solution_count, current_time - self.__start_time, objective))\n",
    "    self.__solution_count += 1\n",
    "\n",
    "\n",
    "def SolveRcpsp(problem, proto_file):\n",
    "  # Determine problem type.\n",
    "  problem_type = ('Resource investment'\n",
    "                  if problem.is_resource_investment else 'RCPSP')\n",
    "\n",
    "  if problem.is_rcpsp_max:\n",
    "    problem_type += '/Max delay'\n",
    "  if problem.is_consumer_producer:\n",
    "    print('Solving %s with %i reservoir resources and %i tasks' %\n",
    "          (problem_type, len(problem.resources), len(problem.tasks)))\n",
    "  else:\n",
    "    print('Solving %s with %i resources and %i tasks' %\n",
    "          (problem_type, len(problem.resources), len(problem.tasks)))\n",
    "\n",
    "  # Create the model.\n",
    "  model = cp_model.CpModel()\n",
    "\n",
    "  num_tasks = len(problem.tasks)\n",
    "  num_resources = len(problem.resources)\n",
    "\n",
    "  all_tasks = range(num_tasks)\n",
    "  all_active_tasks = range(1, num_tasks - 1)\n",
    "  all_resources = range(num_resources)\n",
    "\n",
    "  horizon = problem.deadline if problem.deadline != -1 else problem.horizon\n",
    "  if horizon == -1:  # Naive computation.\n",
    "    horizon = sum(max(r.duration for r in t.recipes) for t in problem.tasks)\n",
    "    if problem.is_rcpsp_max:\n",
    "      for t in problem.tasks:\n",
    "        for sd in t.successor_delays:\n",
    "          for rd in sd.recipe_delays:\n",
    "            for d in rd.min_delays:\n",
    "              horizon += abs(d)\n",
    "  print('  - horizon = %i' % horizon)\n",
    "\n",
    "  # Containers used to build resources.\n",
    "  intervals_per_resource = defaultdict(list)\n",
    "  demands_per_resource = defaultdict(list)\n",
    "  presences_per_resource = defaultdict(list)\n",
    "  starts_per_resource = defaultdict(list)\n",
    "\n",
    "  # Starts and ends for master interval variables.\n",
    "  task_starts = {}\n",
    "  task_ends = {}\n",
    "\n",
    "  # Containers for per-recipe per task variables.\n",
    "  alternatives_per_task = defaultdict(list)\n",
    "  presences_per_task = defaultdict(list)\n",
    "  starts_per_task = defaultdict(list)\n",
    "  ends_per_task = defaultdict(list)\n",
    "\n",
    "  # Create tasks.\n",
    "  for t in all_active_tasks:\n",
    "    task = problem.tasks[t]\n",
    "\n",
    "    if len(task.recipes) == 1:\n",
    "      # Create interval.\n",
    "      recipe = task.recipes[0]\n",
    "      task_starts[t] = model.NewIntVar(0, horizon, 'start_of_task_%i' % t)\n",
    "      task_ends[t] = model.NewIntVar(0, horizon, 'end_of_task_%i' % t)\n",
    "      interval = model.NewIntervalVar(task_starts[t], recipe.duration,\n",
    "                                      task_ends[t], 'interval_%i' % t)\n",
    "\n",
    "      # Store for later.\n",
    "      alternatives_per_task[t].append(interval)\n",
    "      starts_per_task[t].append(task_starts[t])\n",
    "      ends_per_task[t].append(task_ends[t])\n",
    "      presences_per_task[t].append(1)\n",
    "\n",
    "      # Register for resources.\n",
    "      for i in range(len(recipe.demands)):\n",
    "        demand = recipe.demands[i]\n",
    "        res = recipe.resources[i]\n",
    "        demands_per_resource[res].append(demand)\n",
    "        if problem.resources[res].renewable:\n",
    "          intervals_per_resource[res].append(interval)\n",
    "        else:\n",
    "          starts_per_resource[res].append(task_starts[t])\n",
    "          presences_per_resource[res].append(1)\n",
    "    else:\n",
    "      all_recipes = range(len(task.recipes))\n",
    "\n",
    "      # Compute duration range.\n",
    "      min_size = min(recipe.duration for recipe in task.recipes)\n",
    "      max_size = max(recipe.duration for recipe in task.recipes)\n",
    "\n",
    "      # Create one optional interval per recipe.\n",
    "      for r in all_recipes:\n",
    "        recipe = task.recipes[r]\n",
    "        is_present = model.NewBoolVar('is_present_%i_r%i' % (t, r))\n",
    "        start = model.NewIntVar(0, horizon, 'start_%i_r%i' % (t, r))\n",
    "        end = model.NewIntVar(0, horizon, 'end_%i_r%i' % (t, r))\n",
    "        interval = model.NewOptionalIntervalVar(\n",
    "            start, recipe.duration, end, is_present, 'interval_%i_r%i' % (t, r))\n",
    "\n",
    "        # Store variables.\n",
    "        alternatives_per_task[t].append(interval)\n",
    "        starts_per_task[t].append(start)\n",
    "        ends_per_task[t].append(end)\n",
    "        presences_per_task[t].append(is_present)\n",
    "\n",
    "        # Register intervals in resources.\n",
    "        for i in range(len(recipe.demands)):\n",
    "          demand = recipe.demands[i]\n",
    "          res = recipe.resources[i]\n",
    "          demands_per_resource[res].append(demand)\n",
    "          if problem.resources[res].renewable:\n",
    "            intervals_per_resource[res].append(interval)\n",
    "          else:\n",
    "            starts_per_resource[res].append(start)\n",
    "            presences_per_resource[res].append(is_present)\n",
    "\n",
    "      # Create the master interval for the task.\n",
    "      task_starts[t] = model.NewIntVar(0, horizon, 'start_of_task_%i' % t)\n",
    "      task_ends[t] = model.NewIntVar(0, horizon, 'end_of_task_%i' % t)\n",
    "      duration = model.NewIntVar(min_size, max_size, 'duration_of_task_%i' % t)\n",
    "      interval = model.NewIntervalVar(task_starts[t], duration, task_ends[t],\n",
    "                                      'interval_%i' % t)\n",
    "\n",
    "      # Link with optional per-recipe copies.\n",
    "      for r in all_recipes:\n",
    "        p = presences_per_task[t][r]\n",
    "        model.Add(task_starts[t] == starts_per_task[t][r]).OnlyEnforceIf(p)\n",
    "        model.Add(task_ends[t] == ends_per_task[t][r]).OnlyEnforceIf(p)\n",
    "        model.Add(duration == task.recipes[r].duration).OnlyEnforceIf(p)\n",
    "      model.Add(sum(presences_per_task[t]) == 1)\n",
    "\n",
    "  # Create makespan variable\n",
    "  makespan = model.NewIntVar(0, horizon, 'makespan')\n",
    "\n",
    "  # Add precedences.\n",
    "  if problem.is_rcpsp_max:\n",
    "    for t in all_active_tasks:\n",
    "      task = problem.tasks[t]\n",
    "      num_modes = len(task.recipes)\n",
    "      num_successors = len(task.successors)\n",
    "\n",
    "      for s in range(num_successors):\n",
    "        n = task.successors[s]\n",
    "        delay_matrix = task.successor_delays[s]\n",
    "        num_other_modes = len(problem.tasks[n].recipes)\n",
    "        for m1 in range(num_modes):\n",
    "          s1 = starts_per_task[t][m1]\n",
    "          if n == num_tasks - 1:\n",
    "            delay = delay_matrix.recipe_delays[m1].min_delays[0]\n",
    "            model.Add(s1 + delay <= makespan)\n",
    "          else:\n",
    "            for m2 in range(num_other_modes):\n",
    "              delay = delay_matrix.recipe_delays[m1].min_delays[m2]\n",
    "              s2 = starts_per_task[n][m2]\n",
    "              model.Add(s1 + delay <= s2)\n",
    "  else:  # Normal dependencies (task ends before the start of successors).\n",
    "    for t in all_active_tasks:\n",
    "      for n in problem.tasks[t].successors:\n",
    "        if n == num_tasks - 1:\n",
    "          model.Add(task_ends[t] <= makespan)\n",
    "        else:\n",
    "          model.Add(task_ends[t] <= task_starts[n])\n",
    "\n",
    "  # Containers for resource investment problems.\n",
    "  capacities = []\n",
    "  max_cost = 0\n",
    "\n",
    "  # Create resources.\n",
    "  for r in all_resources:\n",
    "    resource = problem.resources[r]\n",
    "    c = resource.max_capacity\n",
    "    if c == -1:\n",
    "      c = sum(demands_per_resource[r])\n",
    "\n",
    "    if problem.is_resource_investment:\n",
    "      capacity = model.NewIntVar(0, c, 'capacity_of_%i' % r)\n",
    "      model.AddCumulative(intervals_per_resource[r], demands_per_resource[r],\n",
    "                          capacity)\n",
    "      capacities.append(capacity)\n",
    "      max_cost += c * resource.unit_cost\n",
    "    elif resource.renewable:\n",
    "      if intervals_per_resource[r]:\n",
    "        model.AddCumulative(intervals_per_resource[r], demands_per_resource[r],\n",
    "                            c)\n",
    "    elif presences_per_resource[r]:  # Non empty non renewable resource.\n",
    "      if problem.is_consumer_producer:\n",
    "        model.AddReservoirConstraint(\n",
    "            starts_per_resource[r], demands_per_resource[r],\n",
    "            resource.min_capacity, resource.max_capacity)\n",
    "      else:\n",
    "        model.Add(\n",
    "            sum(presences_per_resource[r][i] * demands_per_resource[r][i]\n",
    "                for i in range(len(presences_per_resource[r]))) <= c)\n",
    "\n",
    "  # Objective.\n",
    "  if problem.is_resource_investment:\n",
    "    objective = model.NewIntVar(0, max_cost, 'capacity_costs')\n",
    "    model.Add(objective == sum(problem.resources[i].unit_cost * capacities[i]\n",
    "                               for i in range(len(capacities))))\n",
    "  else:\n",
    "    objective = makespan\n",
    "\n",
    "  model.Minimize(objective)\n",
    "\n",
    "  if proto_file:\n",
    "    print('Writing proto to %s' % proto_file)\n",
    "    text_file = open(proto_file, 'w')\n",
    "    text_file.write(str(model))\n",
    "    text_file.close()\n",
    "\n",
    "  # Solve model.\n",
    "  solver = cp_model.CpSolver()\n",
    "  solution_printer = SolutionPrinter()\n",
    "  status = solver.SolveWithSolutionCallback(model, solution_printer)\n",
    "  print('Solve status: %s' % solver.StatusName(status))\n",
    "  print('Optimal objective value: %i' % solver.ObjectiveValue())\n",
    "  print('Statistics')\n",
    "  print('  - conflicts : %i' % solver.NumConflicts())\n",
    "  print('  - branches  : %i' % solver.NumBranches())\n",
    "  print('  - wall time : %f s' % solver.WallTime())\n",
    "\n",
    "\n",
    "parser = pywraprcpsp.RcpspParser()\n",
    "parser.ParseFile(args.input)\n",
    "problem = parser.Problem()\n",
    "SolveRcpsp(problem, args.output_proto)\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}