[OR-Tools 스터디] Assignment with Allowed Groups

13명의 노동자가 있으며 이 수는 0~11로 표현한다. 허용되는 그룹들은 다음 작업자 쌍의 조합이다.

group1 =  [[2, 3],       # Subgroups of workers 0 - 3
             [1, 3],
             [1, 2],
             [0, 1],
             [0, 2]]
group2 =  [[6, 7],       # Subgroups of workers 4 - 7
             [5, 7],
             [5, 6],
             [4, 5],
             [4, 7]]
group3 =  [[10, 11],     # Subgroups of workers 8 - 11
             [9, 11],
             [9, 10],
             [8, 10],
             [8, 11]]

허용된 그룹은 그룹1, 2, 3 각각으로부터 한 쌍씩 세 쌍의 조합일 수 있다.
예를들어, [2,3], [6,7], [10,11]의 조합은 [2,3,6,7,10,11]로부터 나온 허용된 그룹이다.
세개의 집합 각각이 총 5개의 element들을 포함하고 있기 때문에, 허용된 그룹의 전체 수는 5 * 5* 5 = 125이다.

노동자들의 그룹은 허용된 그룹들 중 하나에라도 속한다면 문제의 해결책이 될 수 있다.
다르게 말하면, 실현 가능한 집합은 constraint 중 하나가 만족되는 점으로 구성된다.
non-convex problem의 예이다.

대조적으로 이전에 기술되었던 MIP 예제는 convex problem이다 : 어떤 점이 실현가능하도록 하기 위해서는, 모든 constraint들이 반드시 만족되어야한다.

이와 같은 non-convex 문제의 경우, CP-SAT solver가 일반적으로 MIP solver보다 빠르다.
따르는 섹션은 CP-SAT solver와 MIP solver를 사용하여 문제에 대한 해결책을 보여주고, 두 solver들에 대한 해답 시간을 비교한다.

CP-SAT solution

 

# CP-SAT solution

from ortools.sat.python import cp_model

