{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 电影拍摄调度问题\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/movie-shoot-scheduling-problem-2)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "我们考虑由 [Bomsdorf and Derigs, OR Spectrum](https://link.springer.com/article/10.1007/s00291-007-0103-6) 定义的**电影拍摄调度问题**的简化版本。一部电影由一组场景组成，每个场景在给定的地点以一组演员持续一段确定的时长。我们必须确定场景的拍摄顺序，该顺序不一定与它们在最终电影中的顺序相同。然而，存在紧前约束，规定某些场景必须在其他场景之前拍摄。\n",
    "\n",
    "问题的目标是找到一个使总成本最小化的序列，总成本是演员成本和地点成本之和。事实上，演员不仅需要出现在其每个场景中，还需要出现在其场景之间。他们必须为其在现场的每个额外在场日获得报酬。此外，每当访问某个地点以拍摄一组场景时，都需要支付地点成本，无论场景数量如何。由于我们必须至少访问每个地点一次，因此我们忽略首次访问的成本。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用列表变量表示拍摄顺序。\n",
    "- 使用 `index` 获取场景的位置，并添加紧前约束。\n",
    "- 使用 `create_int_external_function` 将演员和地点成本计算接入目标表达式。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "57f7a427",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的电影拍摄调度问题实例来自 [Optimization Hub](https://opthub.uniud.it/problem/mss)。其格式如下：\n",
    "\n",
    "- 演员数\n",
    "- 场景数\n",
    "- 地点数\n",
    "- 紧前关系数\n",
    "- 每个演员的成本\n",
    "- 每个地点的成本\n",
    "- 每个场景的时长\n",
    "- 每个场景的地点\n",
    "- 对每个场景，每个演员的出场情况\n",
    "- 场景之间的紧前关系\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "OptAgent 模型使用一个列表变量表示场景的拍摄顺序，约束其长度等于场景数，使每个场景恰好出现一次。通过 `model.index` 获取指定场景的位置，并约束前驱场景的位置小于后继场景的位置。\n",
    "\n",
    "`CostFunction.compute_cost` 从回调参数读取候选场景序列，计算演员的额外在场成本与地点的重复访问成本，返回整数总成本。模型使用 `create_int_external_function` 注册该函数，再将它应用于列表变量，最小化得到的调用表达式。\n",
    "\n",
    "调用 `solve(model, time_limit_s=...)` 后，可以从列表表达式读取拍摄顺序，从目标表达式读取成本。读取值前应确认结果具有可行解。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "import sys\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    return [int(elem) for elem in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "\n",
    "\n",
    "class MssInstance:\n",
    "\n",
    "    #\n",
    "    # Read instance data\n",
    "    #\n",
    "    def __init__(self, filename):\n",
    "        file_it = iter(read_integers(filename))\n",
    "        self.nb_actors = next(file_it)\n",
    "        self.nb_scenes = next(file_it)\n",
    "        self.nb_locations = next(file_it)\n",
    "        self.nb_precedences = next(file_it)\n",
    "        self.actor_cost = [next(file_it) for i in range(self.nb_actors)]\n",
    "        self.location_cost = [next(file_it) for i in range(self.nb_locations)]\n",
    "        self.scene_duration = [next(file_it) for i in range(self.nb_scenes)]\n",
    "        self.scene_location = [next(file_it) for i in range(self.nb_scenes)]\n",
    "        self.is_actor_in_scene = [[next(file_it) for i in range(self.nb_scenes)]\n",
    "                                  for i in range(self.nb_actors)]\n",
    "        self.precedences = [[next(file_it) for i in range(2)]\n",
    "                            for i in range(self.nb_precedences)]\n",
    "\n",
    "        self.actor_nb_worked_days = self._compute_nb_worked_days()\n",
    "\n",
    "    def _compute_nb_worked_days(self):\n",
    "        actor_nb_worked_days = [0] * self.nb_actors\n",
    "        for a in range(self.nb_actors):\n",
    "            for s in range(self.nb_scenes):\n",
    "                if self.is_actor_in_scene[a][s]:\n",
    "                    actor_nb_worked_days[a] += self.scene_duration[s]\n",
    "        return actor_nb_worked_days\n",
    "\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=60):\n",
    "    data = MssInstance(instance_file)\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # shoot_order[i] is the scene index shot at position i.\n",
    "    shoot_order = model.list(data.nb_scenes)\n",
    "    model.constraint(\n",
    "        model.count(shoot_order) == data.nb_scenes\n",
    "    )\n",
    "\n",
    "    # Preserve the original precedence constraints through list index lookup.\n",
    "    for before, after in data.precedences:\n",
    "        model.constraint(\n",
    "            model.index(shoot_order, before) < model.index(shoot_order, after),\n",
    "        )\n",
    "\n",
    "    # Evaluate the scene order with an integer-valued external cost function.\n",
    "    cost_function = CostFunction(data)\n",
    "    external_cost = model.create_int_external_function(cost_function.compute_cost)\n",
    "    cost = external_cost(shoot_order)\n",
    "    model.minimize(cost)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    order = list(shoot_order.value)\n",
    "    print(\n",
    "        f\"Actors = {data.nb_actors}; Scenes = {data.nb_scenes}; \"\n",
    "        f\"Locations = {data.nb_locations}; Cost = {cost.value}; \"\n",
    "        f\"Status = {solution.feasible}\"\n",
    "    )\n",
    "    print(\"Shoot order:\", order)\n",
    "\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\n",
    "            f\"{cost.value}\\n\" + \" \".join(map(str, order)) + \"\\n\",\n",
    "            encoding=\"utf-8\",\n",
    "        )\n",
    "    return solution\n",
    "\n",
    "\n",
    "class CostFunction:\n",
    "\n",
    "    def __init__(self, data):\n",
    "        self.data = data\n",
    "\n",
    "    def compute_cost(self, context):\n",
    "        shoot_order = context[0]\n",
    "        if len(shoot_order) < self.data.nb_scenes:\n",
    "            # Infeasible solution if some scenes are missing\n",
    "            return sys.maxsize\n",
    "\n",
    "        location_extra_cost = self._compute_location_cost(shoot_order)\n",
    "        actor_extra_cost = self._compute_actor_cost(shoot_order)\n",
    "        return location_extra_cost + actor_extra_cost\n",
    "\n",
    "    def _compute_location_cost(self, shoot_order):\n",
    "        nb_location_visits = [0] * self.data.nb_locations\n",
    "        previous_location = -1\n",
    "        for i in range(self.data.nb_scenes):\n",
    "            current_location = self.data.scene_location[shoot_order[i]]\n",
    "            # When we change location, we increment the number of scenes of the new location\n",
    "            if previous_location != current_location:\n",
    "                nb_location_visits[current_location] += 1\n",
    "                previous_location = current_location\n",
    "        location_extra_cost = sum(cost * (nb_visits - 1)\n",
    "            for cost, nb_visits in zip(self.data.location_cost, nb_location_visits))\n",
    "        return location_extra_cost\n",
    "\n",
    "    def _compute_actor_cost(self, shoot_order):\n",
    "        # Compute first and last days of work for each actor\n",
    "        actor_first_day = [0] * self.data.nb_actors\n",
    "        actor_last_day = [0] * self.data.nb_actors\n",
    "        for j in range(self.data.nb_actors):\n",
    "            has_actor_started_working = False\n",
    "            start_day_of_scene = 0\n",
    "            for i in range(self.data.nb_scenes):\n",
    "                current_scene = shoot_order[i]\n",
    "                end_day_of_scene = start_day_of_scene \\\n",
    "                    + self.data.scene_duration[current_scene] - 1\n",
    "                if self.data.is_actor_in_scene[j][current_scene]:\n",
    "                    actor_last_day[j] = end_day_of_scene\n",
    "                    if not has_actor_started_working:\n",
    "                        has_actor_started_working = True\n",
    "                        actor_first_day[j] = start_day_of_scene\n",
    "                # The next scene begins the day after the end of the current one\n",
    "                start_day_of_scene = end_day_of_scene + 1\n",
    "\n",
    "        # Compute actor extra cost due to days paid but not worked\n",
    "        actor_extra_cost = 0\n",
    "        for j in range(self.data.nb_actors):\n",
    "            nb_paid_days = actor_last_day[j] - actor_first_day[j] + 1\n",
    "            actor_extra_cost += (nb_paid_days - self.data.actor_nb_worked_days[j]) \\\n",
    "                * self.data.actor_cost[j]\n",
    "        return actor_extra_cost\n",
    "\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "以下代码格演示如何调用 OptAgent 的电影拍摄调度模型。\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\"\n",
    "print(\"Instances:\", INSTANCE_DIR)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_movie5 = main(INSTANCE_DIR / \"movie5.txt\", time_limit=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_movie10 = main(INSTANCE_DIR / \"movie10.txt\", time_limit=1)\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": ".venv",
   "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.14.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}