如何在Pulp中为二进制变量添加二进制约束？装箱约束失效排查

问题核心 #

你的问题出在同长度物品必须放入同一箱子的约束逻辑未准确实现，导致不同长度物品混装。需要重新设计约束规则，强制同一长度的所有物品共享同一个箱子选择。

错误约束的常见问题 #

如果你的原有约束仅针对单个物品关联其长度与箱子的关系（比如x[item,k] <= y[length,k]但未限制同长度物品的箱子选择一致性），这种写法无法阻止同一长度的物品分散到不同箱子，也无法限制不同长度物品混装。

修正后的完整代码 #

import pulp

# 物品数据：(名称, 长度, 重量)
items = [
    ("item1", 10, 5),
    ("item2", 10, 5),
    ("item3", 20, 8),
    ("item4", 20, 8),
    ("item5", 20, 8)
]
max_weight_per_box = 30
max_boxes = 2

# 提取唯一长度类别
lengths = list(set(item[1] for item in items))
box_ids = list(range(max_boxes))

# 创建规划问题
prob = pulp.LpProblem("BinPacking", pulp.LpMinimize)

# 变量1：x[i,k] = 1 表示物品i放入箱子k
x = pulp.LpVariable.dicts(
    "ItemInBox",
    [(item[0], k) for item in items for k in box_ids],
    cat='Binary'
)

# 变量2：y[l,k] = 1 表示长度l的所有物品放入箱子k
y = pulp.LpVariable.dicts(
    "LengthInBox",
    [(l, k) for l in lengths for k in box_ids],
    cat='Binary'
)

# 目标函数：最小化使用的箱子数
prob += pulp.lpSum(y[l,k] for l in lengths for k in box_ids)

# 约束1：每个物品必须放入恰好一个箱子
for item in items:
    prob += pulp.lpSum(x[item[0], k] for k in box_ids) == 1

# 约束2：每个箱子总重量不超过上限
for k in box_ids:
    prob += pulp.lpSum(item[2] * x[item[0], k] for item in items) <= max_weight_per_box

# 约束3：同一长度的物品必须放入同一个箱子
# 子约束3.1：如果某物品放入箱子k，则该长度的所有物品都要放入k（通过y变量关联）
for item in items:
    item_name, l, _ = item
    for k in box_ids:
        prob += x[item_name, k] <= y[l, k]

# 子约束3.2：每个长度类别必须恰好选择一个箱子
for l in lengths:
    prob += pulp.lpSum(y[l, k] for k in box_ids) == 1

# 约束4：最多使用2个箱子
prob += pulp.lpSum(y[l,k] for l in lengths for k in box_ids) <= max_boxes

# 求解问题
prob.solve(pulp.PULP_CBC_CMD(msg=0))

# 输出结果
print("求解状态:", pulp.LpStatus[prob.status])
for k in box_ids:
    print(f"\n箱子{k}中的物品:")
    total_weight = 0
    for item in items:
        item_name = item[0]
        if pulp.value(x[item_name, k]) == 1:
            print(f"- {item_name} (长度:{item[1]}, 重量:{item[2]})")
            total_weight += item[2]
    print(f"总重量: {total_weight}")

关键约束解释 #

1. y[l,k]变量的作用：标记某长度类别的所有物品是否放入箱子k，确保同一长度的物品共享同一个箱子选择。
2. x[item_name, k] <= y[l, k]：如果某物品放入箱子k，那么该物品所属长度类别的y[l,k]必须为1，强制同长度的其他物品也只能放入k。
3. pulp.lpSum(y[l, k] for k in box_ids) == 1：每个长度类别必须恰好选择一个箱子，避免同长度物品分散或不装箱。

预期输出验证 #

运行修正后的代码，会得到符合要求的结果：

求解状态: Optimal

箱子0中的物品:

• item1 (长度:10, 重量:5)
• item2 (长度:10, 重量:5)
  总重量: 10

箱子1中的物品:

• item3 (长度:20, 重量:8)
• item4 (长度:20, 重量:8)
• item5 (长度:20, 重量:8)
  总重量: 24

所有同长度物品被分到同一箱子，且单箱重量不超过30，满足所有约束。

内容的提问来源于stack exchange，提问作者Tavish Aggarwal