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

Question

我有一个Python脚本，需要解决一个线性规划问题。问题在于解的结果必须是二进制的。换句话说，我需要一个类似于MATLAB的bintprog函数的等价物。NumPy和SciPy似乎没有这样的过程。请问有没有人有以下三种建议之一：

• 找到一个包含这样的功能的Python库。

• 限制问题，使得它可以被更通用的线性规划求解器所解决。

• 将Python与MATLAB接口，直接使用bintprog。

- tlayton

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

- Alejandro

---

添加约束条件 0 <= x <= 1 并不能使问题成为二进制规划问题。这只是二进制规划问题的线性松弛问题，可以作为二进制规划问题解法的一部分使用。 - Peter

我建议在整数规划中添加约束条件0 <= x <= 1（如上所述，您可以使用CVXOPT解决），以将整数规划转换为二进制规划。 - Alejandro

是的...也不完全是。只有包含二进制/整数变量的线性规划称为ILP（整数线性规划）。同时包括二进制/整数变量和连续变量的线性规划称为MILP（混合整数线性规划）。在这个语境中，“整数”和“二进制”这两个术语可以互换使用，因为任何整数变量都可以用多个二进制变量（即SOS类型1）表示。但如果将x声明为通用整数变量，则正确的做法是施加0 <= x <= 1的限制条件。然而，在大多数情况下，x可以直接声明为二进制变量。 - Gilead

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

- Gilead

Answer 3

我开发了一个名为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])

- John Hedengren