MCKP问题使用PuLP实现能否提速？现有求解代码求优化建议

问题背景 #

当使用PuLP求解带有大量约束的MCKP问题（N=10000客户，M=12产品）时，代码运行耗时超过30秒，以下是针对性的优化建议和PuLP的更快实现方案。

原始代码 #

import pulp
import numpy as np
import time

def func(N,M,V,T):
    t0 = time.time()
    # Problem Definition
    prob = pulp.LpProblem("MCKP", pulp.LpMaximize)

    # Define the X needed to be solved ---- which has N customers, M products
    X = [[pulp.LpVariable(f"X_{i}_{j}", lowBound=0, upBound=1, cat=pulp.LpInteger)
        for j in range(M)] for i in range(N)]

    # Define the optimization object ---- maximize the total Value
    obj = pulp.LpAffineExpression()
    for i in range(N):
        for j in range(M):
            obj += X[i][j] * V[i][j]
    prob += obj

    # Define the constraints 
    for i in range(N):
        prob += pulp.lpSum(X[i]) == 1   #Each customer must select 1 product
    for i in range(M):
        prob += pulp.lpSum([X[k][i] for k in range(N)]) == T[i]  #Each product must be selected by certain number of customers

    prob.solve()
    t1 = time.time()
    print("Used: {}".format(int(t1 - t0)))

N=10000 #N customers
M=12    #M products
V=np.random.random((N,M))  #Products's value to customers
T=[800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 800, 1200]  #Constraints
func(N,M,V,T)

优化建议 #

1. 变量定义优化

避免使用嵌套列表生成式创建变量，改用pulp.LpVariable.dicts，其内部实现更高效，能减少变量创建的开销：

X = pulp.LpVariable.dicts(
    "X",
    ((i, j) for i in range(N) for j in range(M)),
    lowBound=0,
    upBound=1,
    cat=pulp.LpInteger
)

2. 目标函数构建优化

手动双重循环构建LpAffineExpression会产生额外的Python层开销，直接用lpSum包裹生成器表达式，让PuLP内部高效处理：

prob += pulp.lpSum(X[(i,j)] * V[i][j] for i in range(N) for j in range(M))

如果V是numpy数组，可先转成Python列表（V.tolist()），减少循环中numpy元素的访问开销。

3. 约束批量添加

逐个添加约束会增加Python与PuLP的交互次数，改用生成器表达式批量添加约束，大幅减少交互开销：

• 客户选择约束：

  prob += (pulp.lpSum(X[(i,j)] for j in range(M)) == 1 for i in range(N))
  

• 产品配额约束：

  prob += (pulp.lpSum(X[(k,i)] for k in range(N)) == T[i] for i in range(M))
  

同时避免创建临时列表（如原代码中的[X[k][i] for k in range(N)]），改用生成器表达式节省内存和时间。

4. 求解器参数调优

PuLP默认使用CBC求解器，可通过以下方式提速：

• 启用多线程：利用多核CPU并行计算，设置threads参数；
• 关闭日志：禁用求解过程日志，减少IO开销。
  示例：

prob.solve(pulp.CBC_CMD(threads=8, msg=False))

若有授权，可替换为Gurobi、CPLEX等商业求解器，这类求解器在大规模整数规划问题上的性能远超CBC。

5. 问题结构简化

该问题本质是带配额的指派问题，可先通过贪心算法预分配高价值的客户-产品匹配（比如给每个客户分配价值最高的产品，再调整满足配额约束），再用整数规划修正，能大幅减少求解器的计算量。

PuLP更快实现的完整示例 #

import pulp
import numpy as np
import time

def func_optimized(N,M,V,T):
    t0 = time.time()
    prob = pulp.LpProblem("MCKP", pulp.LpMaximize)

    # 高效定义变量
    X = pulp.LpVariable.dicts(
        "X",
        ((i, j) for i in range(N) for j in range(M)),
        lowBound=0,
        upBound=1,
        cat=pulp.LpInteger
    )

    # 目标函数高效构建
    prob += pulp.lpSum(X[(i,j)] * V[i][j] for i in range(N) for j in range(M))

    # 批量添加约束
    prob += (pulp.lpSum(X[(i,j)] for j in range(M)) == 1 for i in range(N))
    prob += (pulp.lpSum(X[(k,i)] for k in range(N)) == T[i] for i in range(M))

    # 多线程求解+关闭日志
    prob.solve(pulp.CBC_CMD(threads=8, msg=False))
    t1 = time.time()
    print("Used: {}".format(int(t1 - t0)))

N=10000
M=12
V=np.random.random((N,M))
T=[800]*11 + [1200]
func_optimized(N,M,V,T)

内容的提问来源于stack exchange，提问作者Yi-Yu Peng