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

Я работаю над большой проблемой квадратичного программирования. Я хотел бы передать матрицу 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)

python sparse-matrix cplex quadratic-programming
person user58925    schedule 18.09.2018    source источник
comment
Нет, CPLEX Python API не принимает матрицы scipy lil. docplex удобен для числового программирования и, вероятно, примет их, но он находится поверх API CPLEX Python, поэтому должно произойти такое же преобразование. В конечном итоге входные данные также должны быть преобразованы в собственные массивы C, прежде чем они будут переданы в базовый механизм CPLEX.   -  person rkersh    schedule 19.09.2018
comment
В качестве примечания: чтобы избавиться от некоторых накладных расходов, вы можете уменьшить функцию convert до def convert(Q): return [[Q.rows[k], Q.data[k]] for k in range(n-1)].   -  person rkersh    schedule 19.09.2018
comment
Мне уже слишком поздно редактировать первый комментарий, чтобы сказать, что docplex может решить проблему в облаке, и в этом случае локальное преобразование потенциально может быть пропущено. Последняя мысль заключается в том, что вы потенциально можете записать свою модель на диск в формате LP, а затем прочитать ее, а не создавать все сразу в памяти.   -  person rkersh    schedule 19.09.2018

Ответы (1)


arrow_upward
1
arrow_downward

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

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

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

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

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

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

or

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

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

person rkersh    schedule 19.09.2018