纸浆编写适当的约束以产生可行的解决方案
Pulp writing proper constraints to produce feasible solution
我正在尝试为特定数量的固定装置选择 15 名球员的模型。我的 LpProblem 由 2 个二进制变量 player 和 fixture 组成。
choices = LpVariable.dicts(
"Choices", (fixtures, constraints["player"]), 0, 1, LpBinary)
我想使用此约束限制为一组固定装置选择的球员数量(这很糟糕 - 它计算所有选择而不是使用的球员数量):
prob += lpSum([choices[f][p] for f in fixtures for p in constraints["player"]]
) <= player_count + len(fixtures) - 1, "Transfers limit"
我还设置了一个限制条件,为每场比赛恰好挑选 15 名球员:
for fixture in fixtures:
prob += lpSum([choices[fixture][p]
for p in constraints["player"]]) == player_count, str(fixture) + " Total of " + str(player_count) + " players"
我的目标是从 fixture 到 fixture 选择 15 个和少量更改,但由于某些原因,这些限制产生了不可行的问题。例如,如果我搜索 fixtures = [0,1,2]
,当我将传输限制设置为 45 (15*3) 时,问题就变得可行了。我不确定如何制定转移限制约束来实现我的目标。
示例:
players = [1, 2, 3, 4, 5, 6]
fixtures = [1, 2, 3]
prob = LpProblem(
"Fantasy football selection", LpMaximize)
choices = LpVariable.dicts(
"Players", (fixtures, players), 0, 1, LpBinary)
# objective function
prob += lpSum([predict_score(f, p) * choices[f][p]
for p in players for f in fixtures]), "Total predicted score"
# constraints
for f in fixtures:
# total players for each fixture
prob += lpSum([choices[f][p] for p in players]) == 2, ""
if f != fixtures[0]:
# max of 1 change between fixtures
prob += lpSum([1 if choices[f-1][p] != choices[f]
[p] else 0 for p in players]) <= 2, ""
prob.solve()
print("Status: ", LpStatus[prob.status])
我建议引入额外的二进制变量,这些变量可用于跟踪图片 f
和夹具 f-1
之间是否发生了变化。然后,您可以对允许的更改数量施加限制。
在下面的示例代码中,如果您注释掉最后一个约束,您会发现实现了更高的 objective,但代价是进行了更多更改。另请注意,我为 objective 函数中的非零 changes
变量添加了一个小惩罚 - 这是在未进行更改时强制它们为零 - 不需要这个小惩罚此方法可行,但可能更容易查看正在发生的事情。
没有最后一个约束应该得到 118
的 objective 值,但只有 109
的值才能实现。
from pulp import *
import random
players = [1, 2, 3, 4, 5]
fixtures = [1, 2, 3, 4]
random.seed(42)
score_dict ={(f, p):random.randint(0,20) for f in fixtures for p in players}
def predict_score(f,p):
return score_dict[(f,p)]
prob = LpProblem(
"Fantasy football selection", LpMaximize)
# Does fixture f include player p
choices = LpVariable.dicts(
"choices", (fixtures, players), 0, 1, LpBinary)
changes = LpVariable.dicts(
"changes", (fixtures[1:], players), 0, 1, LpBinary)
# objective function
prob += lpSum([predict_score(f, p) * choices[f][p]
for p in players for f in fixtures]
) - lpSum([[changes[f][p] for f in fixtures[1:]] for p in players])/1.0e15, "Total predicted score"
# constraints
for f in fixtures:
# Two players for each fixture
prob += lpSum([choices[f][p] for p in players]) == 2, ""
if f != fixtures[0]:
for p in players:
# Assign change constraints, force to one if player
# is subbed in or out
prob += changes[f][p] >= (choices[f][p] - choices[f-1][p])
prob += changes[f][p] >= (choices[f-1][p] - choices[f][p])
# Enforce only one sub-in + one sub-out per fixture (i.e. at most one change)
# prob += lpSum([changes[f][p] for p in players]) <= 2
prob.solve()
print("Status: ", LpStatus[prob.status])
print("Objective Value: ", prob.objective.value())
choices_soln = [[choices[f][p].value() for p in players] for f in fixtures]
print("choices_soln")
print(choices_soln)
changes_soln = [[changes[f][p].value() for p in players] for f in fixtures[1:]]
print("changes_soln")
print(changes_soln)
我正在尝试为特定数量的固定装置选择 15 名球员的模型。我的 LpProblem 由 2 个二进制变量 player 和 fixture 组成。
choices = LpVariable.dicts(
"Choices", (fixtures, constraints["player"]), 0, 1, LpBinary)
我想使用此约束限制为一组固定装置选择的球员数量(这很糟糕 - 它计算所有选择而不是使用的球员数量):
prob += lpSum([choices[f][p] for f in fixtures for p in constraints["player"]]
) <= player_count + len(fixtures) - 1, "Transfers limit"
我还设置了一个限制条件,为每场比赛恰好挑选 15 名球员:
for fixture in fixtures:
prob += lpSum([choices[fixture][p]
for p in constraints["player"]]) == player_count, str(fixture) + " Total of " + str(player_count) + " players"
我的目标是从 fixture 到 fixture 选择 15 个和少量更改,但由于某些原因,这些限制产生了不可行的问题。例如,如果我搜索 fixtures = [0,1,2]
,当我将传输限制设置为 45 (15*3) 时,问题就变得可行了。我不确定如何制定转移限制约束来实现我的目标。
示例:
players = [1, 2, 3, 4, 5, 6]
fixtures = [1, 2, 3]
prob = LpProblem(
"Fantasy football selection", LpMaximize)
choices = LpVariable.dicts(
"Players", (fixtures, players), 0, 1, LpBinary)
# objective function
prob += lpSum([predict_score(f, p) * choices[f][p]
for p in players for f in fixtures]), "Total predicted score"
# constraints
for f in fixtures:
# total players for each fixture
prob += lpSum([choices[f][p] for p in players]) == 2, ""
if f != fixtures[0]:
# max of 1 change between fixtures
prob += lpSum([1 if choices[f-1][p] != choices[f]
[p] else 0 for p in players]) <= 2, ""
prob.solve()
print("Status: ", LpStatus[prob.status])
我建议引入额外的二进制变量,这些变量可用于跟踪图片 f
和夹具 f-1
之间是否发生了变化。然后,您可以对允许的更改数量施加限制。
在下面的示例代码中,如果您注释掉最后一个约束,您会发现实现了更高的 objective,但代价是进行了更多更改。另请注意,我为 objective 函数中的非零 changes
变量添加了一个小惩罚 - 这是在未进行更改时强制它们为零 - 不需要这个小惩罚此方法可行,但可能更容易查看正在发生的事情。
没有最后一个约束应该得到 118
的 objective 值,但只有 109
的值才能实现。
from pulp import *
import random
players = [1, 2, 3, 4, 5]
fixtures = [1, 2, 3, 4]
random.seed(42)
score_dict ={(f, p):random.randint(0,20) for f in fixtures for p in players}
def predict_score(f,p):
return score_dict[(f,p)]
prob = LpProblem(
"Fantasy football selection", LpMaximize)
# Does fixture f include player p
choices = LpVariable.dicts(
"choices", (fixtures, players), 0, 1, LpBinary)
changes = LpVariable.dicts(
"changes", (fixtures[1:], players), 0, 1, LpBinary)
# objective function
prob += lpSum([predict_score(f, p) * choices[f][p]
for p in players for f in fixtures]
) - lpSum([[changes[f][p] for f in fixtures[1:]] for p in players])/1.0e15, "Total predicted score"
# constraints
for f in fixtures:
# Two players for each fixture
prob += lpSum([choices[f][p] for p in players]) == 2, ""
if f != fixtures[0]:
for p in players:
# Assign change constraints, force to one if player
# is subbed in or out
prob += changes[f][p] >= (choices[f][p] - choices[f-1][p])
prob += changes[f][p] >= (choices[f-1][p] - choices[f][p])
# Enforce only one sub-in + one sub-out per fixture (i.e. at most one change)
# prob += lpSum([changes[f][p] for p in players]) <= 2
prob.solve()
print("Status: ", LpStatus[prob.status])
print("Objective Value: ", prob.objective.value())
choices_soln = [[choices[f][p].value() for p in players] for f in fixtures]
print("choices_soln")
print(choices_soln)
changes_soln = [[changes[f][p].value() for p in players] for f in fixtures[1:]]
print("changes_soln")
print(changes_soln)