随机装箱问题¶

类别： 装箱

使用 OptAgent 的 Python 接口描述变量、约束与目标。

问题与原始示例来源：Hexaly Code Templates。

问题描述¶

在随机装箱问题中，需要将一组物品划分到若干箱子中。没有容量约束，每个箱子可以装入任何物品。该问题的随机性来源于物品的重量是随机的。在本例中，随机性通过不同的场景来表示，每个场景对应一组可能的物品重量。对于给定的物品到箱子的分配方案，每个场景都有一个与之对应的最大箱重。

如何选取最合适的目标函数以最小化这种随机的最大重量是一个挑战。最小化平均最大重量可能掩盖有风险的场景，而最小化最坏场景下的最大重量又可能过于悲观。本例采用折中方案：最小化所有场景中最大箱重的第 90 百分位数。

学习要点¶

使用 OptAgent 的 set 决策变量表示各箱子所装物品
使用 partition 约束确保每个物品恰好进入一个箱子
使用集合 lambda 计算不同随机场景下每个箱子的总重量

数据¶

本例在程序运行时随机生成实例。首先为每个物品选择一个均匀分布，然后对每个场景，从相应的均匀分布中独立采样得到各物品的重量。固定随机种子可以复现实例。

建模思路¶

每个箱子使用一个 set 决策变量表示其物品集合，并通过 partition 约束保证所有箱子构成物品的一个划分。

对于每个场景，模型通过集合 lambda 汇总各箱子的物品重量，再取最大值作为该场景的最大箱重。将所有场景的最大箱重升序排序后，取索引 ceil(0.9 * (场景数 - 1)) 对应的值作为第 90 百分位目标并最小化。

Python 实现¶

import math
import random
from pathlib import Path

from optagent import OptModel, solve


def generate_scenarios(nb_items, nb_scenarios, seed):
    rng = random.Random(seed)

    item_distributions = []
    for _ in range(nb_items):
        item_min = rng.randint(10, 100)
        item_max = item_min + rng.randint(0, 50)
        item_distributions.append((item_min, item_max))

    return [
        [rng.randint(*distribution) for distribution in item_distributions]
        for _ in range(nb_scenarios)
    ]


def main(
    nb_items=10,
    nb_bins=2,
    nb_scenarios=3,
    seed=42,
    time_limit=2,
    output_file=None,
):
    scenario_item_weights_data = generate_scenarios(
        nb_items, nb_scenarios, seed
    )

    model = OptModel()

    # bins[k] contains the items assigned to bin k.
    bins = [model.set(nb_items) for k in range(nb_bins)]
    model.constraint(model.partition(bins))

    scenario_item_weights = model.array(scenario_item_weights_data)

    def make_weight_lambda(scenario):
        return model.lambda_function(
            lambda item: scenario_item_weights[scenario, item]
        )

    scenario_max_weights = []
    for scenario in range(nb_scenarios):
        weight_lambda = make_weight_lambda(scenario)
        bin_weights = [
            model.sum(bin_items, weight_lambda) for bin_items in bins
        ]
        scenario_max_weights.append(model.max(bin_weights))

    sorted_max_weights = model.sort(model.array(scenario_max_weights))
    percentile_index = math.ceil(0.9 * (nb_scenarios - 1))
    stochastic_max_weight = sorted_max_weights[percentile_index]
    model.minimize(stochastic_max_weight)

    solution = solve(model, time_limit_s=float(time_limit))
    if not solution.feasible:
        print(f"No feasible packing found; Status = {solution.status}")
        return solution

    bin_values = [sorted(int(item) for item in bin_items.value) for bin_items in bins]
    display_lines = [
        f"90th percentile maximum weight = {stochastic_max_weight.value}; "
        f"Status = {solution.status}",
        "",
        "Scenario item weights:",
    ]
    display_lines.extend(
        f"{scenario}: {weights}"
        for scenario, weights in enumerate(scenario_item_weights_data)
    )
    display_lines.extend(["", "Bins:"])
    display_lines.extend(
        f"{bin_index}: {items}"
        for bin_index, items in enumerate(bin_values)
    )
    result_text = "\n".join(display_lines)
    print(result_text)

    if output_file is not None:
        Path(output_file).write_text(result_text + "\n", encoding="utf-8")
    return solution

solution = main(
    nb_items=10,
    nb_bins=2,
    nb_scenarios=3,
    seed=42,
    time_limit=1,
)