Реализация алгоритма минимальных затрат или распределения групп с условиями

Question

Я пытаюсь распределить участников по группам Tn и подгруппам TnSm в зависимости от их предпочтений. Я использую метод Minimum Cost Flow, используя инструменты OR от Google в Python. Рассмотрим следующую таблицу предпочтений:

      T1S1  T1S2    T1S3    T2S1    T2S2    T2S3
name1 1     0       3       2       2       3
name2 2     1       1       1       0       1
name3 0     2       1       2       2       3
name4 3     2       3       3       0       0
name5 1     0       2       3       1       2
...

Обе группы Tn имеют в общей сложности 6 мест и состоят из 3 подгрупп TnSm по 2 места в каждой. У меня есть несколько условий, перечисленных ниже:

1. Всего нет. количество участников меньше или равно сумме всех групповых пятен (= 12)
2. Каждый участник может входить в 1-3 подгруппы, но только если подгруппы входят в одну группу
3. Участник должен быть распределен по каждому из этих 12 групповых мест

Я могу распределить участников по нескольким подгруппам, создав узел для каждого участника с мощностью = 3 в источнике и узел для каждой подгруппы с вместимость = 2 в приемнике:

capacities = [3,3,3,3,...] + [1,1,1,1...] + [2,2,2,2,2,2]

Но как теперь я могу убедиться, что участник назначен только 2-й или 3-й подгруппе, если эта конкретная подгруппа является частью группы Tn?

if min_cost_flow_2.SolveMaxFlowWithMinCost() == min_cost_flow_2.OPTIMAL:
    print('Minimum cost:', min_cost_flow_2.OptimalCost(), min_cost_flow_2.MaximumFlow())
    for arc in range(min_cost_flow_2.NumArcs()):
        if min_cost_flow_2.Tail(arc) != source and min_cost_flow_2.Head(arc) != sink:
            if min_cost_flow_2.Flow(arc) > 0:
                print(" ")
                print("***worker %d assigned to team %d at cost: %d" % (min_cost_flow_2.Tail(arc),min_cost_flow_2.Head(arc),min_cost_flow_2.UnitCost(arc)))

Answer 1

Вот мое быстрое и грязное предложение.
примечание: я добавил ограничение

• Участник не может использовать оба места в подгруппах.

#!/usr/bin/env python3
from ortools.sat.python import cp_model


