为什么我不能为整数编程操纵SciPy的约束优化? [英] Why can't I rig SciPy's constrained optimization for integer programming?

问题描述

我已经读到整数编程要么非常棘手，要么不可能SciPy ，而我可能需要使用zibopt之类的东西才能在Python中进行操作.但是我真的以为我可以通过为SciPy优化的向量中的每个元素创建一个是二进制"约束来做到这一点.

I've read that integer programming is either very tricky or not possible with SciPy and that I probably need to use something like zibopt to do it in Python . But I really thought I could do it by creating one "is binary" constraint for each element in a vector being optimized by SciPy.

为此，我利用了

To do that, I utilized the closure trick from http://docs.python-guide.org/en/latest/writing/gotchas/#late-binding-closures and created one constraint function for each element, like so:

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的函数序列".

Then I modified get_binary_constraints for fmin_cobyla, whose constraints are a "sequence of functions that all must be >=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]打印以下内容:

which prints the following for the same test vector [0.5, 1, 3]:

-1
0
-1

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

So, only the 2nd value in the array will meet the condition >= 0.

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

Then, I set up a very simple optimization problem as follows:

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.

Before I go use R's LPSolve package or install zipobt for this, I'd really like to see if I can just use SciPy.

我做错什么了吗，还是在SciPy中无法做到?

Am I doing something wrong, or is this just not possible to do in SciPy?

推荐答案

问题是，看起来似乎并不直观，比带有实数的线性编程要困难得多.您链接到的SO线程中有人提到SciPy使用 Simplex 算法.该算法不适用于整数编程.您必须使用其他算法.

The problem is that, as unintuitive as it may seem, Integer Programming is a fundamentally more difficult problem than Linear Programming with real numbers. Someone in the SO thread you linked to mentions that SciPy uses the Simplex algorithm. The algorithm doesn't work for integer programming. You have to use a different algorithm.

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

If you do find a way to use Simplex to solve integer programming efficiently, you've solved the P=NP problem, which is worth US$1,000,000 to the first person to solve.

这篇关于为什么我不能为整数编程操纵SciPy的约束优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！