Python中的二元线性规划求解器

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

找到一个Python库，其中包括这样的功能。
限制问题，使其可以通过更一般的线性规划求解器来解决。
接口与MATLAB的Python，以便直接使用bintprog。

来源

2010-07-24 tlayton

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

至于与MATLAB接口的Python，我只想推出自己的解决方案。你可以生成一个.m文件，然后在命令行

% matlab -nojava myopt.m

注意运行：

如果你是一个学术的用户，你可以得到一个免费的许可Gurobi，一高性能LP/MILP解算器。它有一个Python界面。 http://www.gurobi.com/
OpenOpt是一个Python优化套件，可以与不同的求解器进行交互。 http://en.wikipedia.org/wiki/OpenOpt

来源

2010-07-24 17:43:22 Gilead

只是要严谨，如果问题是一个二进制编程问题，那么它是不是一个线性规划。您可以尝试CVXOPT。它有一个整数编程功能（见this）。为了使您的问题二进制程序，你需要添加约束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-24 20:25:31 Alejandro

添加约束'0 <= x <= 1'不会生成二进制程序。它只是二进制程序的LP放松，可以用作二进制程序解决方案的一部分。 – Peter 2010-07-24 20:40:25

我的意思是将Integer程序中的约束0 <= x <= 1添加到整数程序中（您可以使用CVXOPT解决上述问题），将整数程序转换为二进制程序。 – Alejandro 2010-07-25 01:06:44

好吧，是的，没有。仅具有二进制/整数变量的线性程序被称为ILP（整数线性程序）。具有二进制/整数变量和连续变量的线性程序称为MILP（混合整数线性程序）。术语“整数”和“二进制”在这种情况下可互换使用，因为可以使用多个二进制变量（即SOS类型1）来表示任何整数变量。但是，如果将x声明为一般整数变量，则应该强制0 <= x <= 1，这是正确的。但是，在大多数情况下，x可以直接声明为二元变量。 – Gilead 2010-07-26 05:31:20

Python中的二元线性规划求解器

回答

相关问题