Недостаточно памяти при решении большой задачи квадратичного программирования с использованием Cplex Python API - PullRequest
Новая
       26

Недостаточно памяти при решении большой задачи квадратичного программирования с использованием Cplex Python API

0 голосов
/ 13 сентября 2018

Я пытаюсь решить большую проблему квадратичного программирования с помощью API IBM Cplex Python. Я исчерпываю память при создании матрицы qMat, которая определяет квадратичную часть проблемы на машине Linux с 120 ГБ ОЗУ.

В приведенном ниже примере кода qMat имеет 10 строк. В актуальной задаче у меня около 100 000 строк. И каждая строка имеет 10 - 1000 ненулевых столбцов. Машине не хватает памяти при создании qMat, который представляет собой список списков, каждый из которых имеет два списка (один с указанием столбцов, другой с указанием значений). Другими словами, машине не хватает памяти еще до того, как она загружает проблему в Cplex. Было бы полезно, если бы вы могли предложить другой способ разработки qMat и загрузки таких данных в Cplex. Конечно, я могу записать qMat построчно в текстовый файл, но можно ли загрузить такой файл в Cplex?

Причина, по которой приведенный ниже код состоит в следующем, заключается в том, что qMatIndexes нужно вычислять только один раз, так как net исправлена. Но сам qMat нужно вычислять много раз, потому что это зависит от mDict. В основном мне нужно многократно запускать оптимизацию Cplex для многих mDicts с разреженной Q-матрицей, имеющей размер 100 000 × 100 000. Именно эту разреженную матрицу Q представляет qMat. 

from __future__ import division


import copy
import numpy as np
import collections
import cplex
from cplex.exceptions import CplexError
import sys
import random
import cjson
from pympler.asizeof import asizeof
from scipy.sparse import csr_matrix

net = collections.OrderedDict([(1, [1, 2, 4]), (2, [2, 3, 4]), (3, [3, 4]), (4, [1, 4])])
mDict = {1:10,2:20,3:30,4:40}

def write_qMat_indexes(net):
    i_indiciesRow = []
    j_indiciesColumn = []

    count = 0
    for ID in net:
        sup = list(set(net[ID]))
        for s in sup:
            i_indiciesRow.append(count + 1)
            j_indiciesColumn.append(s)
        count += 1

    with open('i_indiciesRow.txt', 'w') as file_i_indiciesRow:
        file_i_indiciesRow.write(cjson.encode(i_indiciesRow))

    with open('j_indiciesColumn.txt', 'w') as file_j_indiciesColumn:
        file_j_indiciesColumn.write(cjson.encode(j_indiciesColumn))

def QMatrixDisk():
    with open('i_indiciesRow.txt', 'r') as file:
        for line in file:
            iN_list = cjson.decode(line)

    with open('j_indiciesColumn.txt', 'r') as file:
        for line in file:
            jN_list = cjson.decode(line)

    jN_array = np.array(jN_list)
    jN_locations = {}
    for j in jN_list:
        locations = np.where(jN_array == j)[0]
        jN_locations[j] = list(locations)
    del jN_array
    print "done finding locations"


    with open('qMatIndexes.txt', 'w') as file:
        for r in xrange(len(jN_list)):
            jN = jN_list[r]
            columns = jN_locations[jN]
            firstID_list = []
            columnsList = []
            for c in columns:
                q = iN_list[c]
                if c >= r:
                    firstID_list.append(q)
                    columnsList.append(c)
            Data = (columnsList, firstID_list)
            file.write(cjson.encode(Data) + '\n')




def create_qMat_Disk(mDict):
    with open("i_indiciesRow.txt", 'r') as file:
        for line in file:
            iN_list = cjson.decode(line)

    with open("j_indiciesColumn.txt", 'r') as file:
        for line in file:
            jN_list = cjson.decode(line)


    num_lines = sum(1 for line in open('qMatIndexes.txt'))

    qMat = [[[], []] for _ in range(num_lines)]
    count = 0
    with open('qMatIndexes.txt', 'r') as nfile:
        for line in nfile:
            cq = cjson.decode(line)
            columns = cq[0]
            q_list = cq[1]
            baseAgent = jN_list[count]
            firstAgent = iN_list[count]
            baseM = mDict[baseAgent]
            firstM = mDict[firstAgent]
            multiple = 2.0 * firstM / baseM
            second_mList = [mDict[q] for q in q_list]
            vals = [s * multiple for s in second_mList]
            qMat[count][0] += columns
            qMat[count][1] += vals

            for k in xrange(len(columns)):
                col = columns[k]
                newInds = []
                newVals = []
                if col > count:
                    val = vals[k]
                    newInds.append(count)
                    newVals.append(val)
                qMat[col][0] += newInds
                qMat[col][1] += newVals

            count += 1

    return qMat



write_qMat_indexes(net)
QMatrixDisk()
create_qMat_Disk(mDict)


C = [-6.0, -6.0, -6.0, -6.0, -6.0, -6.0, -4.0, -4.0, -4.0, -4.0]
my_ub = [1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0, 1.0]
my_lb = [0.03333333333333333, 0.03333333333333333, 0.03333333333333333, 0.03333333333333333, 0.03333333333333333, 0.03333333333333333, 0.05, 0.05, 0.05, 0.05]
my_rhs = [1, 1, 1, 1, 1.6]
my_sense = 'EEEEL'


W_rows = [0, 0, 0, 1, 1, 1, 2, 2, 3, 3, 4, 4, 4, 4]
W_columns = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 0, 3, 6, 9]
W_values = [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]

qMat = create_qMat_Disk(mDict)
print len(qMat), "len qMat"


my_prob = cplex.Cplex()
my_prob.parameters.qpmethod.set(4)
my_prob.parameters.lpmethod.set(4)
my_prob.objective.set_sense(my_prob.objective.sense.minimize)
my_prob.variables.add(obj=C, ub=my_ub, lb=my_lb)
my_prob.linear_constraints.add(rhs=my_rhs, senses=my_sense)
my_prob.linear_constraints.set_coefficients(zip(W_rows, W_columns, W_values))

my_prob.objective.set_quadratic(qMat)

my_prob.solve()

solutionValues = my_prob.solution.get_values()
...