Правильные ограничения по написанию целлюлозы для получения приемлемого решения

Я пытаюсь смоделировать подбор 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"

Моя цель - выбрать 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])

python integer-programming pulp
person Rolfrider    schedule 17.11.2019    source источник
comment
Можете ли вы предоставить минимальный воспроизводимый пример? Кроме того, не могли бы вы дать более четкое объяснение того, какое ограничение вы пытаетесь реализовать - я прочитал текст, но до сих пор не понимаю, для чего предназначено отсутствующее ограничение.   -  person kabdulla    schedule 02.12.2019
comment
Эй, я добавил простой пример, ограничение, которое я пытаюсь реализовать, - это максимум 1 изменение между приборами, например, это приводит к недопустимому решению. Я думаю, это потому, что переменные зависят друг от друга, и это может быть нелинейное уравнение.   -  person Rolfrider    schedule 02.12.2019
comment
Обычно вы не можете использовать операторы if указанным вами способом, но будет способ сформулировать необходимое ограничение ... вам просто нужно подумать о том, какие операции / ограничения требуются для двоичных переменных. И что такое predict_score() функция?   -  person kabdulla    schedule 02.12.2019
comment
возвращает целое число, указывающее счет игрока   -  person Rolfrider    schedule 02.12.2019
comment
моя попытка ответа опубликована ниже. Обратите внимание, что для полностью минимального воспроизводимого примера вам действительно следует выполнить любой требуемый импорт, а также обеспечить минимальную реализацию любого такого функции. См., Например, пустышку predict_score(), которую я вставил в свой ответ.   -  person kabdulla    schedule 03.12.2019

Ответы (1)


arrow_upward
1
arrow_downward

Я бы порекомендовал ввести дополнительные двоичные переменные, которые можно использовать для отслеживания изменений между ficture f и fixture 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)
person kabdulla    schedule 02.12.2019