1.2.1

下载 Notebook 下载完整案例

背包问题¶

类别： 装箱

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

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

问题描述¶

背包问题定义如下。考虑一组具有不同重量和价值的物品。我们需要选择一个物品子集放入一个已知容量的背包中。背包中物品的总重量不得超过其容量。目标是最大化背包中物品的总价值。

学习要点¶

• 了解 OptAgent 的建模方式：区分决策变量与中间表达式

数据¶

我们提供来自 OR Library 的实例。数据集的格式如下：

• 物品的数量
• 对每个物品，其重量
• 对每个物品，其价值
• 该实例的已知上界

建模思路¶

我们将背包问题建模为整数规划。对每个物品，我们定义一个 布尔决策变量，当物品被选中时为 1，否则为 0。我们使用 sum 算子计算被选中物品的总重量。注意，我们是从决策变量的值推导出这个值：总重量是一个中间表达式，而非决策变量。定义它之后，我们可以约束总重量小于背包的容量。类似地，我们定义另一个中间表达式，对应于被选中物品的总价值。最后，我们最大化该总价值。

Python 实现¶

from pathlib import Path

from optagent import OptModel, solve


def read_instance(filename):
    values = [int(value) for value in Path(filename).read_text(encoding="utf-8").split()]
    iterator = iter(values)
    nb_items = next(iterator)
    weights = [next(iterator) for _ in range(nb_items)]
    profits = [next(iterator) for _ in range(nb_items)]
    knapsack_capacity = next(iterator)
    return nb_items, weights, profits, knapsack_capacity


def main(input_file, output_file=None, time_limit=20):
    nb_items, weights, profits, knapsack_capacity = read_instance(input_file)
    model = OptModel()

    # x[i] is true when item i is selected.
    selected = [model.bool() for i in range(nb_items)]

    # Keep the original Hexaly formulation: weight and value are intermediate expressions.
    knapsack_weight = model.sum(
        selected[i] * weights[i] for i in range(nb_items)
    )
    model.constraint(knapsack_weight <= knapsack_capacity)

    knapsack_value = model.sum(
        selected[i] * profits[i] for i in range(nb_items)
    )
    model.maximize(knapsack_value)

    solution = solve(model, time_limit_s=float(time_limit))
    selected_items = [
        i for i, variable in enumerate(selected) if variable.value
    ]
    print(
        f"Items = {nb_items}; Capacity = {knapsack_capacity}; "
        f"Weight = {knapsack_weight.value}; Value = {knapsack_value.value}; "
        f"Status = {solution.feasible}"
    )
    print("Selected items:", selected_items)

    if output_file is not None:
        Path(output_file).write_text(
            f"{knapsack_value.value}\n"
            + " ".join(map(str, selected_items))
            + "\n",
            encoding="utf-8",
        )
    return solution

本地运行¶

以下代码格演示如何调用 OptAgent 背包模型。

INSTANCE_DIR = Path.cwd() / "instances"
print("Instances:", INSTANCE_DIR)

solution_toy = main(INSTANCE_DIR / "toy.in", time_limit=1)

solution_100_1 = main(INSTANCE_DIR / "kp_100_1.in", time_limit=1)