def CPSAT():
    #define the data
    costs = [
        [90, 76, 75, 70, 50, 74],
        [35, 85, 55, 65, 48, 101],
        [125, 95, 90, 105, 59, 120],
        [45, 110, 95, 115, 104, 83],
        [60, 105, 80, 75, 59, 62],
        [45, 65, 110, 95, 47, 31],
        [38, 51, 107, 41, 69, 99],
        [47, 85, 57, 71, 92, 77],
        [39, 63, 97, 49, 118, 56],
        [47, 101, 71, 60, 88, 109],
        [17, 39, 103, 64, 61, 92],
        [101, 45, 83, 59, 92, 27],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    #create the allowed groups
    #CP-SAT solver에 대해 노동자들의 허용된 그룹을 정의하기 위해, 그룹에 속해있는 노동자들을 나타내기 위한 binary 배열을 만들어야 한다.
    #예로, group1(노동자 0-3)에 대해 binary vector [0, 0, 1, 1]을 노동자 2,3을 포함한 그룹으로 정의한다.

    group1 = [
        [0, 0, 1, 1],  # Workers 2, 3
        [0, 1, 0, 1],  # Workers 1, 3
        [0, 1, 1, 0],  # Workers 1, 2
        [1, 1, 0, 0],  # Workers 0, 1
        [1, 0, 1, 0],  # Workers 0, 2
    ]

    group2 = [
        [0, 0, 1, 1],  # Workers 6, 7
        [0, 1, 0, 1],  # Workers 5, 7
        [0, 1, 1, 0],  # Workers 5, 6
        [1, 1, 0, 0],  # Workers 4, 5
        [1, 0, 0, 1],  # Workers 4, 7
    ]

    group3 = [
        [0, 0, 1, 1],  # Workers 10, 11
        [0, 1, 0, 1],  # Workers 9, 11
        [0, 1, 1, 0],  # Workers 9, 10
        [1, 0, 1, 0],  # Workers 8, 10
        [1, 0, 0, 1],  # Workers 8, 11
    ]
    #CP-SAT는 반복문 내에서 그 벡터들의 모든 125개 조합들을 만들어낼 필요가 없다.
    #CP-SAT solver는 그에 대해 AllowedAssignments라는 메소드를 제공해주는데, 이는 우리가 노동자들의 세 집합(0-3, 4-7, 8-11) 각각에 대해 허용된 그룹으로 개별적으로 constraint들을 정의할 수 있도록 해준다.

    model = cp_model.CpModel()

    #create the variables
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = model.NewBoolVar(f'x[{worker},{task}]')

    #add the constraints
    #each worker is assigned to at most one task (각 작업자는 최대 하나의 일을 부여받음)
    for worker in range(num_workers):
        model.AddAtMostOne(x[worker, task] for task in range(num_tasks))
    #each task is assigned to exactly one worker (각 일들은 한명의 작업자에게 부여됨)
    for task in range(num_tasks):
        model.AddExactlyOne(x[worker, task] for worker in range(num_workers))

    #create the objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    model.Minimize(sum(objective_terms))

    #invoke the solver
    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    #display the results
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        print(f'Total cost = {solver.ObjectiveValue()}\n')
        for worker in range(num_workers):
            for task in range(num_tasks):
                if solver.BooleanValue(x[worker, task]):
                    print(f'Worker {worker} assigned to task {task}.' +
                          f'Cost = {costs[worker][task]}')
    else:
        print('No solution found.')
CPSAT()

 

 

MIP solution

#MIP Solution
from ortools.linear_solver import pywraplp

def MIP():
    #define data
    costs = [
        [90, 76, 75, 70, 50, 74],
        [35, 85, 55, 65, 48, 101],
        [125, 95, 90, 105, 59, 120],
        [45, 110, 95, 115, 104, 83],
        [60, 105, 80, 75, 59, 62],
        [45, 65, 110, 95, 47, 31],
        [38, 51, 107, 41, 69, 99],
        [47, 85, 57, 71, 92, 77],
        [39, 63, 97, 49, 118, 56],
        [47, 101, 71, 60, 88, 109],
        [17, 39, 103, 64, 61, 92],
        [101, 45, 83, 59, 92, 27],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    #create the allowed groups
    group1 = [  # Subgroups of workers 0 - 3
        [2, 3],
        [1, 3],
        [1, 2],
        [0, 1],
        [0, 2],
    ]

    group2 = [  # Subgroups of workers 4 - 7
        [6, 7],
        [5, 7],
        [5, 6],
        [4, 5],
        [4, 7],
    ]

    group3 = [  # Subgroups of workers 8 - 11
        [10, 11],
        [9, 11],
        [9, 10],
        [8, 10],
        [8, 11],
    ]

    #declare the solver
    #create the mip solver with the SCIP backend
    solver = pywraplp.Solver.CreateSolver('SCIP')
    if not solver:
        return

    #create the variables
    # x[worker, task] is an array of 0-1 variables, which will be 1
    #if the worker is assigned to the task.
    x = {}
    for worker in range(num_workers):
        for task in range(num_tasks):
            x[worker, task] = solver.BoolVar(f'x[{worker}, {task}]')

    #add the constraints
    #total size of the tasks each worker takes on is at most total_size_max
    for worker in range(num_workers):
        solver.Add(
            solver.Sum([x[worker, task] for task in range(num_tasks)]) <= 1
        )

    #each task is assigned to exactly one worker.
    for task in range(num_tasks):
        solver.Add(
            solver.Sum([x[worker, task] for worker in range(num_workers)]) == 1
        )

    #create the objective
    objective_terms = []
    for worker in range(num_workers):
        for task in range(num_tasks):
            objective_terms.append(costs[worker][task] * x[worker, task])
    solver.Minimize(solver.Sum(objective_terms))

    #invoke the solver
    status = solver.Solve()

    if status == pywraplp.Solver.OPTIMAL or status == pywraplp.Solver.FEASIBLE:
        print(f'Total cost = {solver.Objective().Value()}\n')
        for worker in range(num_workers):
            for task in range(num_tasks):
                if x[worker, task].solution_value() > 0.5:
                    print(f'Worker {worker} assigned to task {task}.' +
                          f'Cost : {costs[worker][task]}')
    else:
        print('No solution found.')

MIP()

 

 

결과적으로 CP-SAT이 MIP solver보다 훨씬 빠름

 

Reference:

https://developers.google.com/optimization/assignment/assignment_groups

허용된 그룹이 있는 할당  |  OR-Tools  |  Google Developers