将scipy.optimize.minimize限制为整数值

Question

我使用scipy.optimize.minimize来优化一个实际问题，其答案只能是整数。我当前的代码如下所示：

from scipy.optimize import minimize 

def f(x): 
    return (481.79/(5+x[0]))+(412.04/(4+x[1]))+(365.54/(3+x[2]))+(375.88/(3+x[3]))+(379.75/(3+x[4]))+(632.92/(5+x[5]))+(127.89/(1+x[6]))+(835.71/(6+x[7]))+(200.21/(1+x[8])) 

def con(x): 
    return sum(x)-7 

cons = {'type':'eq', 'fun': con} 

print scipy.optimize.minimize(f, [1,1,1,1,1,1,1,0,0], constraints=cons, bounds=([0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7],[0,7])) 

这产生了：

x: array([ 2.91950510e-16, 2.44504019e-01, 9.97850733e-01, 
    1.05398840e+00, 1.07481251e+00, 2.60570253e-01, 
    1.36470363e+00, 4.48527831e-02, 1.95871767e+00] 

但我想它一个整数优化（四舍五入所有x到最接近的整数并不总是给出最低）。

有没有办法只用整数值来使用scipy.optimize.minimize？

（我想我可以创建的x所有可能的排列的数组，并评估每个组合F（X），但是这似乎并不像一个非常优雅和快速的解决方案。）

Answer 1

纸浆解决方案

经过一番研究，我不认为你的目标函数是线性的。我在Python pulp库中重新创建了这个问题，但是纸浆并不喜欢我们用浮点数和'LpAffineExpression'来划分。 This answer表明线性规划“不了解分歧”，但该评论是在增加约束的情况下，而不是目标函数。该评论指出我“Mixed Integer Linear Fractional Programming (MILFP)”和Wikipedia。

这里是你如何能做到这一点的纸浆，如果实际工作（也许有人可以找出原因）：

import pulp 

data = [(481.79, 5), (412.04, 4), (365.54, 3)] #, (375.88, 3), (379.75, 3), (632.92, 5), (127.89, 1), (835.71, 6), (200.21, 1)] 
x = pulp.LpVariable.dicts('x', range(len(data)), lowBound=0, upBound=7, cat=pulp.LpInteger) 

numerator = dict((i,tup[0]) for i,tup in enumerate(data)) 
denom_int = dict((i,tup[1]) for i,tup in enumerate(data)) 

problem = pulp.LpProblem('Mixed Integer Linear Programming', sense=pulp.LpMinimize) 

# objective function (doesn't work) 
# TypeError: unsupported operand type(s) for /: 'float' and 'LpAffineExpression' 
problem += sum([numerator[i]/(denom_int[i] + x[i]) for i in range(len(data))]) 

problem.solve() 

for v in problem.variables(): 
    print(v.name, "=", v.varValue) 

---

与scipy.optimize蛮力解决方案

您可以使用brute，范围为slice s，每个x在您的功能中。如果你的函数中有3个x，你的范围元组中也有3个。所有这一切的关键是要步大小的1添加到slice(start, stop,step)这样slice(#, #, 1)。

from scipy.optimize import brute 
import itertools 

def f(x): 
    return (481.79/(5+x[0]))+(412.04/(4+x[1]))+(365.54/(3+x[2])) 

ranges = (slice(0, 9, 1),) * 3 
result = brute(f, ranges, disp=True, finish=None) 
print(result) 

---

itertools解决方案

或者您可以使用itertools生成所有组合：

combinations = list(itertools.product(*[[0,1,2,3,4,5,6,7,8]]*3)) 

values = [] 
for combination in combinations: 
    values.append((combination, f(combination))) 

best = [c for c,v in values if v == min([v for c,v in values])] 
print(best) 

注：这是你的原始功能的缩小版例如目的。

Answer 2

一两件事，可能会帮助你的问题，你可以有一个约束为：

max([x-int(x)])=0 

这不会完全解决你的问题，该算法将仍然尝试和欺骗，你会得到的值与一些水平错误~±5e-10，它仍然会尝试和优化，只是由于在scipy的算法中的错误，但它总比没有好。

cons = ({'type':'eq', 'fun': con}, 
     {'type':'eq','fun': lambda x : max([x[i]-int(x[i]) for i in range(len(x))])}) 

已经测试了这个过程的一些优化，我知道了解决方案，这个过程是比无约束搜索的初始值更敏感，它得到相当准确的答案，但是该解决方案实际上可能不会找到真正的价值，你基本上需要优化过程的大幅跳跃（它使用什么来确保它不是优化到本地最小值）来搜索样本空间，因为较小的增量通常不足以移动到下一个数字。