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

Question

我有一个Python脚本，需要解决一个线性规划问题。不过有个特别的要求，就是解决方案必须是二进制的，也就是说结果只能是0或1。这个功能在MATLAB里有个叫bintprog的函数可以实现。但是在NumPy和SciPy里似乎没有类似的功能。有没有人能给我一些建议，帮我做到以下三件事中的一件：

• 找一个Python库，里面有这样的函数。

• 对问题进行约束，使它可以用更通用的线性规划求解器来解决。

• 把Python和MATLAB连接起来，直接使用bintprog。

Answer 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])

Answer 2

这算是个半个答案，不过你可以用Python来和GLPK（通过python-glpk）进行交互。GLPK支持整数线性规划。（二进制程序其实是整数程序的一种特例。）

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

或者你可以直接用Python写出你的问题，然后生成一个MPS文件（大多数标准的线性规划/混合整数线性规划求解器，比如CPLEX、Gurobi、GLPK都能接受这个文件）。这样做可能是个不错的选择，因为据我所知，目前没有高质量的混合整数线性规划求解器是原生支持Python的（而且可能永远也不会有）。这样你也可以尝试不同的求解器。

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

至于如何让Python和MATLAB配合使用，我建议自己动手解决。你可以生成一个.m文件，然后从命令行运行它。

% matlab -nojava myopt.m

注意事项：

1. 如果你是学术用户，可以免费获得Gurobi的许可证，这是一款高性能的线性规划/混合整数线性规划求解器。它有Python接口。 http://www.gurobi.com/
2. OpenOpt是一个Python优化工具包，可以和不同的求解器进行交互。 http://en.wikipedia.org/wiki/OpenOpt

Answer 3

为了严谨起见，如果问题是一个二进制编程问题，那它就不是线性规划问题。

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