基于Pulp的组合优化：百万级工厂分配的大规模数据集求解问题

现有基于Pulp的实现仅能处理少量工厂（如5个）的最优产品（a或b）分配，但当工厂数量达到50左右时求解就无法完成（比如含205个工厂的data2数据集），需要支持约100万个工厂的求解需求。

问题目标为总成本最小化，成本包含两部分：

• 产品单位成本
• 排放超限费用：排放按产品维度汇总计算，若有N个工厂分配至产品a，则该产品总排放限额为N×limit_a，超出部分按echarge_a计费；产品b规则同理。

现有实现代码 #

# factory picker

import pulp

data = {
    'f1': (1.2,),
    'f2': (1.0,),
    'f3': (1.7,),
    'f4': (1.8,),
    'f5': (1.6,)
}

unit_cost = {'a': 5, 'b': 8}
limit = {'a': 60, 'b': 100}
echarge = {'a': 0.007, 'b': 0.004}

# 辅助变量
factories = list(data.keys())
products = ['a', 'b']
fp = [(f, p) for f in factories for p in products]

### 问题初始化
prob = pulp.LpProblem('factory_assignments', pulp.LpMinimize)

### 变量定义
# make[factory, product] 为1表示该工厂生产对应产品，0则不生产
make = pulp.LpVariable.dicts('make', fp, cat=pulp.LpBinary)

# 各产品的超限排放费用
emission = pulp.LpVariable.dicts('emission', products, lowBound=0)

### 目标函数
# 总单位成本
tot_unit_cost = sum(unit_cost[p] * make[f, p] for f, p in fp)

# 总成本 = 总单位成本 + 总超限排放费用
prob += tot_unit_cost + sum(emission[p] for p in products)

### 约束条件
# 处理排放超限的线性约束：emission[p] >= （实际总排放 - 限额）* 计费标准，结合lowBound=0实现max(0, ...)效果
for p in products:
    prob += emission[p] >= sum(make[f, p] * (data[f][0] - limit[p]) for f in factories) * echarge[p] * 31

# 每个工厂必须且只能生产一种产品
for f in factories:
    prob += sum(make[f, p] for p in products) == 1

### 输出问题结构用于验证
print(prob)

### 求解
soln = prob.solve()

# 输出分配结果
for f, p in fp:
    if make[f, p].varValue:   # 值为1时表示分配该产品
        print(f'make {p} in factory {f}')

print(f'tot unit cost: {pulp.value(tot_unit_cost)}')

for p in products:
    print(f'emission cost for {p} is: {emission[p].varValue}')

大规模测试数据集 #

data2=[0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       0.0000000e+00, 0.0000000e+00, 0.0000000e+00, 0.0000000e+00,
       2.9000000e-03, 4.1000000e-02, 5.0000000e-02, 5.0000000e-02,
       5.0000000e-02, 5.0000000e-02, 9.9600000e-02, 1.0000000e-01,
       1.0000000e-01, 1.0000000e-01, 1.0000000e-01, 1.0000000e-01,
       1.0000000e-01, 1.0000000e-01, 1.0000000e-01, 1.0000000e-01,
       1.3080000e-01, 1.5000000e-01, 1.9530000e-01, 2.0410000e-01,
       2.6460000e-01, 3.3200000e-01, 4.0000000e-01, 4.8920000e-01,
       5.9270000e-01, 7.4900000e-01, 1.0000000e+00, 1.2304000e+00,
       1.6982000e+00, 2.0000000e+00, 2.0000000e+00, 2.0000000e+00,
       2.0000000e+00, 2.0000000e+00, 2.0000000e+00, 2.0000000e+00,
       2.0500000e+00, 2.0500000e+00, 2.0500000e+00, 2.0500000e+00,
       2.1000000e+00, 2.1308000e+00, 2.2000000e+00, 2.3476000e+00,
       2.6386000e+00, 3.0332000e+00, 3.4218000e+00, 4.0000000e+00,
       4.0000000e+00, 4.0000000e+00, 4.0500000e+00, 4.1000000e+00,
       4.1500000e+00, 4.2978000e+00, 4.6630000e+00, 5.1240000e+00,
       5.6640000e+00, 6.0000000e+00, 6.0500000e+00, 6.1500000e+00,
       6.4658000e+00, 7.0000000e+00, 7.4410000e+00, 8.0000000e+00,
       8.1000000e+00, 8.3500000e+00, 8.9414000e+00, 9.4960000e+00,
       1.0031600e+01, 1.0291000e+01, 1.0933500e+01, 1.1585100e+01,
       1.2100000e+01, 1.2735700e+01, 1.3531200e+01, 1.4169500e+01,
       1.5000000e+01, 1.5985300e+01, 1.6753900e+01, 1.7894500e+01,
       1.8880200e+01, 2.0076900e+01, 2.1259500e+01, 2.2545500e+01,
       2.4053700e+01, 2.5606200e+01, 2.7227700e+01, 2.9049800e+01,
       3.1036700e+01, 3.3092700e+01, 3.5307800e+01, 3.7707200e+01,
       4.0306600e+01, 4.3051700e+01, 4.5969700e+01, 4.9029100e+01,
       5.2323200e+01, 5.5997000e+01, 5.9875500e+01, 6.4000000e+01,
       6.8299200e+01, 7.3040000e+01, 7.8102900e+01, 8.3400000e+01,
       8.8983700e+01, 9.5201100e+01, 1.0167750e+02, 1.0873550e+02,
       1.1608100e+02, 1.2402830e+02, 1.3227530e+02, 1.4071130e+02,
       1.5020780e+02, 1.6034020e+02, 1.7100620e+02, 1.8246580e+02,
       1.9532960e+02, 2.0884600e+02, 2.2325970e+02, 2.3874330e+02,
       2.5563800e+02, 2.7392080e+02, 2.9362100e+02, 3.1453630e+02,
       3.3796300e+02, 3.6373040e+02, 3.9154620e+02, 4.2200780e+02,
       4.5533300e+02, 4.9321970e+02, 5.3590330e+02, 5.8393730e+02,
       6.4024060e+02, 7.0435050e+02, 7.8055390e+02, 8.7628510e+02,
       9.9769820e+02, 1.1596923e+03, 1.4036132e+03, 1.8536339e+03,
       3.2332685e+03]

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