gpt4 book ai didi

python - 为什么我不能为整数规划设置 SciPy 的约束优化?

转载 作者:太空狗 更新时间:2023-10-29 22:16:20 25 4
gpt4 key购买 nike

I've read that integer programming is either very tricky or not possible with 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,它的约束是一个 "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] 打印以下内容:

-1
0
-1

因此,只有数组中的第 2 个值满足 >= 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 中是不可能的?

最佳答案

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

如果您确实找到了一种使用单纯形来有效解决整数规划的方法,那么您就解决了 P=NP问题,值得US$1,000,000给第一个解决的人。

关于python - 为什么我不能为整数规划设置 SciPy 的约束优化?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15793381/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com