如何在PuLP中构建约束实现物品按天数升序分组？

原代码的核心问题是缺少强制天数升序分组的约束，仅通过最小化箱子天数总和与使用数量的目标函数，无法避免天数大的物品混入小编号箱子的情况。以下是修正后的约束构建方案：

关键修改点 #

• 新增物品-箱子映射变量：创建item_bin变量，直接记录每个物品对应的箱子编号，简化约束逻辑。
• 关联映射变量与分配变量：确保item_bin与item_in_bin的取值一致，保证变量逻辑正确性。
• 添加升序分组约束：利用物品已按天数升序排序的前提，强制索引小的物品（天数更小）所在箱子编号不大于索引大的物品（天数更大）的箱子编号。

完整修正代码 #

from itertools import product
import pandas as pd
import pulp

df = pd.DataFrame([["item0", 9, 6],["item1", 9, 8],["item2", 9, 1],
    ["item3", 1, 7],["item4", 1, 3],["item5", 9, 5]], columns=["itemname", "Quantity", "Days"])

# 按天数升序排序，重置索引
df = df.sort_values('Days').reset_index(drop = True)
max_weight = 20
max_bins = 4
bin_penalty = 5
day_penalty = 10
bins = list(range(max_bins))

problem = pulp.LpProblem("sort_item_ascending", pulp.LpMinimize)

bin_used = pulp.LpVariable.dicts("is_bin_used", bins, cat="Binary")

# 物品-箱子分配变量
possible_item_in_bin = [(item_index, bin_num) for item_index, bin_num in product(df.index, bins)]
item_in_bin = pulp.LpVariable.dicts("is_item_in_bin", possible_item_in_bin, cat="Binary")

# 约束1：每个物品仅放入一个箱子
for item_index in df.index:
    problem += (pulp.lpSum([item_in_bin[item_index, bin_index] for bin_index in bins]) == 1,
        f"Ensure_item_{item_index}_single_bin")

# 约束2：每个箱子承重不超过最大值
for bin_index in bins:
    problem += (pulp.lpSum(
            [ item_in_bin[item_index, bin_index] * df.loc[item_index, "Quantity"] for item_index in df.index ]
        ) <= max_weight * bin_used[bin_index],
        f"Bin_{bin_index}_weight_limit")

# -------------------------- 新增升序分组约束部分 --------------------------
# 新增变量：记录每个物品对应的箱子编号
item_bin = pulp.LpVariable.dicts("item_bin", df.index, lowBound=0, upBound=max_bins-1, cat='Integer')

# 约束3：关联item_bin与item_in_bin，保证变量取值一致
for item_idx in df.index:
    problem += item_bin[item_idx] == pulp.lpSum([b * item_in_bin[item_idx, b] for b in bins]), \
        f"Item_{item_idx}_bin_mapping"

# 约束4：强制天数升序分组（索引小的物品，箱子编号不大于索引大的物品）
for i in df.index:
    for j in df.index:
        if i < j:
            problem += item_bin[i] <= item_bin[j], f"Group_order_{i}_le_{j}"
# -------------------------- 新增约束结束 --------------------------

# 目标函数：最小化箱子使用数量 + 箱子天数总和（加权）
total_days_per_bin = pulp.LpVariable.dicts("total_days", bins, cat='Integer')
for b in bins:
    problem += total_days_per_bin[b] == pulp.lpSum([item_in_bin[item_idx, b] * df.loc[item_idx, "Days"] for item_idx in df.index])

problem += (
    day_penalty * pulp.lpSum(total_days_per_bin[b] for b in bins) + bin_penalty * pulp.lpSum(bin_used[b] for b in bins),
    "Minimize_bins_and_days"
)

# 求解问题
problem.solve(pulp.PULP_CBC_CMD(msg=True))

# 分配结果到DataFrame
for idx, b in possible_item_in_bin:
    if item_in_bin[idx, b].varValue == 1:
        df.loc[idx, 'bin'] = b

print(df)

效果说明 #

运行修正后的代码后，物品会严格按照天数升序分配到箱子中（不会出现天数6的item0进入bin2而天数更小的物品在bin0/bin1的情况），同时满足每个箱子的承重限制。

内容的提问来源于stack exchange，提问作者Aakash Parsi