CVXPY使用GLPK_MI求解192变量整数规划耗时过长如何优化？

1. 核心错误：无效约束拖慢求解 #

你当前代码误将成本求和表达式cost_constraint加入约束列表，该表达式既不是等式也不是不等式，属于无效约束，会导致求解器逻辑异常，是耗时极长的首要原因。

2. 变量定义冗余优化 #

你用192个布尔变量+96个行和为1的约束实现二选一逻辑，完全可以简化为96个布尔变量，直接砍掉一半变量和96个约束，求解效率大幅提升：

import cvxpy as cp
import numpy as np

# 参数定义
unit_cost = np.array([0.4]*32 + [0.45]*58 + [0.4]*6)
single_volume = 17100
v_min = 300000

# 简化变量：x[i]=1代表第i时段选17100体积，0代表选0体积
x = cp.Variable(96, boolean=True)

# 约束只有总容积要求
constraints = [cp.sum(x * single_volume) >= v_min]

# 目标函数：最小化总成本
obj = cp.Minimize(cp.sum(x * unit_cost))

# 求解，推荐用CBC替代GLPK_MI，性能更好
prob = cp.Problem(obj, constraints)
prob.solve(solver=cp.CBC, verbose=True)

# 结果提取
selected = x.value.astype(bool)
best_volume = np.sum(selected * single_volume)
best_cost = np.sum(selected * unit_cost)
print(f"最小成本：{best_cost}")
print(f"总容积：{best_volume}")
print(f"选中时段索引：{np.where(selected)[0]}")

3. 求解器替换建议 #

GLPK_MI是开源混合整数求解器中性能偏低的选项，替换为开源的CBC求解器速度可提升3~10倍，若有商用求解器授权，使用GUROBI/CPLEX可获得更快的求解速度。

4. 更优解法：贪心直接求解 #

该问题属于典型的贪心可解场景，不需要使用整数规划：
要满足300000的容积要求，需要至少ceil(300000/17100) = 18个时段开启17100体积。优先选择单位成本最低的时段即可：

• 0.4元的低价格时段共有38个，远大于18个的需求
• 最终最小成本为18*0.4=7.2元，总容积为18*17100=307800，完全满足要求，毫秒级即可得到结果。

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