CPLEX с Python API - как сделать формулировку модели быстрее? - PullRequest
Новая
       7

CPLEX с Python API - как сделать формулировку модели быстрее?

0 голосов
/ 06 июня 2018

Я обратился к CPLEX, поскольку мне предстоит решить довольно большую линейную задачу.
Если мы используем scipy.optimize.linprog Обозначение:

Свернуть: c ^ T *x
при условии: A_ub * x <= b_ub и A_eq * x == b_eq, </p>

, тогда моя A_ub матрица имеет форму примерно (20000, 10000): 20000 ограничений10000 переменных.

Очень быстро построить матрицы A_ub, A_eq и векторы c, b_ub, b_eq , используя numpy.
Но создание проблемы CPLEX из этого требуетоколо 30 секунд (что не приемлемо в моей ситуации).Это происходит потому, что их Python API не может принимать матрицу в качестве входных данных (по крайней мере, я не смог найти такую ​​функциональность после нескольких дней тестирования различных сценариев).
Единственный способ создать проблему - это построить ее либо по столбцу,столбец или строка за строкой, например: 

problem = cplex.Cplex()
problem.set_problem_type(problem.problem_type.LP)
problem.objective.set_sense(problem.objective.sense.minimize)
problem.variables.add(obj=c)

n_constraints, n_vars = A_ub.shape
index = list(range(n_vars))
list_rhs = list(b_ub)
# for each row (constraint) create a SparsePair instance
sparse_pairs = [cplex.SparsePair(ind=index, val=A_ub[i]) for i in range(n_constraints)]

# this piece takes 30 seconds
problem.linear_constraints.add(
    lin_expr=sparse_pairs,
    rhs=list_rhs,
    senses=['L'] * n_less_cons
)

Я также пытался сделать это столбец за столбцом и непосредственно заполняя коэффициенты, но все одинаково медленно.

Я не могу поверить, что этоОбычно постановка задачи занимает в 6-7 раз больше времени, чем ее решение (решение занимает 4-5 секунд).Кто-нибудь знает, есть ли более быстрый способ создать проблему в CPLEX?
В настоящее время быстрее решить проблему с помощью cvxopt, используя GLPK с открытым исходным кодом (15 секунд), потому что он непосредственно принимает матрицы в качестве входных данных,как scipy.linprog.

PS Я также проверил API Python Gurobi, и у него та же проблема (он работает даже медленнее).

Ответы [ 3 ]

0 голосов
/ 28 февраля 2019

Предположим, что A_ub - это разреженная матрица, 

a_rows = A_ub.row.tolist()
a_cols = A_ub.col.tolist()
a_vals = A_ub.data
list_rhs = list(b_ub)
problem.linear_constraints.add(rhs=list_rhs, senses=['L'] * n_less_cons)
problem.linear_constraints.set_coefficients(zip(a_rows, a_cols, a_vals))

Вы можете попробовать это.В моем случае это работает лучше.

0 голосов
/ 03 мая 2019

Здесь обсуждалась та же проблема: https://github.com/cvxgrp/cvxpy/issues/617. Кажется, до сих пор нет решения этой проблемы.

0 голосов
/ 06 июня 2018

Docplex имеет класс CplexTransformer (docplex.mp.sktrans.transformers.py), который строит и решает линейную модель из матрицы и вектора стоимости.Он принимает непрямые матрицы, кадры данных Pandas и разреженные матрицы матрицы Сциписа (для очень разреженных матриц формулировка матрицы матрицы действительно может помочь).

Вот очень маленький фрагмент кода, показывающий использование CplexTransformer: 

# ----- a very small CplexTransformer example
from docplex.mp.sktrans.transformers import CplexTransformer
import scipy.sparse as sp


def solve_cpxtrans_sparse_coo():
    xs = [0, 0, 1, 1, 0, 1]
    ys = [0, 1, 1, 2, 3, 3]
    dd = [1, 1, 1, 1, 5, 7]
    spm = sp.coo_matrix((dd, (xs, ys)), shape=(2, 4))
    ubs = 10
    res = CplexTransformer(sense="min").transform(spm, y=[3, 2, 1], ubs=ubs, sense='ge')
    print(res)
    xs= res['value'].tolist()
    print(xs)
...