Python中的二进制线性规划求解器

Question

我有一个Python脚本,我需要解决线性编程问题.问题是解决方案必须是二进制的.换句话说,我需要一个等效的MATLAB的bintprog函数.NumPy和SciPy似乎没有这样的程序.有没有人建议我如何做这三件事之一:

• 找一个包含这样一个函数的Python库.

• 限制问题,使其可以通过更通用的线性编程求解器来解决.

• 使用MATLAB与Python接口,以便直接使用bintprog.

Answer 1

只是要严格,如果问题是二进制编程问题,那么它不是一个线性程序.

你可以试试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

Answer 2

这是一个半答案，但您可以使用 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