大量写出适当的约束以产生可行的解决方案

Question

我正在尝试为特定数量的灯具选择15名球员的模型。我的LpProblem由2个二进制变量播放器和固件组成。

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"

我的目标是从固定装置中选取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])

Answer 1

我建议引入其他二进制变量，这些变量可用于跟踪在结构f和夹具f-1之间是否进行了更改。然后，您可以对允许的更改数量施加限制。

在下面的示例代码中，如果您注释掉最后一个约束，您会发现可以实现更高的目标，但是需要付出更多的更改。还要注意，我为目标函数中的非零changes变量添加了一个小小的惩罚-这是在不进行更改的情况下将其强制为零-这种方法不需要此小的惩罚，但是可能让它更容易看到正在发生的事情。

具有最后一个约束应获得目标值118，但只有目标值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)