{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "7fb27b941602401d91542211134fc71a",
   "metadata": {},
   "source": [
    "# 切割下料问题\n",
    "\n",
    "**类别：** 装箱\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/cutting-stock-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "acae54e37e7d407bbb7b55eff062a284",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "在切割下料问题中,我们必须从具有固定尺寸的大卷材(或板材)上切割出宽度和高度各不相同的矩形物品。切割遵循一个结构化的两级切断模式:\n",
    "\n",
    "- **条带 (Bands)**:具有相同宽度的物品沿其高度方向并排排列,形成水平条带。每个条带具有固定的宽度(即该物品的共同宽度),其总长度等于所有物品高度之和。\n",
    "- **卷材 (Rolls)**:条带随后被垂直堆叠在卷材内。一个卷材内所有条带的总宽度不能超过卷材的宽度。同样地,每个条带的长度必须能放入卷材的长度内。\n",
    "\n",
    "目标是最小化所使用的卷材数量。\n",
    "\n",
    "### 学到的要点\n",
    "\n",
    "- 使用 **两层集合决策变量** 来建模一个分层装箱结构(物品放入条带,条带放入卷材)\n",
    "- 对集合使用 **distinct 算子** 配合一个 lambda,以强制一个条带内的所有物品共享相同的宽度\n",
    "- **用三元运算符保护对集合的 max 操作**(count(s) > 0 ? max(s, ...) : 0)以避免空集上的 NaN 问题\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9a63283cbaf04dbcab1f6479b197f3a8",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "我们提供的切割下料实例来自 [2DPackLib](https://site.unibo.it/operations-research/en/research/2dpacklib) 中的 A 类实例。数据文件的格式如下:\n",
    "\n",
    "- 第一行:物品种类数\n",
    "- 第二行:卷材宽度、卷材长度\n",
    "- 对每种物品类型:宽度、高度、需求\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8dd0d8092fe74a7c96281538738b07e2",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "切割下料问题的 OptAgent 模型使用两层 [集合决策变量](https://optagent.pages.dev/guide/modeling/)。在第一层,对于每个条带,我们定义一个集合变量来表示分配到该条带的物品。在第二层,对于每个卷材,我们定义一个集合变量来表示分配到该卷材的条带。两层都使用 partition 约束以确保每个物品恰好属于一个条带,且每个条带恰好属于一个卷材。\n",
    "\n",
    "在每个条带内,所有物品必须共享相同的宽度。这通过 distinct 算子配合一个 lambda 函数来强制:`distinct(bands[b], (i) => rawWidth[i])` 返回该条带中不同的宽度集合,我们将其数量约束为不超过 1。我们使用可变参 sum 算子将物品高度累加作为条带长度,并约束每个条带的长度不超过卷材长度。在卷材层,我们使用可变参 sum 算子对卷材的条带集合配合返回每个条带宽度的 lambda 函数来计算条带的总宽度,并约束其不超过卷材宽度。\n",
    "\n",
    "模型对卷材数量计算一个简单的下界(物品总面积除以卷材面积),并使用 objective threshold 在达到该下界时提前停止。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "72eea5119410473aa328ad9291626812",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8edb47106e1a46a883d545849b8ab81b",
   "metadata": {},
   "outputs": [],
   "source": [
    "import math\n",
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "\n",
    "def read_integers(filename):\n",
    "    with Path(filename).open(encoding=\"utf-8\") as file:\n",
    "        return [int(value) for value in file.read().split()]\n",
    "\n",
    "\n",
    "def read_instance(filename):\n",
    "    values = read_integers(filename)\n",
    "    iterator = iter(values)\n",
    "    types, roll_width, roll_length = next(iterator), next(iterator), next(iterator)\n",
    "    widths, lengths = [], []\n",
    "    for _ in range(types):\n",
    "        width, length, demand = next(iterator), next(iterator), next(iterator)\n",
    "        widths.extend([width] * demand)\n",
    "        lengths.extend([length] * demand)\n",
    "    return roll_width, roll_length, widths, lengths\n",
    "\n",
    "\n",
    "def main(instance_file, output_file=None, time_limit=10):\n",
    "    roll_width, roll_length, widths_data, lengths_data = read_instance(instance_file)\n",
    "    n = len(widths_data)\n",
    "    nb_max_bands = n\n",
    "    nb_max_rolls = n\n",
    "    min_number_of_rolls = math.ceil(\n",
    "        sum(widths_data[i] * lengths_data[i] for i in range(n))\n",
    "        / (roll_width * roll_length)\n",
    "    )\n",
    "\n",
    "    model = OptModel()\n",
    "    bands = [model.set(n) for index in range(nb_max_bands)]\n",
    "    rolls = [model.set(nb_max_bands) for index in range(nb_max_rolls)]\n",
    "    model.constraint(model.partition(bands))\n",
    "    model.constraint(model.partition(rolls))\n",
    "    widths, lengths = model.array(widths_data), model.array(lengths_data)\n",
    "    band_widths, band_lengths = [], []\n",
    "    for band in bands:\n",
    "        # 条带内物品总长度不能超过卷材长度\n",
    "        length = model.sum(band, model.lambda_function(lambda item: lengths[item]))\n",
    "        model.constraint(length <= roll_length)\n",
    "        # 一个条带里的所有物品宽度都相同\n",
    "        distinct = model.distinct(band, model.lambda_function(lambda item: widths[item]))\n",
    "        model.constraint(model.count(distinct) <= 1)\n",
    "        band_widths.append(model.iif(\n",
    "            band.count() > 0,\n",
    "            model.max(band, model.lambda_function(lambda item: widths[item])),\n",
    "            0,\n",
    "        ))\n",
    "        band_lengths.append(length)\n",
    "    band_width_array = model.array(band_widths)\n",
    "    roll_used, total_width = [], []\n",
    "    for roll in rolls:\n",
    "        # 条带宽度总和不能超过卷材宽度\n",
    "        width = model.sum(roll, model.lambda_function(lambda band: band_width_array[band]))\n",
    "        model.constraint(width <= roll_width)\n",
    "        total_width.append(width)\n",
    "        roll_used.append(roll.count() > 0)\n",
    "    used_rolls = model.sum(*roll_used)\n",
    "    model.minimize(used_rolls)\n",
    "    solution = solve(\n",
    "        model,\n",
    "        time_limit_s=float(time_limit),\n",
    "        objective_threshold={0: min_number_of_rolls},\n",
    "    )\n",
    "    values = {'used_rolls': used_rolls.value, **{f'band_{i}': band.value for i, band in enumerate(bands)}, **{f'roll_{i}': roll.value for i, roll in enumerate(rolls)}, **{f'band_width_{i}': width.value for i, width in enumerate(band_widths)}, **{f'band_length_{i}': length.value for i, length in enumerate(band_lengths)}, **{f'roll_width_{i}': width.value for i, width in enumerate(total_width)}}\n",
    "    lines = []\n",
    "    for index in range(nb_max_rolls):\n",
    "        bands_in_roll = sorted(int(band) for band in values[f\"roll_{index}\"])\n",
    "        if not bands_in_roll:\n",
    "            continue\n",
    "        lines.append(f\"Roll {index} | width: {int(values[f'roll_width_{index}'])}/{roll_width}\")\n",
    "        for band_index in bands_in_roll:\n",
    "            items = sorted(int(item) for item in values[f\"band_{band_index}\"])\n",
    "            if items:\n",
    "                lines.append(\n",
    "                    f\"  Band width={int(values[f'band_width_{band_index}'])} \"\n",
    "                    f\"length={int(values[f'band_length_{band_index}'])} | Items: \"\n",
    "                    + \" \".join(str(item) for item in items)\n",
    "                )\n",
    "    header = (\n",
    "        f\"Number of rolls used: {int(values['used_rolls'])}; \"\n",
    "        f\"Min rolls: {min_number_of_rolls}; Status = {solution.feasible}\"\n",
    "    )\n",
    "    print(header)\n",
    "    for line in lines:\n",
    "        print(line)\n",
    "    if output_file is not None:\n",
    "        Path(output_file).write_text(header + \"\\n\" + \"\\n\".join(lines) + \"\\n\", encoding=\"utf-8\")\n",
    "    return solution"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "10185d26023b46108eb7d9f57d49d2b3",
   "metadata": {},
   "source": [
    "## 本地运行\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "8763a12b2bbd4a93a75aff182afb95dc",
   "metadata": {},
   "outputs": [],
   "source": [
    "INSTANCE_DIR = Path.cwd() / \"instances\""
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "7623eae2785240b9bd12b16a66d81610",
   "metadata": {},
   "outputs": [],
   "source": [
    "solution = main(INSTANCE_DIR / \"A1.txt\", time_limit=10)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "73e5c591",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "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
}