{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 货架装箱问题\n",
    "\n",
    "**类别：** 装箱\n",
    "\n",
    "使用 OptAgent 的 Python 接口描述变量、约束与目标。\n",
    "\n",
    "问题与原始示例来源：[Hexaly Code Templates](https://www.hexaly.com/templates/shelf-packing-problem)。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 问题描述\n",
    "\n",
    "在 Shelf Packing Problem 中，一组具有已知重量和已知类别的物品必须被分配到位于货架上的、具有统一容量的箱子中。货架上的总重量以及属于给定类别的物品数量均受到限制。目标是最小化用于放置所有物品的货架数量（第一个目标函数），然后最小化箱子数量（第二个目标函数）。该问题是 [Bin Packing Problem (BPP)](https://optagent.pages.dev/examples/packing/bin_packing_problem_bpp/) 的一个变种，因此是 NP-hard 的。\n",
    "\n",
    "### 学习要点\n",
    "\n",
    "- 使用 OptAgent 的 `set` 决策变量建模箱子的内容\n",
    "- 使用 `union` 表达货架上所有箱子的物品并集\n",
    "- 使用 `partition` 确保每个物品恰好放入一个箱子\n",
    "- 使用 `lambda_function` 计算箱子和货架的总重量\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 数据\n",
    "\n",
    "Shelf Packing Problem 实例是随机生成的 JSON 文件。它们由以下元素组成：\n",
    "\n",
    "- “nbItems”\n",
    "- “nbShelves”\n",
    "- “nbCategories”\n",
    "- “binCapacity”\n",
    "- “shelfCapacity”\n",
    "- “itemWeights”\n",
    "- “itemCategories”\n",
    "- “limitCategories”：limitCategories[c] 是货架 s 上类别 c 的最大物品数量\n",
    "- “binsAssignment”：binsAssignment[s] 是分配给货架 s 的箱子列表\n",
    "\n",
    "Python 示例使用标准库 `json` 读取实例数据。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 建模思路\n",
    "\n",
    "此处实现的 OptAgent 模型使用 `set` 决策变量。\n",
    "\n",
    "每个货架上有若干箱子。对每个货架，我们使用 `union` 定义其中所有箱子的物品并集。\n",
    "\n",
    "对于每个箱子，我们定义一个 `set` 来描述分配到该箱子中的物品。这些集合通过 `partition` 约束形成分区，确保每个物品恰好被分配到一个箱子。\n",
    "分配到一个箱子中的物品的重量之和不得超过箱子容量。\n",
    "货架上所有物品的重量之和不得超过货架容量。\n",
    "在任何货架上，给定类别的物品数量不得超过设定的限制。为此，我们对货架物品集合与该类别的物品数组执行 `intersection`，并将交集数量限制在 `limitCategories[c]` 以内。\n",
    "\n",
    "目标是首先最小化使用的货架数量（第一个目标），然后最小化使用的箱子数量（第二个目标）。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Python 实现\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import json\n",
    "from pathlib import Path\n",
    "\n",
    "from optagent import OptModel, solve\n",
    "\n",
    "\n",
    "def read_instance(instance_filename):\n",
    "    with open(instance_filename, encoding=\"utf-8\") as f:\n",
    "        return json.load(f)\n",
    "\n",
    "\n",
    "def main(input_file, output_file=None, time_limit=60):\n",
    "    data = read_instance(input_file)\n",
    "    nb_items = data[\"nbItems\"]\n",
    "    nb_categories = data[\"nbCategories\"]\n",
    "    nb_shelves = data[\"nbShelves\"]\n",
    "    bin_capacity = data[\"binCapacity\"]\n",
    "    shelf_capacity = data[\"shelfCapacity\"]\n",
    "    weights_data = data[\"itemWeights\"]\n",
    "    categories_data = data[\"itemCategories\"]\n",
    "    limit_categories = data[\"limitCategories\"]\n",
    "    bins_assignment = data[\"binsAssignment\"]\n",
    "    nb_max_bins = nb_items\n",
    "\n",
    "    model = OptModel()\n",
    "\n",
    "    # bins[k] is the set of items assigned to bin k.\n",
    "    bins = [model.set(nb_items) for k in range(nb_max_bins)]\n",
    "\n",
    "    # A shelf contains the union of the bins assigned to it by the instance.\n",
    "    shelves = [\n",
    "        model.union(bins[b] for b in bins_assignment[s])\n",
    "        for s in range(nb_shelves)\n",
    "    ]\n",
    "\n",
    "    # Every item must be assigned to exactly one bin.\n",
    "    model.constraint(model.partition(model.array(bins)))\n",
    "\n",
    "    weights = model.array(weights_data)\n",
    "    weight_lambda = model.lambda_function(lambda item: weights[item // 1])\n",
    "\n",
    "    bin_weights = [model.sum(bin_items, weight_lambda) for bin_items in bins]\n",
    "    for k, bin_weight in enumerate(bin_weights):\n",
    "        model.constraint(bin_weight <= bin_capacity)\n",
    "    bins_used = [model.count(bin_items) > 0 for bin_items in bins]\n",
    "\n",
    "    shelves_weights = [model.sum(shelf, weight_lambda) for shelf in shelves]\n",
    "    for s, shelf_weight in enumerate(shelves_weights):\n",
    "        model.constraint(\n",
    "            shelf_weight <= shelf_capacity,\n",
    "        )\n",
    "\n",
    "    # Limit the number of items of each category on every shelf.\n",
    "    for c in range(nb_categories):\n",
    "        items_per_category = [\n",
    "            i for i in range(nb_items) if categories_data[i] == c\n",
    "        ]\n",
    "        items_per_category_array = model.array(items_per_category)\n",
    "        for s, shelf in enumerate(shelves):\n",
    "            category_count = model.count(\n",
    "                model.intersection(shelf, items_per_category_array)\n",
    "            )\n",
    "            model.constraint(\n",
    "                category_count <= limit_categories[c],\n",
    "            )\n",
    "\n",
    "    shelves_used = [model.count(shelf) > 0 for shelf in shelves]\n",
    "    total_shelves_used = model.sum(shelves_used)\n",
    "    total_bins_used = model.sum(bins_used)\n",
    "\n",
    "    # Objectives are optimized lexicographically in declaration order.\n",
    "    model.minimize(total_shelves_used)\n",
    "    model.minimize(total_bins_used)\n",
    "\n",
    "    solution = solve(model, time_limit_s=float(time_limit))\n",
    "    if not solution.feasible:\n",
    "        print(f\"No feasible packing found; Status = {solution.status}\")\n",
    "        return solution\n",
    "\n",
    "    lines = [\n",
    "        f\"Shelves used = {total_shelves_used.value}; \"\n",
    "        f\"Bins used = {total_bins_used.value}; Status = {solution.status}\"\n",
    "    ]\n",
    "    for s in range(nb_shelves):\n",
    "        if not shelves_used[s].value:\n",
    "            continue\n",
    "        lines.append(\n",
    "            f\"Shelf {s} total weight: {shelves_weights[s].value}/{shelf_capacity}\"\n",
    "        )\n",
    "        for k in bins_assignment[s]:\n",
    "            if bins_used[k].value:\n",
    "                items = \" \".join(f\"#{item}\" for item in sorted(bins[k].value))\n",
    "                lines.append(\n",
    "                    f\"> Bin {k} weight: {bin_weights[k].value}/{bin_capacity} | \"\n",
    "                    f\"Items: {items}\"\n",
    "                )\n",
    "\n",
    "    result_text = \"\\n\".join(lines)\n",
    "    print(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": "markdown",
   "metadata": {},
   "source": [
    "## 本地运行\n",
    "\n",
    "Notebook 直接调用 `main` 并显式传入 JSON 实例路径。以下代码格相互独立，可以按需要单独运行；调整 `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_0 = main(\n",
    "    INSTANCE_DIR / \"instance_0.json\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_1 = main(\n",
    "    INSTANCE_DIR / \"instance_1.json\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_2 = main(\n",
    "    INSTANCE_DIR / \"instance_2.json\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_3 = main(\n",
    "    INSTANCE_DIR / \"instance_3.json\",\n",
    "    time_limit=1,\n",
    ")\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "solution_4 = main(\n",
    "    INSTANCE_DIR / \"instance_4.json\",\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
}