def main():
    participants = [
        "name1",
        "name2",
        "name3",
        "name4",
        "name5",
        "name6",
        "name7",
        "name8",
        #"name9",
        #"name10",
        #"name11",
        #"name12",
    ]

    preferences = [
        #T0 T0 T0 T0 T0 T0 T1 T1 T1 T1 T1 T1
        #S0 S0 S1 S1 S2 S2 S0 S0 S1 S1 S2 S2
        # a  b  a  b  a  b  a  b  a  b  a  b
        [1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3],  # 1
        [2, 2, 3, 3, 1, 1, 1, 1, 0, 0, 1, 1],  # 2
        [0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3],  # 3
        [3, 3, 2, 2, 3, 3, 3, 3, 0, 0, 0, 0],  # 4
        [1, 1, 0, 0, 2, 2, 3, 3, 1, 1, 2, 2],  # 5
        [1, 1, 0, 0, 3, 3, 2, 2, 3, 3, 2, 2],  # 6
        [2, 2, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1],  # 7
        [0, 0, 2, 2, 1, 1, 2, 2, 2, 2, 3, 3],  # 8
        [3, 3, 1, 1, 0, 0, 3, 3, 0, 0, 2, 2],  # 9
        [1, 1, 0, 0, 2, 2, 3, 3, 0, 0, 2, 2],  # 10
        [1, 1, 0, 0, 3, 3, 2, 2, 2, 2, 3, 3],  # 11
        [2, 2, 1, 1, 0, 0, 3, 3, 2, 2, 1, 1],  # 12
    ]

    num_participants = len(participants)
    all_participants = range(num_participants)

    num_groups = 2
    all_groups = range(num_groups)

    num_sub_groups = 3
    all_sub_groups = range(num_sub_groups)

    num_sub_groups_spots = 2
    all_sub_groups_spots = range(num_sub_groups_spots)
    # 2 spots per TxSy

    # Create Model
    model = cp_model.CpModel()

    # Variables
    # True if the participant is assigned to this spot
    x = {}
    for p in all_participants:
        for tn in all_groups:
            for sg in all_sub_groups:
                for sg_s in all_sub_groups_spots:
                    x[(p, tn, sg, sg_s)] = model.NewBoolVar(
                        f"x[{participants[p]},{tn},{sg},{sg_s}]")

    # True is the participant is assigned to this group
    y = {}
    for p in all_participants:
        for tn in all_groups:
            y[(p, tn)] = model.NewBoolVar(f"y[{participants[p]},{tn}]")

    # Constraints

    # Each spots is assigned to exactly one participant.
    for tn in all_groups:
        for sg in all_sub_groups:
            for sg_s in all_sub_groups_spots:
                model.Add(
                    sum(x[(n, tn, sg, sg_s)] for n in all_participants) == 1)

    # Each participant can't use both spots of any sub groups of any groups.
    for p in all_participants:
        for tn in all_groups:
            for sg in all_sub_groups:
                model.Add(
                    sum(x[(p, tn, sg, n)] for n in all_sub_groups_spots) <= 1)

    # Each participant is assigned to exactly one group.
    for p in all_participants:
        model.Add(sum(y[(p, n)] for n in all_groups) == 1)

    # A participant work in a group if it is assigned to at least one spots in the group
    for p in all_participants:
        for tn in all_groups:
            # implement y[(p, tn)] == (sum(x[(p, tn, *, *)]) >= 1)
            model.Add(
                sum(x[(p, tn, n, m)] for n in all_sub_groups
                    for m in all_sub_groups_spots) >= 1).OnlyEnforceIf(
                        y[(p, tn)])
            # implement not y[(p, tn)] == (sum(x[(p, tn, *, *)]) == 0)
            model.Add(
                sum(x[(p, tn, n, m)] for n in all_sub_groups
                    for m in all_sub_groups_spots) == 0).OnlyEnforceIf(
                        y[(p, tn)].Not())

    #model.Minimize(
    model.Maximize(
        sum([
            x[(p, tn, sg, sg_s)] * preferences[p][tn * sg * sg_s + sg * sg_s + sg_s]
            for p in all_participants
            for tn in all_groups
            for sg in all_sub_groups
            for sg_s in all_sub_groups_spots
        ]))

    # Creates the solver and solve.
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print('Maximum cost = %i' % solver.ObjectiveValue())
        print()
        for p in all_participants:
            for tn in all_groups:
                for sg in all_sub_groups:
                    for sg_s in all_sub_groups_spots:
                        if solver.Value(x[(p, tn, sg, sg_s)]) == 1:
                            print(
                                f'Participant: {participants[p]}, assigned to T{tn}S{sg}:{sg_s}, Preference({preferences[p][tn*sg*sg_s+sg*sg_s+sg_s]})'
                            )

    # Statistics.
    print()
    print('Statistics')
    print('  - conflicts       : %i' % solver.NumConflicts())
    print('  - branches        : %i' % solver.NumBranches())
    print('  - wall time       : %f s' % solver.WallTime())


if __name__ == '__main__':
    main()

решение:

./assignment.py
Maximum cost = 27

Participant: name1, assigned to T0S0:1, Preference(1)
Participant: name2, assigned to T0S1:1, Preference(3)
Participant: name3, assigned to T1S1:1, Preference(2)
Participant: name4, assigned to T1S0:0, Preference(3)
Participant: name4, assigned to T1S1:0, Preference(3)
Participant: name4, assigned to T1S2:0, Preference(3)
Participant: name5, assigned to T1S0:1, Preference(1)
Participant: name6, assigned to T1S2:1, Preference(3)
Participant: name7, assigned to T0S0:0, Preference(2)
Participant: name7, assigned to T0S1:0, Preference(2)
Participant: name7, assigned to T0S2:0, Preference(2)
Participant: name8, assigned to T0S2:1, Preference(2)

Statistics
  - conflicts       : 508560
  - branches        : 544413
  - wall time       : 42.424461 s