python - 具有固定集合约束的 Python 投资组合选择

Question

我正在做一个项目，我试图从一组 125 名玩家中选择最佳玩家子集(如下例)

约束是:

a) 玩家数量 = 3

b) 价格总和 <= 30

优化函数为Max(Sum of 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

我查看了 scipy 优化包，但我无法在任何地方找到将宇宙约束到这个子集的方法。如果有图书馆可以做到这一点，谁能指点我？谢谢

Answer 1

这个问题很适合表述为数学程序，可以用不同的优化库来解决。

它被称为精确的 k 项背包问题。

例如，您可以使用 Package PuLP。它具有与不同优化软件包的接口(interface)，但捆绑了一个免费的求解器。

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)

使用 Brad Solomon 使用的相同随机数据从 125 名玩家中抽取 3 名玩家的运行时间在我的机器上为 0.5 秒。