Scipy.linprog 的 Gurobi 风格模型构建？

Question

我想比较一下Gurobi和Scipy的线性编程工具，比如linprog。 Scipy 需要以 matrix-list-vector-form 的形式指定问题，而 Gurobi 的工作方式类似于 here 这样

m = Model()
m.addVar(...) %for variables
m.addConstr(..>) %for constraints
m.update() %for updating the model
m.optimize % for optimizing the model
m.params %for getting parameters
m._vars %for getting variables

比较

Scipy

Minimize: c^T * x

Subject to: A_ub * x <= b_ub
A_eq * x == b_eq


c : array_like
Coefficients of the linear objective function to be minimized.
A_ub : array_like, optional
2-D array which, when matrix-multiplied by x, gives the values of the upper-bound inequality constraints at x.
b_ub : array_like, optional
1-D array of values representing the upper-bound of each inequality constraint (row) in A_ub.
A_eq : array_like, optional
2-D array which, when matrix-multiplied by x, gives the values of the equality constraints at x.
b_eq : array_like, optional
1-D array of values representing the RHS of each equality constraint (row) in A_eq.
bounds : sequence, optional

我的目标是仅用一种方法编写代码，并仍然使用两个求解器对结果进行基准测试。为了加快比较求解器的速度：

1. Scipy 是否存在 Gurobi 式的 LP 问题模型构建？

2. 是否存在一些包可以使这两种方法互换（我可以为 Gurobi 编写 scipy 风格，或者为 Scipy 编写 Gurobi 风格）？

3. scipy 是否提供任何其他接口来指定线性规划问题？

Answer 1

这听起来需要做很多工作来展示显而易见的内容：

• 像 Gurobi 这样的商业求解器比非商业求解器更快、更强大
  • H 也有高质量的基准测试表明了这一点。 Mittelmann（CLP 和 GLPK 是最受欢迎的非商业）
虽然 scipy 的 linprog 还可以，但比包括 CBC/CLP、GLPK、lpSolve 在内的开源竞争对手差很多...
• 速度和稳健性！
  另外：scipy 的 linprog 似乎确实没有维护
  • 未解决的问题

有一些方法可以做到这一点：

• A) 使用 linprog 的问题定义方式并将其转换为 Gurobi 风格
  非常容易将矩阵形式转换为 Gurobi 的建模
• B) 使用 cvxpy 作为建模工具，获取标准形式并为 Gurobi（实际上：有一个）和 linprog（同样简单）编写一个包装器。这将允许双方使用非常强大的建模语言
  缺点：根据问题进行不透明的转换（例如
  • abs(some_vector)

    可能会引入辅助变量）

• C) 编写一些 MPS 阅读器/或从其他工具中获取一个来在 Gurobi 中对问题进行建模，输出这些内容并在 linprog 中读取和解决
  候选工具：
  • cvxopt's mps-reader（很好地隐藏在文档中），一些 GLPK 接口甚至一些 CBC 接口
  （也许是隐藏的变换）

无论您做什么，解决方案过程分析都将是代码的重要组成部分，因为 linprog 可能会失败很多。它也无法处理大型稀疏模型。

基于您的 gurobi-example 的评论

你的例子（TSP）是MIP，而不是LP
对于 MIP，上面所说的一切都会变得更糟（尤其是商业和开源之间的性能差异）
scipy 中没有 MIP 求解器！

Answer 2

我以一种非常直接的方式做到了这一点。这并不像前一篇文章所暗示的那样需要大量工作。 例如

res = linprog(c, A_ub=Aineq, b_ub=Bineq, A_eq=None if len(Aeq) == 0 else Aeq, b_eq=None if len(Beq) == 0 else Beq, bounds=x_bounds, method="highs", integrality=1)
if not res is None: return np.rint(res.x).astype(np.int64)

翻译为：

m = Model()
v = m.addVars(range(len(c)), lb=[x[0] for x in x_bounds], ub=[x[1] for x in x_bounds], vtype=[GRB.BINARY if x == (0,1) else GRB.INTEGER for x in x_bounds], name=labels)
m.addConstrs((sum(v[i]*a for i, a in enumerate(Aineq[j])) <= Bineq[j] for j in range(len(Aineq))))
m.addConstrs((sum(v[i]*a for i, a in enumerate(Aeq[j])) == Beq[j] for j in range(len(Aeq))))
m.setObjective(sum(v[i]*c[i] for i in range(len(c))), GRB.MINIMIZE)
m.update()
m.optimize()
return [int(v.x) for v in m.getVars()] if m.Status == GRB.OPTIMAL else None

当然，如果不是所有的边界都是整数或二进制，您可能需要更多的变量类型处理，或者 scipy 提供的其他各种可能性，例如列表与标量、无值等。不用说，它可以在几行中完成Python 代码。