Разреженная матрица Python в Cplex?

Question

Я работаю над большой проблемой квадратичного программирования.Я хотел бы добавить матрицу Q, определяющую целевую функцию, в IBM Cplex с использованием Python API.Матрица Q построена с использованием матрицы Scipy Lil, потому что она редкая.В идеале я хотел бы передать матрицу на Cplex.Принимает ли Cplex матрицу Scipy Lil?

Я могу преобразовать Q в формат списка списков, который принимает Cplex, давайте назовем его qMat.Но размер qMat становится слишком большим, и машине не хватает памяти (даже при 120 гигабайтах).

Ниже приведен код незавершенной работы.В актуальной задаче n составляет около полумиллиона, а m составляет около 5 миллионов.В актуальной задаче 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)

Answer 1

Если n = 500000 и m = 5000000, то это 2.5e12 ненулевых.Для каждого из них вам понадобится примерно один double для ненулевого значения и один CPXDIM для индекса.Это 8 + 4 = 12 байтов на ненулевой.Это даст:

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

Примерно 28 ТБ памяти!Точно не ясно, сколько не нулей вы планируете иметь, но с помощью этого вычисления вы легко сможете определить, возможно ли вообще делать то, что вы просите.

Как уже упоминалось в комментариях,API-интерфейс CPLEX Python не принимает матрицы scipy lil.Вы можете попробовать docplex , что удобно для numpy, или вы можете даже попытаться сгенерировать LP файл напрямую.

Использование чего-то вроде следующего - это, вероятно, ваш лучший выбор вУсловия сокращения накладных расходов на конверсию (я думаю, что я сделал ошибку по одному в разделе комментариев выше):

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)]))

В любом случае, вы должныпоиграйте с ними, чтобы увидеть, что дает лучшую производительность (с точки зрения скорости и памяти).