6

我已经读到整数编程要么非常棘手，要么无法使用 SciPy 进行，我可能需要使用 zibopt 之类的东西在 Python 中进行。但我真的认为我可以通过为 SciPy 优化的向量中的每个元素创建一个“二元”约束来做到这一点。

为此，我利用了http://docs.python-guide.org/en/latest/writing/gotchas/#late-binding-closures中的闭包技巧， 并为每个元素创建了一个约束函数，如下所示：

def get_binary_constraints(vector, indices_to_make_binary=None):
    indices_to_make_binary = indices_to_make_binary or range(len(vector))
    for i in indices_to_make_binary:
        def ith_element_is_binary(vector, index=i):
            return vector[index] == 0 or vector[index] == 1
        yield ith_element_is_binary

test_vector = scipy.array([0.5, 1, 3])
constraints = list(get_binary_constraints(test_vector))
for constraint in constraints:
    print constraint(test_vector)

打印：

False
True
False

然后我修改了 fmin_cobyla 的 get_binary_constraints，它的约束是“所有函数必须 >=0”的序列。

def get_binary_constraints(vector, indices_to_make_binary=None):
    indices_to_make_binary = indices_to_make_binary or range(len(vector))
    for i in indices_to_make_binary:
        def ith_element_is_binary(vector, index=i):
            return int(vector[index] == 0 or vector[index] == 1) - 1
        yield ith_element_is_binary

它为相同的测试向量 [0.5, 1, 3] 打印以下内容：

-1
0
-1

因此，只有数组中的第二个值满足 >= 0 的条件。

然后，我设置了一个非常简单的优化问题，如下所示：

from scipy import optimize
import scipy

def get_binary_constraints(vector, indices_to_make_binary=None):
    indices_to_make_binary = indices_to_make_binary or range(len(vector))
    for i in indices_to_make_binary:
        def ith_element_is_binary(vector, index=i):
            return int(vector[index] == 0 or vector[index] == 1) - 1
        yield ith_element_is_binary

def objective_function(vector):
    return scipy.sum(vector)

def main():
    guess_vector = scipy.zeros(3)
    constraints = list(get_binary_constraints(guess_vector))
    result = optimize.fmin_cobyla(objective_function, guess_vector, constraints)
    print result

if __name__ == '__main__':
    main()

这就是我得到的：

Return from subroutine COBYLA because the MAXFUN limit has been reached.

NFVALS = 1000   F =-8.614066E+02    MAXCV = 1.000000E+00
X =-2.863657E+02  -2.875204E+02  -2.875204E+02
[-286.36573349 -287.52043407 -287.52043407]

在我去使用 R 的 LPSolve 包或为此安装 zipobt 之前，我真的很想看看我是否可以只使用 SciPy。

我做错了什么，或者这在 SciPy 中是不可能的吗？

4

1 回答 1

11

问题在于，尽管看起来不直观，但整数规划从根本上来说是一个比实数线性规划更困难的问题。您链接到的 SO 线程中有人提到 SciPy 使用Simplex算法。该算法不适用于整数规划。您必须使用不同的算法。

如果您确实找到了一种使用 Simplex 有效解决整数规划的方法，那么您已经解决了P=NP问题，对于第一个解决的人来说价值1,000,000 美元。

于 2013-04-03T17:02:39.737 回答