16

我有一个 Python 脚本，我需要在其中解决线性规划问题。问题是解决方案必须是二进制的。换句话说，我需要一个等效于 MATLAB 的bintprog函数。NumPy 和 SciPy 似乎没有这样的程序。有没有人对我如何做这三件事之一有建议：

  • 查找包含此类函数的 Python 库。

  • 约束问题，使其可以通过更通用的线性规划求解器来求解。

  • 将 Python 与 MATLAB 连接，以便直接使用bintprog。

4

3 回答 3

7

严格来说，如果问题是二进制规划问题，那么它就不是线性规划。

您可以尝试CVXOPT。它有一个整数编程函数（见这个）。要使您的问题成为二进制程序，您需要添加约束 0 <= x <= 1。

编辑：您实际上可以将变量声明为二进制，因此您不需要添加约束 0 <= x <= 1。

cvxopt.glpk.ilp = ilp(...)
Solves a mixed integer linear program using GLPK.

(status, x) = ilp(c, G, h, A, b, I, B)

PURPOSE
Solves the mixed integer linear programming problem

    minimize    c'*x
    subject to  G*x <= h
                A*x = b
                x[I] are all integer
                x[B] are all binary
于 2010-07-24T20:25:31.000 回答
5

这是一个半答案，但您可以使用 Python 与 GLPK 交互（通过 python-glpk）。GLPK 支持整数线性规划。（二进制程序只是整数程序的一个子集）。

http://en.wikipedia.org/wiki/GNU_Linear_Programming_Kit

或者您可以简单地用 Python 编写您的问题并生成一个 MPS 文件（大多数标准 LP/MILP（CPLEX、Gurobi、GLPK）求解器都可以接受）。这可能是一条不错的路线，因为据我所知，没有任何 Python 原生的高质量 MILP 求解器（可能永远不会有）。这也将允许您尝试不同的求解器。

http://code.google.com/p/pulp-or/

至于将 Python 与 MATLAB 连接，我会推出自己的解决方案。您可以生成一个 .m 文件，然后从命令行运行它

% matlab -nojava myopt.m

备注：

  1. 如果您是学术用户，您可以获得 Gurobi 的免费许可证，这是一个高性能 LP/MILP 求解器。它有一个 Python 接口。 http://www.gurobi.com/
  2. OpenOpt 是一个 Python 优化套件，可与不同的求解器交互。 http://en.wikipedia.org/wiki/OpenOpt
于 2010-07-24T17:43:22.727 回答
1

我开发了一个名为 gekko ( pip install gekko) 的包，它解决了线性、二次、非线性和混合整数规划（LP、QP、NLP、MILP、MINLP）的大规模问题，并在 MIT 许可下发布。二进制变量声明为整数变量类型，其下限为 0，上限为 1 b=m.Var(integer=True,lb=0,ub=1)。下面是使用定义多个二进制变量的一个更完整的问题：m.Array()

from gekko import GEKKO
m = GEKKO()
x,y = m.Array(m.Var,2,integer=True,lb=0,ub=1) 
m.Maximize(y)
m.Equations([-x+y<=1,
             3*x+2*y<=12,
             2*x+3*y<=12])
m.options.SOLVER = 1
m.solve()
print('Objective: ', -m.options.OBJFCNVAL)
print('x: ', x.value[0])
print('y: ', y.value[0])
于 2021-09-01T17:17:19.120 回答