Portfolio Selection in Python with Fixed-Set Constraints

Question

I am working on a project where I am trying to choose the optimal subset of players from a set of 125 players (example below)

Limitations:

a) Number of players = 3

b) Sum of prices <= 30

Max optimization function (total votes)

        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

I looked at the scipy optimize package, but I cannot find a way to limit the universe to this subset. Can someone tell me if there is a library that will do this? Thanks

Answer 1

The problem is well suited for formulation in the form of a mathematical program and can be solved using various optimization libraries.

k-item-.

, PuLP. , .

easy_install pulp

, , , PuLP .

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)

, 3 125 , , 0,5 .

Answer 2

- - 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);

, scipy (, this).

:

• Minizinc Python , . .

. , , : , .

Answer 3

@CaptainTrunky is correct, scipy.minimize will not work here.

Here is a terrible workaround using itertools, please ignore if one of the other methods worked. Think that to attract 3 players out of 125 creates 317,750 combinations, n! / ((N - k)! * K!). The lead time on the main circuit is ~ 6 m.

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