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と指摘しました。

ここ

が（多分、誰かが理由を把握することができます）、それは、実際に働いていた場合、あなたがパルプでそれを行うことができる方法です：あなたが使用することができますscipy.optimize

と

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) 

---

ブルートソリューション関数内の各xに対してはbrute、範囲はsliceです。あなたの関数に3つのxがあるならば、範囲タプルに3 sliceもあります。このすべての鍵は、そうslice(#, #, 1)slice(start, stop,step)に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))])}) 

私は解決策を知っているいくつかの最適化にこのプロセスをテストした、このプロセスは、制約のない検索よりも初期値に敏感である解決策が実際に真の価値を見つけないかもしれないが、それは、かなり正確な答えを得ます最小の増分は通常次の数に移動するのに十分ではないので、サンプル空間を検索するために、基本的には最適化プロセス（ローカル最小に最適化されていないことを確認するために使用するもの）の大きな飛躍が必要です。