{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 最大割问题\n",
    "\n",
    "**类别：** 选址\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/max-cut-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "**在最大割问题**中，我们考虑一个图 G = (V, E)。我们希望找到该图的一个最大割，即将图的顶点划分为两个互补集合 S 和 T，使得 S 和 T 之间的边数尽可能大。等价地，该问题在于找到该图的一个尽可能多边的二部子图。这里，我们考虑该问题的一个更通用的版本：加权最大割问题。每条边都与一个数（其权重）相关联，问题的目标是找到一个顶点的子集 S，使得 S 与其补集之间的边权重之和尽可能大。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 了解 OptAgent 的建模方式：[区分决策变量与中间表达式](https://optagent.pages.dev/guide/modeling/)\n",
    "- 使用 [`非线性算子`](https://optagent.pages.dev/guide/modeling/) 来确定图中每条边是否在割集中\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的最大割问题实例来自 [Biq Mac Library](http://biqmac.uni-klu.ac.at/biqmaclib.html)。最优解和每个数据集的描述可在此处找到 [此处](http://biqmac.uni-klu.ac.at/biqmaclib.pdf)。数据文件的格式如下：\n",
    "\n",
    "- 顶点数\n",
    "- 边数\n",
    "- 带边权重的邻接表\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "最大割问题的 OptAgent 模型使用 布尔决策变量 表示每个顶点是否属于子集 S。\n",
    "\n",
    "由其起点和终点顶点描述的一条边位于割集中，当且仅当恰好有一个顶点属于 S。使用非线性 **neq** 算子，我们确定每条边是否在割集中。然后我们可以计算目标函数的值，即割集中所有边的权重之和。\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",
    "def read_integers(filename):\n",
    "    return [int(elem) for elem in Path(filename).read_text(encoding=\"utf-8\").split()]\n",
    "\n",
    "#\n",
    "# Read instance data\n",
    "#\n",
    "def read_instance(filename):\n",
    "    file_it = iter(read_integers(filename))\n",
    "    # Number of vertices\n",
    "    n = next(file_it)\n",
    "    # Number of edges\n",
    "    m = next(file_it)\n",
    "\n",
    "    # Origin of each edge\n",
    "    origin = [None] * m\n",
    "    # Destination of each edge\n",
    "    dest = [None] * m\n",
    "    # Weight of each edge\n",
    "    w = [None] * m\n",
    "\n",
    "    for e in range(m):\n",
    "        origin[e] = next(file_it)\n",
    "        dest[e] = next(file_it)\n",
    "        w[e] = next(file_it)\n",
    "    \n",
    "    return n, m, origin, dest, w\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=10):\n",
    "    n, m, origin, dest, w = read_instance(instance_file)\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # x[i] is true when vertex i belongs to one side of the cut.\n",
    "    x = [model.bool() for i in range(n)]\n",
    "\n",
    "    # An edge is cut exactly when its endpoints are in different subsets.\n",
    "    incut = [\n",
    "        model.neq(x[origin[e] - 1], x[dest[e] - 1]) for e in range(m)\n",
    "    ]\n",
    "    cut_weight = model.sum(w[e] * incut[e] for e in range(m))\n",
    "    model.maximize(cut_weight)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    side = [int(bool(variable.value)) for variable in x]\n",
    "    print(\n",
    "        f\"Vertices = {n}; Edges = {m}; Cut weight = {cut_weight.value}; \"\n",
    "        f\"Status = {solution.feasible}\"\n",
    "    )\n",
    "    print(\"Side assignments:\", side)\n",
    "\n",
    "    if output_file is not None:\n",
    "        lines = [str(cut_weight.value)]\n",
    "        lines.extend(f\"{i + 1} {side[i]}\" for i in range(n))\n",
    "        Path(output_file).write_text(\"\\n\".join(lines) + \"\\n\", encoding=\"utf-8\")\n",
    "    return solution\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "以下代码格演示如何调用 OptAgent 的 Max-Cut 模型。\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_g05_60 = main(INSTANCE_DIR / \"g05_60.0\", time_limit=1)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_t2g10 = main(INSTANCE_DIR / \"t2g10_5555\", 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
}