为什么我不能为整数编程安装SciPy的约束优化？

Question

我已经读过整数编程要么非常棘手,要么用SciPy不可能 ,我可能需要使用像zibopt这样的东西来用Python做.但我真的认为我可以通过为SciPy优化的向量中的每个元素创建一个"is binary"约束来实现.

为此,我利用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中是不可能做到的？

Answer 1

问题在于,尽管看起来不直观,但整数编程比使用实数的线性编程更加困难.您链接的SO线程中有人提到SciPy使用Simplex算法.该算法不适用于整数编程.您必须使用不同的算法.

如果你确实找到了一种方法来使用Simplex来有效地解决整数规划问题,那么你已经解决了P = NP问题,这个问题值得第一个人解决,价值1,000,000美元.