为什么我不能为整数规划装配 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.

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

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

因此，只有数组中的第 2 个值满足条件 >= 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屋！