{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "26f7f190",
   "metadata": {},
   "source": [
    "# Talent Scheduling\n",
    "\n",
    "In a talent scheduling problem, we are given a set of scenes $S = \\{ 0, ..., n - 1 \\}$ and a set of actors $A = \\{ 0, ..., m - 1 \\}$.\n",
    "In a scene $s \\in S$, a set of actors $A_s \\subseteq A$ plays for $d_s$ days.\n",
    "An actor comes to the location when the first scene he or she plays starts and leaves when the last scene he or she plays ends.\n",
    "For each day actor $a$ is on location, we need to pay the cost $c_a$.\n",
    "We want to find a sequence of scenes to shoot such that the total cost is minimized.\n",
    "\n",
    "## DP Formulation\n",
    "\n",
    "Suppose that a set of scenes $Q$ is remaining.\n",
    "A set of actors $\\bigcup_{s \\in S \\setminus Q} A_s$ already came to the location, and $\\bigcup_{s \\in Q} A_s$ is still on location because they need to play on the remaining scenes $Q$.\n",
    "Therefore, if we shoot a scene $s \\in Q$ next, the set of actors on location will be\n",
    "\n",
    "$$\n",
    "    L(s, Q) = A_s \\cup \\left( \\bigcup_{s' \\in S \\setminus Q} A_{s'} \\cap \\bigcup_{s' \\in Q } A_{s'}  \\right).\n",
    "$$\n",
    "\n",
    "We need to pay the cost $d_s \\sum_{a \\in L(s, Q)} c_a$ when shooting scene $s$.\n",
    "Once we shot scene $s$, the remaining problem is to decide the order of the remaining scenes $Q \\setminus \\{ s \\}$.\n",
    "Therefore, a state is defined by the set of remaining scenes $Q$, and the minimum cost to shoot $Q$ is represented by $V(Q)$.\n",
    "Because $A_s$, actors who play in scence $s$, are always on location when $s$ is shot, $\\sum_{s \\in Q} d_s \\sum_{a \\in A_s} c_a$ is a lower bound on $V(Q)$.\n",
    "We have the following DP formulation.\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "    \\text{compute } & V(S) \\\\\n",
    "    & V(Q) = \\begin{cases}\n",
    "        \\min\\limits_{s \\in Q} d_s \\sum\\limits_{a \\in L(s, Q)} c_a + V(Q \\setminus \\{ s \\}) & \\text{if } Q \\neq \\emptyset \\\\\n",
    "        0 & \\text{if } Q = \\emptyset\n",
    "    \\end{cases} \\\\\n",
    "    & V(Q) \\geq \\sum_{s \\in Q} d_s \\sum_{a \\in A_s} c_a.\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "If $A_s$, the set of actors that play in scence $s$, is equivalent to the set of actors currently on location, we can shoot $s$ with the minimum cost:\n",
    "we just need to pay for the actors who play in $s$.\n",
    "We should always shoot such a scene first.\n",
    "In state $Q$, the set of actors on location is $\\bigcup_{s \\in S \\setminus Q} A_{s} \\cap \\bigcup_{s \\in Q} A_{s}$.\n",
    "Therefore, we have the following optimal transition under certain conditions:\n",
    "\n",
    "$$\n",
    "    V(Q) = d_s \\sum\\limits_{a \\in A_s} c_a + V(Q \\setminus \\{ s \\}) \\text{ if } s \\in Q \\land A_s = \\bigcup_{s' \\in S \\setminus Q} A_{s'} \\cap \\bigcup_{s' \\in Q} A_{s'}.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8bc6812c",
   "metadata": {},
   "source": [
    "## Install DIDPPy"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "650fc341",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Requirement already satisfied: didppy in /home/kuro/tidel/code/didp-rs/didppy/.venv/lib/python3.10/site-packages (0.7.1)\r\n"
     ]
    }
   ],
   "source": [
    "!pip install didppy"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "ac5d85dc",
   "metadata": {},
   "source": [
    "## Data"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "98eb0734",
   "metadata": {},
   "outputs": [],
   "source": [
    "# Number of scenes\n",
    "n = 4\n",
    "# Number of actors\n",
    "m = 4\n",
    "# Duration of scenes\n",
    "d = [1, 1, 1, 1]\n",
    "# Costs of actors\n",
    "c = [1, 3, 1, 2]\n",
    "# Actors in each scene\n",
    "scene_to_actors = [[0, 1, 3], [1, 2], [0, 2, 3], [0, 1, 2]]"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "116e8e69",
   "metadata": {},
   "source": [
    "## Modeling"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "745c9e01",
   "metadata": {},
   "outputs": [],
   "source": [
    "import didppy as dp\n",
    "\n",
    "model = dp.Model()\n",
    "\n",
    "scene = model.add_object_type(number=n)\n",
    "actor = model.add_object_type(number=m)\n",
    "\n",
    "# Q\n",
    "remaining = model.add_set_var(object_type=scene, target=list(range(n)))\n",
    "\n",
    "scene_to_actors_table = model.add_set_table(scene_to_actors, object_type=scene)\n",
    "actor_to_cost = model.add_int_table(c)\n",
    "\n",
    "# Precompute the minimum cost of each scene\n",
    "scene_to_min_cost = model.add_int_table(\n",
    "    [d[s] * sum(c[a] for a in scene_to_actors[s]) for s in range(n)]\n",
    ")\n",
    "\n",
    "for s in range(n):\n",
    "    already_shot = remaining.complement()\n",
    "    came_to_location = scene_to_actors_table.union(already_shot)\n",
    "    standby = scene_to_actors_table.union(remaining)\n",
    "    on_location = scene_to_actors_table[s] | (came_to_location & standby)\n",
    "\n",
    "    shoot = dp.Transition(\n",
    "        name=\"shoot {}\".format(s),\n",
    "        cost=d[s] * actor_to_cost[on_location] + dp.IntExpr.state_cost(),\n",
    "        effects=[(remaining, remaining.remove(s))],\n",
    "        preconditions=[remaining.contains(s)],\n",
    "    )\n",
    "    model.add_transition(shoot)\n",
    "\n",
    "model.add_base_case([remaining.is_empty()])\n",
    "\n",
    "model.add_dual_bound(scene_to_min_cost[remaining])\n",
    "\n",
    "for s in range(n):\n",
    "    already_shot = remaining.complement()\n",
    "    came_to_location = scene_to_actors_table.union(already_shot)\n",
    "    standby = scene_to_actors_table.union(remaining)\n",
    "\n",
    "    shoot = dp.Transition(\n",
    "        name=\"forced shoot {}\".format(s),\n",
    "        cost=scene_to_min_cost[s] + dp.IntExpr.state_cost(),\n",
    "        effects=[(remaining, remaining.remove(s))],\n",
    "        preconditions=[\n",
    "            remaining.contains(s),\n",
    "            scene_to_actors_table[s] == (came_to_location & standby),\n",
    "        ],\n",
    "    )\n",
    "    model.add_transition(shoot, forced=True)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4020e1de",
   "metadata": {},
   "source": [
    "## Solving"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "9a37dbc0",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Transitions to apply:\n",
      "\n",
      "shoot 2\n",
      "shoot 0\n",
      "forced shoot 3\n",
      "forced shoot 1\n",
      "\n",
      "Cost: 20\n"
     ]
    }
   ],
   "source": [
    "solver = dp.CABS(model, quiet=True)\n",
    "solution = solver.search()\n",
    "\n",
    "print(\"Transitions to apply:\")\n",
    "print(\"\")\n",
    "\n",
    "for t in solution.transitions:\n",
    "    print(t.name)\n",
    "\n",
    "print(\"\")\n",
    "print(\"Cost: {}\".format(solution.cost))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "language": "python",
   "name": ".venv"
  },
  "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.10.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}