用于快速设置和解决的Python中lpsolve的替代方案

Question

我已经在Python中使用了很长一段时间，并且取得了很好的效果。我甚至为它编写了自己的Cython包装器，以克服原来Python包装器的混乱。

我的Cython包装器在设置问题时要快得多，但是解决时间当然只取决于faster代码，与Python无关。

我只是在解实值线性问题，没有MIP。我必须解决的最新的(也是最大的) LP有一个大小约为5,000×3,000的约束矩阵，而设置加size大约需要150 ms。问题是，我必须解决同一个问题的一个稍微修改的版本，在我的模拟中多次使用(约束、RHS、界等等是时间依赖的，用于多个时间步骤的模拟)。约束矩阵通常是非常稀疏的，约为NNZ的0.1% - 0.5%或更少。

使用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矩阵，再加上上面所有那些花哨的操作，肯定会成为性能杀手。

如果可能的话，我宁愿呆在开源软件上，但是任何建议都是最受欢迎的。我为这个长邮差道歉。

安德里亚。

Answer 1

@无穷大

我现在正在考虑使用lpsolve。生成一个用于输入的.lp文件是非常直接的，它确实解决了几个较小的问题。但是..。我现在正试图解决一个节点着色问题。这是个MIP。我第一次尝试解决500个节点问题时，进行了大约15分钟的lp放松。从昨晚开始就一直在研究真正的MIP。还在磨蹭。这些着色问题是困难的，但14个小时内看不到尽头的是太多了。

我所知道的最好的选择是铜管-or.org；硬币-或索弗斯尝试他们的clp和cbc解算器，这取决于您要解决的问题类型。我见过的基准说，它们是CPLEX和Gurobi之外最好的选择。它是免费的，但您需要确保它对您的目的是“合法的”。开源解决方案基准的Bernhard和Matthias的一篇好的基准论文