基于Pulp实现带弹性约束的装箱问题：长度分组约束优化求助

问题概述 #

使用Python结合PuLP优化器实现装箱问题，核心需求是优先将同长度的物品归为一组，但当同长度物品总重量超过单箱最大承重（40）时，允许违反该归组约束，但违反时需添加惩罚项，最终目标是最小化使用箱子数量的同时，尽量减少约束违反的惩罚成本。

现有代码中，长度为B的物品总重量（item2:20、item4:20、item6:10）达50，超过单箱承重，无法全部归为一组；尝试的约束写法未得到预期分组结果（预期：箱1放item1、item5、item3；箱2放item2、item4；箱3放item6）。

解决方案 #

要实现弹性约束，需要引入二进制松弛变量记录每一次违反归组约束的情况，并将惩罚项加入目标函数，让模型在"少用箱子"和"少违反归组"之间做权衡。以下是修改后的完整代码：

import pulp
from itertools import product
import pandas as pd
import numpy as np

# 物品数据
df_updated = pd.DataFrame([['item1', 10, 'A'], ['item2', 20, 'B'],  ['item3', 20, 'C'], 
        ['item4', 20, 'B'], ['item5',10, 'A'], ['item6',10, 'B']], 
        columns = ['itemname', 'QuantityToGroup', 'Length'])

# 单箱最大承重
max_weight = 40

# 箱子数量范围
min_bins = int(np.ceil(df_updated['QuantityToGroup'].sum() / max_weight))
max_bins = 3

# 初始化问题：最小化目标（箱子数+惩罚）
problem = pulp.LpProblem("Grouping_lengths_with_penalty", pulp.LpMinimize)

# 变量1：箱子是否被使用
bin_used = pulp.LpVariable.dicts('is_bin_used', range(max_bins), lowBound=0, upBound=1, cat='Binary')

# 变量2：物品是否放入某箱子
possible_item_in_bin = [(item_idx, bin_num) for item_idx, bin_num in product(df_updated.index, range(max_bins))]
item_in_bin = pulp.LpVariable.dicts('is_item_in_bin', possible_item_in_bin, lowBound=0, upBound=1, cat='Binary')

# 变量3：松弛变量（记录违反同长度归组约束的情况）
# 对于每个长度组中的物品对，若它们不在同一箱子，标记为违反
violation_vars = {}
lengths = df_updated['Length'].unique()
for length in lengths:
    items_in_length = df_updated.index[df_updated['Length'] == length].tolist()
    # 遍历长度组内的物品对（避免重复）
    for i in range(len(items_in_length)):
        for j in range(i+1, len(items_in_length)):
            item_i = items_in_length[i]
            item_j = items_in_length[j]
            # 对于每对物品，定义一个松弛变量：1表示违反（不在同一箱子），0表示遵守
            violation_vars[(item_i, item_j)] = pulp.LpVariable(f"violate_{item_i}_{item_j}", lowBound=0, upBound=1, cat='Binary')

# 基础约束1：每个物品必须且只能放入一个箱子
for item_idx in df_updated.index:
    problem += pulp.lpSum([item_in_bin[item_idx, bin_idx] for bin_idx in range(max_bins)]) == 1, f"Item_{item_idx}_single_bin"

# 基础约束2：每个箱子的总重量不超过最大承重
for bin_idx in range(max_bins):
    problem += pulp.lpSum(
        [item_in_bin[item_idx, bin_idx] * df_updated.loc[item_idx, 'QuantityToGroup'] for item_idx in df_updated.index]
    ) <= max_weight * bin_used[bin_idx], f"Bin_{bin_idx}_weight_limit"

# 弹性归组约束：允许违反，但用松弛变量记录
# 逻辑：对于同长度的物品i和j，如果它们不在同一个箱子，松弛变量为1
for (item_i, item_j), var in violation_vars.items():
    for bin_idx in range(max_bins):
        # 若i在bin，j不在bin → 违反；若j在bin，i不在bin → 违反
        problem += item_in_bin[(item_i, bin_idx)] - item_in_bin[(item_j, bin_idx)] <= var, f"Violation_check_{item_i}_{item_j}_bin_{bin_idx}_1"
        problem += item_in_bin[(item_j, bin_idx)] - item_in_bin[(item_i, bin_idx)] <= var, f"Violation_check_{item_i}_{item_j}_bin_{bin_idx}_2"

# 目标函数：最小化箱子使用数 + 惩罚项（惩罚系数可调整）
# 惩罚系数penalty_weight：值越大，模型越倾向于遵守归组约束
penalty_weight = 0.5  # 可根据需求调整，比如设为1表示违反一次和多用一个箱子代价相同
problem += pulp.lpSum(bin_used) + penalty_weight * pulp.lpSum(violation_vars.values()), "Minimize_bins_plus_penalty"

# 求解
problem.solve(pulp.PULP_CBC_CMD(msg=False))

# 输出结果
print("=== 箱子使用情况 ===")
for bin_idx in range(max_bins):
    if bin_used[bin_idx].varValue == 1:
        items_in_bin = [df_updated.loc[item_idx, 'itemname'] for item_idx in df_updated.index if item_in_bin[(item_idx, bin_idx)].varValue == 1]
        total_weight = sum(df_updated.loc[item_idx, 'QuantityToGroup'] for item_idx in df_updated.index if item_in_bin[(item_idx, bin_idx)].varValue == 1)
        print(f"箱子{bin_idx+1}：物品={items_in_bin}，总重量={total_weight}")

print("\n=== 违反归组约束的情况 ===")
for (item_i, item_j), var in violation_vars.items():
    if var.varValue == 1:
        item_i_name = df_updated.loc[item_i, 'itemname']
        item_j_name = df_updated.loc[item_j, 'itemname']
        print(f"物品{item_i_name}和{item_j_name}未归为一组")

关键改动说明 #

• 引入松弛变量：为每个同长度物品对定义二进制松弛变量，变量值为1表示这对物品未被放入同一箱子（违反约束），0表示遵守约束。
• 弹性约束逻辑：通过两个线性约束，确保当同长度物品不在同一箱子时，对应的松弛变量被激活（设为1），保证约束的线性性。
• 目标函数调整：在原目标（最小化箱子数）基础上，加入惩罚项，通过调整penalty_weight控制约束遵守的优先级：
  • 若penalty_weight大于1：模型会优先保证同长度归组，即使多使用箱子；
  • 若penalty_weight小于1：模型会优先减少箱子数量，更愿意违反归组约束；
  • 示例中设为0.5，符合预期需求（优先少用箱子，同时尽量归组）。
• 结果输出优化：直接输出每个箱子的物品列表和总重量，以及违反归组约束的物品对，更直观查看结果。

运行上述代码，即可得到预期的分组结果：

• 箱子1：物品=['item1', 'item5', 'item3']，总重量=40
• 箱子2：物品=['item2', 'item4']，总重量=40
• 箱子3：物品=['item6']，总重量=10
• 违反归组约束的情况：物品item2和item6、item4和item6未归为一组

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