Skip to main content
 首页 » 编程设计

Cplex 中的 Python 稀疏矩阵

2024年12月31日16虾米哥

我正在研究一个大型二次规划问题。我想使用 Python API 将定义目标函数的 Q 矩阵输入到 IBM 的 Cplex 中。 Q 矩阵是使用 scipy lil 矩阵构建的,因为它是稀疏的。理想情况下,我想将矩阵传递给 Cplex。 Cplex 是否接受 scipy lil 矩阵?

我可以将 Q 转换为 Cplex 接受的列表列表的格式,我们称之为 qMat。但是 qMat 的大小变得太大,机器内存不足(即使有 120 Gig)。

下面是我正在进行的工作代码。在实际问题中,n 约为 50 万,m 约为 500 万。在实际问题中,Q 是给定的,而不是像下面的问题那样随机分配的。

from __future__ import division 
import numpy as np 
import cplex 
import sys 
import random 
from scipy import sparse 
 
n = 10 
m = 5 
 
def create(): 
    Q = sparse.lil_matrix((n, n)) 
    nums = random.sample(range(0, n), m) 
    for i in nums: 
        for j in nums: 
            a = random.uniform(0,1) 
            Q[i,j] = a 
            Q[j,i] = a 
    return Q 
 
def convert(Q): 
    qMat = [[[], []] for _ in range(n)] 
    for k in xrange(n-1): 
        qMat[k][0] = Q.rows[k] 
        qMat[k][1] = Q.data[k] 
    return qMat 
 
Q = create() 
qMat = convert(Q) 
my_prob = cplex.Cplex() 
my_prob.objective.set_quadratic(qMat) 

请您参考如下方法:

如果 n = 500000 和 m = 5000000,则为 2.5e12 非零值。对于其中的每一个,您大约需要一个 double 用于非零值,一个 CPXDIM 用于索引。即每个非零 8+4=12 个字节。这将给出:

>>> print(2.5e12 * 12 / 1024. / 1024. / 1024.) 
27939.6772385 

大约 28TB 内存!目前尚不清楚您计划拥有多少个非零值,但使用此计算您可以轻松确定是否有可能按照您的要求进行操作。

如评论中所述,CPLEX Python API 不接受 scipy lil 矩阵。你可以试试 docplex ,这是 numpy 友好的,或者你甚至可以尝试生成一个 LP file直接。

就减少转换开销而言,使用类似下面的方法可能是您的最佳选择(我想我在上面的评论部分犯了一个差一错误):

my_prob.objective.set_quadratic(list(zip(Q.rows, Q.data))) 

或

my_prob.objective.set_quadratic([[row, data] for row, data in zip(Q.rows, Q.data)])) 

无论如何,您都应该尝试一下,看看什么能提供最佳性能(在速度和内存方面)。