ポートフォリオ選択の固定設定

Question

私は125人の選手の集合から、選手の最適なサブセットを選択しようとしているプロジェクトに取り組んでいます

（下記の例）

制約は以下のとおりです。

価格の選手の

a）は数= 3

b）の合計は< = 30

最適化機能は、投票のマックス（和）である

 Player Vote Price 
    William Smith 0.67 8.6 
Robert Thompson 0.31 6.7 
Joseph Robinson 0.61 6.2 
Richard Johnson 0.88 4.3 
    Richard Hall 0.28 9.7 

私はscipy最適化パッケージを見ましたが、私はこのサブセットに宇宙を制約する方法を見つけることができません。それを行うライブラリがあれば誰でも私を指摘できますか？ おかげ

Answer 1

あなたの問題は、A）制約のタスク離散最適化です。離散変数を導入してを撮影/撮影しないでください。プレイヤーを紹介する必要があります。次Minizinc擬似コードを考えてみましょう：

array[players_num] of var bool: taken_players; array[players_num] of float: votes; array[players_num] of float: prices; constraint sum (taken_players * prices) <= 30; constraint sum (taken_players) = 3; solve maximize sum (taken_players * votes); 

は、私の知る限りでは、あなたはこのような問題（例えばthis）を解決するためにscipyのダウンロードに使用することはできません。

次の方法であなたの問題を解決することができます：

1. あなたはPythonでMinizincの問題を発生し、外部ソルバーを呼び出すことによってそれを解決することができます。よりスケーラブルで堅牢なようです。
2. あなたは二番目のオプションは、あなたのために簡単であるように思わsimulated annealing
3. Mixed integer approach

を使用することができます。しかし、個人的には、私は最初の方が好きです。さまざまな制約の広い範囲を導入することができ、問題の定式化はより自然で明快です。

Answer 2

@CaptainTrunkyが正しい場合、scipy.minimizeはここでは機能しません。

ここでは、itertoolsを使用した非常に愚かな回避策があります。他の方法のいずれかが機能している場合は、無視してください。 25から3人のプレイヤーを引き出すと、n！/（（n - k）！* k！）の317,750の組み合わせが作成されます。メインループのランタイム〜6m。

from itertools import combinations 

df = DataFrame({'Player' : np.arange(0, 125), 
       'Vote' : 10 * np.random.random(125), 
       'Price' : np.random.randint(1, 10, 125) 
       }) 

df 
Out[109]: 
    Player Price  Vote 
0   0  4 7.52425 
1   1  6 3.62207 
2   2  9 4.69236 
3   3  4 5.24461 
4   4  4 5.41303 
..  ... ...  ... 
120  120  9 8.48551 
121  121  8 9.95126 
122  122  8 6.29137 
123  123  8 1.07988 
124  124  4 2.02374 

players = df.Player.values 
idx = pd.MultiIndex.from_tuples([i for i in combinations(players, 3)]) 

votes = [] 
prices = [] 

for i in combinations(players, 3): 
    vote = df[df.Player.isin(i)].sum()['Vote'] 
    price = df[df.Player.isin(i)].sum()['Price'] 
    votes.append(vote); prices.append(price) 

result = DataFrame({'Price' : prices, 'Vote' : votes}, index=idx) 

# The index below is (first player, second player, third player) 

result[result.Price <= 30].sort_values('Vote', ascending=False) 
Out[128]: 
      Price  Vote 
63 87 121 25.0 29.75051 
    64 121 20.0 29.62626 
64 87 121 19.0 29.61032 
63 64 87 20.0 29.56665 
    65 121 24.0 29.54248 
     ...  ... 
18 22 78 12.0 1.06352 
    23 103 20.0 1.02450 
22 23 103 20.0 1.00835 
18 22 103 15.0 0.98461 
     23 14.0 0.98372 

Answer 3

問題は、数学的なプログラムとして処方することに適していると異なる最適化ライブラリを用いて解決することができます。

正確なkアイテムナップザック問題として知られています。

たとえば、パッケージPuLPを使用することができます。さまざまな最適化ソフトウェアパッケージとのインターフェースを備えていますが、フリーソルバにバンドルされています。

easy_install pulp 

無料ソルバーは、多くの場合、市販のものより道遅いですが、私は、パルプが標準ソルバーを使用して、問題の合理的に大規模なバージョンを解決することができるはずだと思います。次のように

あなたの問題は、パルプを用いて解決することができます。

from pulp import * 

# Data input 
players = ["William Smith", "Robert Thompson", "Joseph Robinson", "Richard Johnson", "Richard Hall"] 
vote = [0.67, 0.31, 0.61, 0.88, 0.28] 
price = [8.6, 6.7, 6.2, 4.3, 9.7] 

P = range(len(players)) 

# Declare problem instance, maximization problem 
prob = LpProblem("Portfolio", LpMaximize) 

# Declare decision variable x, which is 1 if a 
# player is part of the portfolio and 0 else 
x = LpVariable.matrix("x", list(P), 0, 1, LpInteger) 

# Objective function -> Maximize votes 
prob += sum(vote[p] * x[p] for p in P) 

# Constraint definition 
prob += sum(x[p] for p in P) == 3 
prob += sum(price[p] * x[p] for p in P) <= 30 

# Start solving the problem instance 
prob.solve() 

# Extract solution 
portfolio = [players[p] for p in P if x[p].varValue] 
print(portfolio) 

ブラッド・ソロモンで使用したのと同じランダムデータで125から3人の選手を描画するためのランタイムが私のマシンで0.5秒です。