將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))])}) 

已經測試了這個過程的一些優化，我知道了解決方案，這個過程是比無約束搜索的初始值更敏感，它得到相當準確的答案，但是該解決方案實際上可能不會找到真正的價值，你基本上需要優化過程的大幅跳躍（它使用什麼來確保它不是優化到本地最小值）來搜索樣本空間，因爲較小的增量通常不足以移動到下一個數字。