{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 装箱问题(BPP)\n", "\n", "**类别：** 装箱\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/bin-packing-problem-bpp)。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 问题描述\n", "\n", "**在装箱问题(Bin Packing Problem, BPP)**中,若干已知重量的物品必须被分配到具有相同容量的箱子中。每个物品必须恰好放入一个箱子中,且每个箱子内物品的总重量不得超过其容量。目标是最小化所使用的箱子数量。\n", "\n", "### 学习要点\n", "\n", "- 添加 [集合决策变量](https://optagent.pages.dev/guide/modeling/) 以建模每个箱子内的物品\n", "- 定义一个 [lambda 函数](https://optagent.pages.dev/guide/modeling/) 来计算每个箱子的总重量\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 数据\n", "\n", "所提供的装箱问题(BPP)算例来自 [BPPLIB](http://or.dei.unibo.it/library/bpplib) 中的 Falkenauer 算例。数据文件的格式如下:\n", "\n", "- 第一行:物品数量\n", "- 第二行:箱子容量\n", "- 接下来每一行对应一个物品的重量\n" ] }, { "cell_type": "markdown", "id": "dddde02b", "metadata": {}, "source": [ "## 建模思路\n", "\n", "装箱问题(BPP)的 OptAgent 模型使用 [集合决策变量](https://optagent.pages.dev/guide/modeling/)。对每个箱子,我们定义一个集合变量,表示分配到该箱子中的物品集合。我们对集合变量施加划分约束,以确保每个物品恰好被放入一个箱子中。\n", "\n", "我们使用集合上的可变参数 **sum** 算子,以及一个返回任意物品索引对应重量的 [lambda 函数](https://optagent.pages.dev/guide/modeling/),来计算每个箱子的总重量。请注意,该 sum 中的项数在搜索过程中会变化,因为集合的大小可以变化。\n", "\n", "当一个箱子至少包含一个物品时,它才被实际使用。借助 **count** 算子(返回集合中的元素数量),我们可以检查每个箱子是否被实际使用,从而计算所使用的箱子总数。\n", "\n", "该模型对最优箱子数量计算了简单的下界与上界。它仅定义 nbMaxBins 个集合变量,并使用 [`solve(..., objective_threshold=...)`](https://optagent.pages.dev/api/solve/) 在找到使用不超过该下界的箱子的解时停止搜索。\n" ] }, { "cell_type": "markdown", "id": "527e816a", "metadata": {}, "source": [ "## Python 实现\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bpp-model", "metadata": {}, "outputs": [], "source": [ "import math\n", "from pathlib import Path\n", "\n", "from optagent import OptModel, solve\n", "\n", "\n", "\n", "\n", "def read_integers(filename):\n", " with open(filename) as f:\n", " return [int(elem) for elem in f.read().split()]\n", "\n", "\n", "def main(input_file, output_file=None, time_limit=50):\n", " file_it = iter(read_integers(input_file))\n", " nb_items = int(next(file_it))\n", " bin_capacity = int(next(file_it))\n", " weights_data = [int(next(file_it)) for _ in range(nb_items)]\n", "\n", " nb_min_bins = int(math.ceil(sum(weights_data) / float(bin_capacity)))\n", " nb_max_bins = min(nb_items, 2 * nb_min_bins)\n", "\n", " #\n", " # Declare the optimization model\n", " #\n", " model = OptModel()\n", "\n", " # Set decisions: bins[k] represents the items in bin k\n", " bins = [model.set(nb_items) for k in range(nb_max_bins)]\n", "\n", " # Each item must be in one bin and one bin only\n", " model.constraint(model.partition(bins))\n", "\n", " # Create an array and a function to retrieve the item's weight\n", " weights = model.array(weights_data)\n", " weight_lambda = model.lambda_function(lambda i: model.at(weights, i))\n", "\n", " # Weight constraint for each bin\n", " bin_weights = [model.sum(b, weight_lambda) for b in bins]\n", " for w in bin_weights:\n", " model.constraint(w <= bin_capacity)\n", "\n", " # Bin k is used if at least one item is in it\n", " bins_used = [model.count(b) > 0 for b in bins]\n", "\n", " # Count the used bins\n", " total_bins_used = model.sum(*bins_used)\n", "\n", " # Minimize the number of used bins\n", " model.minimize(total_bins_used)\n", "\n", " # Stop once the first objective reaches the trivial lower bound\n", " solution = solve(\n", " model,\n", " time_limit_s=float(time_limit),\n", " objective_threshold={0: nb_min_bins},\n", " )\n", " result_values = {'total_bins_used': total_bins_used.value, **{f'bin_{k}': bin_var.value for k, bin_var in enumerate(bins)}}\n", "\n", " lines = []\n", " for k in range(nb_max_bins):\n", " items = sorted(int(item) for item in result_values[f\"bin_{k}\"])\n", " if not items:\n", " continue\n", " weight_value = int(sum(weights_data[i] for i in items))\n", " line = f\"Bin weight: {weight_value} | Items: \" + \" \".join(str(i) for i in items)\n", " lines.append(line)\n", "\n", " header = (\n", " f\"Nb items = {nb_items}; Bin capacity = {bin_capacity}; \"\n", " f\"Min bins = {nb_min_bins}; Total bins used = {int(result_values['total_bins_used'])}; \"\n", " f\"Status = {solution.feasible}\"\n", " )\n", " print(header)\n", " for line in lines:\n", " print(line)\n", "\n", " if output_file is not None:\n", " with Path(output_file).open(\"w\", encoding=\"utf-8\") as f:\n", " f.write(header + \"\\n\")\n", " f.write(\"\\n\".join(lines) + \"\\n\")\n", " return solution\n" ] }, { "cell_type": "markdown", "id": "bpp-runs", "metadata": {}, "source": [ "## 本地运行\n", "\n", "Notebook 直接调用 `main` 并显式传入实例路径。以下代码格相互独立，可以按需要单独运行；调整 `time_limit` 可以控制每个实例的求解时间。\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bpp-instance-dir", "metadata": {}, "outputs": [], "source": [ "from pathlib import Path\n", "\n", "INSTANCE_DIR = Path.cwd() / \"instances\"\n", "print(\"Instances:\", INSTANCE_DIR)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bpp-run-t120-00", "metadata": {}, "outputs": [], "source": [ "solution_t120_00 = main(INSTANCE_DIR / \"t120_00.txt\", time_limit=1)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bpp-run-t120-05", "metadata": {}, "outputs": [], "source": [ "solution_t120_05 = main(INSTANCE_DIR / \"t120_05.txt\", time_limit=1)\n" ] }, { "cell_type": "code", "execution_count": null, "id": "bpp-run-u120-00", "metadata": {}, "outputs": [], "source": [ "solution_u120_00 = main(INSTANCE_DIR / \"u120_00.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 }