Блог

Я использую lpsolve на Python очень долгое время, и в целом результаты хорошие. Я даже написал для него свою собственную оболочку Cython, чтобы преодолеть беспорядок, который представляет собой оригинальная оболочка Python.

Моя оболочка Cython намного быстрее настраивает проблему, но, конечно, время решения зависит только от кода lpsolve C и не имеет ничего общего с Python.

Я решаю только вещественные линейные задачи, без MIPS. Последний (и один из самых больших) LP, который мне приходилось решать, имел матрицу ограничений размером около 5000 x 3000, а настройка и решение занимают около 150 мс. Проблема в том, что мне приходится решать слегка измененную версию одной и той же проблемы много раз в моей симуляции (ограничения, RHS, границы и т. Д. Зависят от времени для симуляции со многими временными шагами). Матрица ограничений обычно очень разреженная, с примерно 0,1% — 0,5% NNZ или меньше.

Используя lpsolve, настройка и решение проблемы так же просты, как следующее:

 import numpy
from lp_solve.lp_solve import PRESOLVE_COLS, PRESOLVE_ROWS, PRESOLVE_LINDEP, PRESOLVE_NONE, SCALE_DYNUPDATE, lpsolve

# The constraint_matrix id a 2D NumPy array  and it contains 
# both equality and inequality constraints
# And I need it to be single precision floating point, like all 
# other NumPy arrays from here onwards
m, n = constraint_matrix.shape

n_le = len(inequality_constraints)
n_e  = len(equality_constraints)

# Setup RHS vector
b = numpy.zeros((m, ), dtype=numpy.float32)

# Assign equality and inequality constraints (= and <=)
b[0:n_e]  = equality_constraints
b[-n_le:] = inequality_constraints

# Tell lpsolve which rows are equalities and which are inequalities
e = numpy.asarray(['LE']*m)
e[0:-n_le] = 'EQ'

# Make the LP
lp = lpsolve('make_lp', m, n)

# Some options for scaling the problem
lpsolve('set_scaling', lp, SCALE_DYNUPDATE)
lpsolve('set_verbose', lp, 'IMPORTANT')

# Use presolve as it is much faster
lpsolve('set_presolve', lp, PRESOLVE_COLS | PRESOLVE_ROWS | PRESOLVE_LINDEP)

# I only care about maximization
lpsolve('set_sense', lp, True)

# Set the objective function of the problem
lpsolve('set_obj_fn', lp, objective_function)
lpsolve('set_mat', lp, constraint_matrix)

# Tell lpsolve about the RHS
lpsolve('set_rh_vec', lp, b)

# Set the constraint type (equality or inequality)
lpsolve('set_constr_type', lp, e)

# Set upper bounds for variables - lower bounds are automatically 0
lpsolve('set_upbo', lp, ub_values)

# Solve the problem
out = lpsolve('solve', lp)

# Retrieve the solution for all the variables
vars_sol = numpy.asarray([lpsolve('get_var_primalresult', lp, i) for i in xrange(m   1, m   n   1)], dtype=numpy.float32)

# Delete the problem, timestep done
lpsolve('delete_lp', lp)
  

По причинам, которые слишком долго объяснять, мои массивы NumPy — это все массивы с плавающей запятой одинарной точности, и я бы хотел, чтобы они оставались такими.

Теперь, после всего этого болезненного введения, я хотел бы спросить: кто-нибудь знает другую библиотеку (с разумными оболочками Python), которая позволяет мне настраивать и решать проблему такого размера так же быстро (или потенциально быстрее), чем lpsolve? Большинство библиотек, на которые я смотрел (PuLP, CyLP, PyGLPK и т. Д.), Похоже, не имеют простого способа сказать «это вся моя матрица ограничений, установите ее за один раз». Похоже, что они в основном ориентированы на то, чтобы быть «языками моделирования», которые позволяют создавать подобные вещи (пример CyLP):

 # Add variables
x = s.addVariable('x', 3)
y = s.addVariable('y', 2)

# Create coefficients and bounds
A = np.matrix([[1., 2., 0],[1., 0, 1.]])
B = np.matrix([[1., 0, 0], [0, 0, 1.]])
D = np.matrix([[1., 2.],[0, 1]])
a = CyLPArray([5, 2.5])
b = CyLPArray([4.2, 3])
x_u= CyLPArray([2., 3.5])

# Add constraints
s  = A * x <= a
s  = 2 <= B * x   D * y <= b
s  = y >= 0
s  = 1.1 <= x[1:3] <= x_u
  

Честно говоря, меня не волнует гибкость, мне просто нужна необработанная скорость при настройке и решении проблемы. Создание NumPy-матриц плюс выполнение всех этих причудливых операций, описанных выше, определенно приведет к снижению производительности.

Я бы предпочел использовать решатели с открытым исходным кодом, если это возможно, но любое предложение приветствуется. Мои извинения за длинный пост.

Андреа.

@infinity77,

Сейчас я рассматриваю возможность использования lpsolve. Довольно просто сгенерировать файл .lp для ввода, и это решило несколько небольших проблем. НО… Сейчас я пытаюсь решить проблему с раскраской узла. Это MIP. Моя первая попытка решить проблему с 500 узлами заняла около 15 минут в качестве релаксации lp. lpsolve работает над настоящим MIP со вчерашнего вечера. Все еще шлифуется. Эти проблемы с раскраской сложны, но 14 часов без конца — это слишком много.

Лучшая альтернатива, о которой я знаю, — это из coin-or.org ;[Монета-Или решатели] 1 Попробуйте их решатели clp и cbc в зависимости от того, какой тип проблемы вы решаете. Тесты, которые я видел, говорят, что они являются лучшим выбором за пределами CPLEX и Gurobi. Это бесплатно, но вам нужно будет убедиться, что это «законно» для ваших целей. Хорошая контрольная работа Бернхарда Майндла и Маттиаса Темпла из Open Source Solver Benchmarks