{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 社交高尔夫问题\n",
    "\n",
    "**类别：** 排程\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/social-golfer-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**在 社交高尔夫问题 中**，我们考虑一个拥有 32 名会员的高尔夫俱乐部。每位会员每周打一次高尔夫，总是 4 人一组。该问题的目标是构建一个为期 10 周的高尔夫会员日程表，使社交最大化，即尽可能减少重复的同组。更一般地，问题是对 m 组 n 名高尔夫爱好者在 p 周内进行调度，以最大化社交。关于更多细节，请参阅 [CSPLib](http://www.csplib.org/Problems/prob010/) 或 [MathPuzzle](http://www.mathpuzzle.com/MAA/54-Golf%20Tournaments/mathgames_08_14_07.html)。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用 OptAgent 的 `bool` 决策变量建模每周分组\n",
    "- 使用 `and_`、`sum` 和 `max` 计算每对球员的重复同组次数\n",
    "- 区分分组决策变量与相遇次数等中间表达式\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的 社交高尔夫问题 实例文件包含三个数字：\n",
    "\n",
    "- 组数\n",
    "- 每组的大小\n",
    "- 周数\n",
    "\n",
    "我们在示例中使用的实例已知存在无重复同组的解。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "社交高尔夫问题的 OptAgent 模型使用布尔变量分配球员。对于每周 `w`、每组 `gr` 和每位球员 `gf`，`x[w][gr][gf]` 等于 1 表示球员 `gf` 在第 `w` 周被分到组 `gr`，否则为 0。使用 `sum` 约束每位球员每周恰好属于一个组，并确保每组人数正确。\n",
    "\n",
    "使用 `and_` 计算每周每组中两位球员是否相遇，再对所有周和组求和得到每对球员的相遇总次数。每对球员超过首次相遇的次数通过 `max(meetings - 1, 0)` 计算，目标是最小化所有球员对重复相遇次数的总和。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    return [int(value) for value in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "\n",
    "\n",
    "def read_instance(instance_file):\n",
    "    nb_groups, group_size, nb_weeks = read_integers(instance_file)\n",
    "    return nb_groups, group_size, nb_weeks\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=10):\n",
    "    nb_groups, group_size, nb_weeks = read_instance(input_file)\n",
    "    nb_golfers = nb_groups * group_size\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # x[w][gr][gf] is true when golfer gf joins group gr in week w.\n",
    "    x = [[[model.bool() for _ in range(nb_golfers)] for _ in range(nb_groups)] for _ in range(nb_weeks)]\n",
    "\n",
    "    # Each golfer is assigned to exactly one group every week.\n",
    "    for w in range(nb_weeks):\n",
    "        for gf in range(nb_golfers):\n",
    "            model.constraint(\n",
    "                model.sum(x[w][gr][gf] for gr in range(nb_groups)) == 1,\n",
    "            )\n",
    "\n",
    "    # Every group contains exactly group_size golfers.\n",
    "    for w in range(nb_weeks):\n",
    "        for gr in range(nb_groups):\n",
    "            model.constraint(\n",
    "                model.sum(x[w][gr][gf] for gf in range(nb_golfers)) == group_size,\n",
    "            )\n",
    "\n",
    "    # Count meetings beyond the first for every pair of golfers.\n",
    "    redundant_meetings = []\n",
    "    for gf0 in range(nb_golfers):\n",
    "        for gf1 in range(gf0 + 1, nb_golfers):\n",
    "            nb_meetings = model.sum(\n",
    "                model.and_(x[w][gr][gf0], x[w][gr][gf1]) for w in range(nb_weeks) for gr in range(nb_groups)\n",
    "            )\n",
    "            redundant_meetings.append(model.max(nb_meetings - 1, 0))\n",
    "\n",
    "    objective = model.sum(redundant_meetings)\n",
    "    model.minimize(objective)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible schedule found; Status = {solution.status}\")\n",
    "        return solution\n",
    "\n",
    "    display_lines = [\n",
    "        f\"Groups = {nb_groups}; Group size = {group_size}; Weeks = {nb_weeks}; \"\n",
    "        f\"Redundant meetings = {objective.value}; Status = {solution.status}\"\n",
    "    ]\n",
    "    output_lines = [str(objective.value)]\n",
    "    for w in range(nb_weeks):\n",
    "        display_lines.append(f\"Week {w + 1}\")\n",
    "        for gr in range(nb_groups):\n",
    "            golfers = [gf for gf in range(nb_golfers) if x[w][gr][gf].value]\n",
    "            golfer_text = \" \".join(str(gf) for gf in golfers)\n",
    "            display_lines.append(f\"  Group {gr + 1}: {golfer_text}\")\n",
    "            output_lines.append(golfer_text)\n",
    "        output_lines.append(\"\")\n",
    "\n",
    "    result_text = \"\\n\".join(display_lines)\n",
    "    print(result_text)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(\n",
    "            \"\\n\".join(output_lines) + \"\\n\",\n",
    "            encoding=\"utf-8\",\n",
    "        )\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "Notebook 直接调用 `main` 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；较大实例可能需要更长的 `time_limit`。\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_c4_3_3 = main(\n",
    "    INSTANCE_DIR / \"c_4_3_3.in\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_c7_5_5 = main(\n",
    "    INSTANCE_DIR / \"c_7_5_5.in\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_c10_10_3 = main(\n",
    "    INSTANCE_DIR / \"c_10_10_3.in\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "name": "python",
   "version": "3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}