投資組合選擇在Python與約束固定設置

Question

我上一個項目，我想從一組125級的玩家選擇的玩家的最優子集工作（下面的例子）

約束條件是：

價格的

一個）的玩家數量= 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

你的問題是離散優化的任務，因爲一）約束。您應該引入離散變量來表示已採取/未採取的玩家。考慮以下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); 

據我所知，你不能使用SciPy的解決此類問題（例如this）。

您可以通過以下方法解決問題：

1. 您可以在Python產生Minizinc問題，並通過調用外部求解器解決這個問題。它似乎更具可擴展性和可靠性。
2. 您可以使用simulated annealing
3. Mixed integer approach

第二個選擇似乎是爲您簡單。但是，我個人更喜歡第一個：它允許你引入各種各樣的約束條件，問題的形成感覺更加自然和清晰。

Answer 2

@CaptainTrunky是正確的，scipy.minimize不會在這裏工作。

這是一個非常糟糕的解決方法，使用itertools，請忽略其他方法之一是否工作。考慮從125個創建317,750個組合中抽取3個玩家，n！/（（n-k）！* k！）。主循環上的運行時間〜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-item揹包問題。

例如，您可以使用Package 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級的玩家使用相同的隨機數據13759布拉德·所羅門是0.5秒我的機器上：

您的問題可以用指腹如下解決。