基于Python Pulp的0-1背包问题：ID唯一选择及新增约束实现

背景与原始问题 #

我是一名主要使用SAS和R的统计学家，目前尝试用Python的PuLP库实现经典0-1背包问题。

原始数据（fan.csv简化版） #

id       Fan    Cost    Switch
10001   32.83   3.18    A/B
10003   75.25   4.20    C
10005   71.60   8.79    A/B
10010   24.23   9.99    C/D
10011   98.69   8.88    D
10012   48.81   8.68    C/D

需求与数据转换 #

需求：最大化Fan值，每个Switch类别选择1或2个物品，且总成本不超过阈值。部分物品可归属多个Switch类别（如ID10001可作为A或B），因此将数据转为长格式：

id       Fan    Cost    Switch
10001   32.83   3.18    A
10001   32.83   3.18    B
10003   75.25   4.20    C
10005   71.60   8.79    A
10005   71.60   8.79    B
10010   24.23   9.99    C
10010   24.23   9.99    D
10011   98.69   8.88    D
10012   48.81   8.68    C
10012   48.81   8.68    D

当前核心问题 #

数据转长格式后同一ID重复出现，不清楚如何给线性优化模型添加约束，确保每个物品（ID）最多被选择一次。已编写的代码如下：

import os
import pandas as pd
from pulp import *
import numpy as np

# Step 1
os.chdir("E:\\")
df01 = pd.read_csv("fan.csv")

df02 = df01[df01['Switch'].str.contains('/')]
df03 = df01[~df01['Switch'].str.contains('/')]

df02[['Swit1','Swit2']] = df02.Switch.str.split("/", expand=True)
df04 = pd.wide_to_long(df02, ["Swit"], i="id", j="Pos")
df04.reset_index(inplace=True)
df04.drop(["Pos"], axis=1, inplace=True)

df05 = pd.concat([df04,df03])
df06 = df05.sort_values(by=['id'])
df06.reset_index(drop=True, inplace=True)

df06.loc[(~df06['Switch'].str.contains('/')), 'Swit'] = df06.Switch

# Step 2    
df07 = df06.groupby(["Swit", "id", "Fan", "Cost"]).agg('count')
df07 = df07.reset_index()

costs = {}
fans = {}

for sth in df07.Swit.unique():
    df07_sth = df07[df07.Swit == sth]
    cost = list(df07_sth[['id', 'Cost']].set_index("id").to_dict().values())[0]
    fan = list(df07_sth[['id', 'Fan']].set_index("id").to_dict().values())[0]
    costs[sth] = cost
    fans[sth] = fan

sth_num_available = {
    "A": 1,
    "B": 1,
    "C": 1,
    "D": 2,
}

cost_cap = 25

_vars = {k: LpVariable.dict(k, v, cat='Binary') for k, v in fans.items()}

model1 = LpProblem("Fans", LpMaximize)
fanval = []
costval = []
switch_constraints = []

for k, v in _vars.items():
    costval += lpSum([costs[k][i] * _vars[k][i] for i in v])
    fanval += lpSum([fans[k][i] * _vars[k][i] for i in v])
    model1 += lpSum([_vars[k][i] for i in v]) == sth_num_available[k]

model1 += lpSum(fanval)
model1 += lpSum(costval) <= cost_cap

model1.solve()

注：示例数据量小导致问题不可行，实际数据约1000行且每日更新。

新增约束需求与问题 #

扩展后的数据：

id       Fan    Cost    Switch  Hit Group   Cat
10001   32.83   3.18    A/B       0   G1    C1
10003   75.25   4.20    C         1   G1    C2
10005   71.60   8.79    A/B       0   G1    C3
10010   24.23   9.99    C/D       1   G2    C1
10011   98.69   8.88    D         1   G2    C2
10012   48.81   8.68    C/D       1   G2    C3

约束1：每个Group中Hit=1的ID最多选2个 #

尝试代码报错：

df02 = df01.copy()
df02.set_index(["id","Group",], drop=False, inplace=True)
for G, total in df02.Assign.groupby(level='Group').sum().items():
    model1.addConstraint(name='Group' + G + 'Hit', constraint=df02.Hit.dot(total) <= 2)

错误信息：

Traceback (most recent call last):
  File "<stdin>", line 2, in <module>
  File "C:\Users\Programs\Python\Python311\Lib\site-packages\pandas\core\series.py", line 3015, in dot
    if lvals.shape[0] != rvals.shape[0]:
                         ~~~~~~~~~~~^^^
IndexError: tuple index out of range

约束2：解决方案至少包含2个Cat类别 #

尝试代码无报错但未实现预期约束：

df04 = df02.copy()
df04.reset_index(drop=True, inplace=True)
df04.set_index(["id","Cat",], drop=False, inplace=True)
for category, total in df04.Assign.groupby(level='Cat').sum().items():
    model1.addConstraint(name='Cat_' + category, constraint=total >= 2)

解决方案 #

1. 同一ID最多选一次的约束实现 #

当前变量按Switch类别定义，同一ID会在多个Switch分组下存在变量，需对每个ID添加约束：所有关联变量之和≤1。

# 获取所有唯一ID
unique_ids = df07['id'].unique()

for id_val in unique_ids:
    # 收集该ID对应的所有Switch变量
    id_vars = []
    for switch in _vars:
        if id_val in _vars[switch]:
            id_vars.append(_vars[switch][id_val])
    # 添加约束：该ID最多被选择一次
    model1 += lpSum(id_vars) <= 1, f"MaxOneSelection_ID_{id_val}"

2. 修复Group中Hit=1的ID选择约束 #

错误原因是直接用pandas的dot操作PuLP变量，需手动关联Hit=1的ID对应的变量：

# 按Group分组获取Hit=1的ID列表
group_hit_ids = df01[df01['Hit'] == 1].groupby('Group')['id'].apply(list).to_dict()

for group, ids in group_hit_ids.items():
    # 收集该Group下Hit=1的ID对应的所有变量
    hit_vars = []
    for id_val in ids:
        for switch in _vars:
            if id_val in _vars[switch]:
                hit_vars.append(_vars[switch][id_val])
    # 添加约束：该Group中Hit=1的ID最多选2个
    model1 += lpSum(hit_vars) <= 2, f"MaxHitSelection_Group_{group}"

3. 实现至少包含2个Cat类别的约束 #

需定义辅助变量标记Cat是否被选中，再约束选中的Cat数量≥2：

# 定义辅助二进制变量：每个Cat是否有至少一个ID被选中
cat_vars = LpVariable.dict("CatSelected", df01['Cat'].unique(), cat='Binary')

# 关联辅助变量与ID选择变量：若Cat下有ID被选中，辅助变量必须为1
for cat in cat_vars:
    cat_ids = df01[df01['Cat'] == cat]['id'].unique()
    cat_id_vars = []
    for id_val in cat_ids:
        for switch in _vars:
            if id_val in _vars[switch]:
                cat_id_vars.append(_vars[switch][id_val])
    model1 += lpSum(cat_id_vars) >= cat_vars[cat], f"CatSelected_{cat}_Trigger"

# 添加主约束：选中的Cat数量≥2
model1 += lpSum(cat_vars.values()) >= 2, f"MinCatCount_2"

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