{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# 钢厂板坯设计问题\n", "\n", "**类别：** 装箱\n", "\n", "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n", "\n", "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/steel-mill-slab-design-problem)。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 问题描述\n", "\n", "**在钢厂板坯设计问题中**，我们需要将钢铁订单的生产组织到板坯中。钢厂通过将铁水浇铸成板坯来生产钢材。钢厂可生产有限数量的板坯规格。每个订单具有两个属性：颜色（对应于钢厂中的某条工艺路径）和重量。板坯具有最大容量：分配给某块板坯的订单总重量不得超过该容量。此外，由于将板坯切割后再送往钢厂的不同工序代价高昂，因此每块板坯中所包含的不同颜色数量是有限制的（通常为两种）。目标是最小化钢材浪费，即生产出来但未被任何订单使用的钢材数量。更多详情请参见 [CSPLib](http://www.csplib.org/Problems/prob038/)。\n", "\n", "### 学习要点\n", "\n", "- 使用 OptAgent 的 `set` 决策变量表示分配给各板坯的订单集合\n", "- 使用 `partition` 约束确保每个订单恰好分配给一块板坯\n", "- 使用集合 lambda 动态计算板坯重量和不同颜色数量\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 数据\n", "\n", "数据文件的格式如下：\n", "\n", "- 第一行：板坯规格数以及所有可用的规格大小\n", "- 第二行：颜色种类数\n", "- 第三行：订单数量\n", "- 接下来每一行描述一个订单：订单的规格大小和颜色\n", "\n", "我们假设每块板坯最多只能包含两种不同颜色的订单。\n" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## 建模思路\n", "\n", "每块板坯使用一个 `set` 决策变量表示其订单集合，并通过 `partition` 约束使每个订单恰好属于一块板坯。\n", "\n", "模型使用集合 lambda 汇总每块板坯的订单重量，并约束其不超过最大板坯规格；同时通过 `distinct` 统计订单颜色，限制每块板坯最多包含两种颜色。板坯浪费量由预计算表给出，即能够容纳当前订单总重量的最小板坯规格减去订单总重量。目标是最小化所有板坯的总浪费量。\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 [\n", " int(value)\n", " for value in Path(filename).read_text(encoding=\"utf-8\").split()\n", " ]\n", "\n", "\n", "def read_instance(filename):\n", " values = iter(read_integers(filename))\n", " nb_slab_sizes = next(values)\n", " slab_sizes = [next(values) for _ in range(nb_slab_sizes)]\n", " nb_colors = next(values)\n", " nb_orders = next(values)\n", " quantities = []\n", " colors = []\n", " for _ in range(nb_orders):\n", " quantities.append(next(values))\n", " colors.append(next(values))\n", " return slab_sizes, nb_colors, quantities, colors\n", "\n", "\n", "def pre_compute_waste_for_content(slab_sizes, sum_size_orders):\n", " if slab_sizes != sorted(slab_sizes):\n", " raise ValueError(\"Slab sizes must be sorted in ascending order\")\n", "\n", " max_size = slab_sizes[-1]\n", " waste_for_content = [0] * (max(sum_size_orders, max_size) + 1)\n", " previous_size = 0\n", " for size in slab_sizes:\n", " for content in range(previous_size + 1, size):\n", " waste_for_content[content] = size - content\n", " previous_size = size\n", " return waste_for_content\n", "\n", "\n", "def main(input_file, output_file=None, time_limit=20):\n", " slab_sizes, _nb_colors, quantities_data, colors_data = read_instance(\n", " input_file\n", " )\n", " nb_colors_max_slab = 2\n", " nb_orders = len(quantities_data)\n", " nb_slabs = nb_orders\n", " max_size = slab_sizes[-1]\n", " waste_for_content = pre_compute_waste_for_content(\n", " slab_sizes, sum(quantities_data)\n", " )\n", "\n", " model = OptModel()\n", "\n", " colors = model.array(colors_data)\n", " quantities = model.array(quantities_data)\n", " color_lambda = model.lambda_function(lambda order: colors[order])\n", " quantity_lambda = model.lambda_function(lambda order: quantities[order])\n", "\n", " # Set decisions: slabs[s] contains the orders assigned to slab s.\n", " slabs = [\n", " model.set(nb_orders)\n", " for s in range(nb_slabs)\n", " ]\n", " model.constraint(model.partition(slabs))\n", "\n", " slab_contents = []\n", " for s, slab in enumerate(slabs):\n", " distinct_colors = model.distinct(slab, color_lambda)\n", " model.constraint(\n", " model.count(distinct_colors) <= nb_colors_max_slab,\n", " )\n", "\n", " slab_content = model.sum(slab, quantity_lambda)\n", " slab_contents.append(slab_content)\n", " model.constraint(\n", " slab_content <= max_size\n", " )\n", "\n", " waste_array = model.array(waste_for_content)\n", " wasted_steel = [waste_array[content] for content in slab_contents]\n", " total_wasted_steel = model.sum(*wasted_steel)\n", " model.minimize(total_wasted_steel)\n", "\n", " solution = solve(model, time_limit_s=float(time_limit))\n", " if not solution.feasible:\n", " print(f\"No feasible slab design found; Status = {solution.status}\")\n", " return solution\n", "\n", " used_slabs = [sorted(int(order) for order in slab.value) for slab in slabs]\n", " used_slabs = [orders for orders in used_slabs if orders]\n", "\n", " output_lines = [str(int(total_wasted_steel.value)), str(len(used_slabs))]\n", " for orders in used_slabs:\n", " output_lines.append(\n", " f\"{len(orders)} \" + \" \".join(str(order + 1) for order in orders)\n", " )\n", "\n", " result_text = \"\\n\".join(output_lines)\n", " print(f\"Status = {solution.status}\\n{result_text}\")\n", " if output_file is not None:\n", " Path(output_file).write_text(result_text + \"\\n\", encoding=\"utf-8\")\n", " return solution\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_12_orders = main(\n", " INSTANCE_DIR / \"12orderproblem.in\",\n", " time_limit=1,\n", ")\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solution_13_orders = main(\n", " INSTANCE_DIR / \"13orderproblem.in\",\n", " time_limit=1,\n", ")\n" ] }, { "cell_type": "code", "execution_count": null, "metadata": {}, "outputs": [], "source": [ "solution_14_orders = main(\n", " INSTANCE_DIR / \"14orderproblem.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 }