资源分配问题下CVXPY与Gurobi实现效率对比及CVXPY内存优化咨询
CVXPY实现资源分配问题的内存优化方案
内存占用过高的核心成因
现有CVXPY实现的高内存消耗来源于三个和建模逻辑直接相关的设计缺陷,完全偏离了CVXPY的批量建模设计初衷,和原生Gurobi的底层对象构造逻辑脱节:
- 逐键独立定义散列字典变量:每一个
(资源,作业)对都生成一个独立的cp.VariablePython对象,叠加字典的哈希存储结构,在大规模问题下会产生大量碎片化的Python对象开销 - 嵌套循环逐元素累加构造约束:每一条约束都是独立生成的Python约束对象,没有利用向量/矩阵形式的批量约束能力,造成约束对象的内存堆积
- 临时数组转换操作:将变量值转列表、转numpy数组参与运算的过程,会产生大量临时的变量引用副本,额外占用可观的内存空间
对标Gurobi字典变量能力的优化实现
CVXPY本身支持批量多维变量定义,完全可以实现和GurobiaddVars(字典键)同等的内存效率,具体优化步骤如下:
- 建立连续整数索引映射
将资源、作业集合转换为有序列表,构建名称到整数索引的映射关系,替代字典的散列键访问逻辑,为批量多维变量提供索引维度 - 用批量多维变量替代散列字典逐键定义
直接定义二维二元变量对应(资源, 作业)的分配关系,定义一维向量变量对应作业的gap状态,所有变量存储在单个多维数组对象中,不再为每个键生成独立的Variable实例,从根本上降低变量层的内存开销 - 用矩阵运算批量构造约束,替代嵌套循环
利用多维数组的沿轴求和能力,一次性生成所有作业的需求约束、所有资源的供给约束,不再逐元素累加构造零散约束 - 预填结构化的得分、成本矩阵
将原有字典存储的得分、成本值,按索引位置预填充为和变量形状一致的二维矩阵,用逐元素乘加的矩阵运算替代临时列表转数组的点积操作,消除临时内存拷贝
优化后完整代码
import cvxpy as cp import numpy as np # 索引映射构建 res_list = list(res) job_list = list(job) res_idx = {r:i for i,r in enumerate(res_list)} job_idx = {j:i for i,j in enumerate(job_list)} n_res = len(res_list) n_job = len(job_list) # 批量变量定义(对标Gurobi addVars能力) X = cp.Variable(shape=(n_res, n_job), boolean=True, name="assign") G = cp.Variable(shape=(n_job,), boolean=True, name="gap") # 预填充结构化参数矩阵 score_mat = np.zeros((n_res, n_job)) cost_mat = np.zeros((n_res, n_job)) for (r,j), score in ms.items(): score_mat[res_idx[r], job_idx[j]] = score for (r,j), cost in cst.items(): cost_mat[res_idx[r], job_idx[j]] = cost # 批量约束构造 job_gap_penalty = 101 constraints = [ cp.sum(X, axis=0) + G == 1, # 所有作业的需求约束 cp.sum(X, axis=1) <= 1, # 所有资源的供给约束 cp.sum(cp.multiply(cost_mat, X)) <= budget # 预算约束 ] # 目标函数构造 objective = cp.Maximize( cp.sum(cp.multiply(score_mat, X)) - job_gap_penalty * cp.sum(G) ) # 求解 prob = cp.Problem(objective, constraints) prob.solve(solver=cp.GUROBI, verbose=False)
优化效果说明
上述实现的内存占用和原生Gurobi实现基本持平:
- 变量层内存开销下降90%以上,单个数组对象替代了数百个独立Variable实例的碎片化存储
- 约束层为批量矩阵形式定义,直接传递给Gurobi求解器接口,没有零散约束对象的额外内存开销
- 消除了所有临时列表、临时数组的转换操作,无额外内存拷贝
若需要按原
(资源名, 作业名)键查询变量求解值,可直接通过批量变量的数组索引访问:X.value[res_idx[r], job_idx[j]],无需在建模阶段保留散列字典结构。
内容的提问来源于stack exchange,提问作者Mohsen Ghanavati
相关产品推荐
相关产品推荐

