[OR-Tools 스터디] Linear Sum Assignment Solver

이번 섹션에서는 linear sum assignment solver에 대해 기술할 것이다. 이는 단순한 assignment problem을 위한 전문 solver이며,

이는 MIP 혹은 CP-SAT solver보다 더 빠르게 동작할 수 있다.

그러나 MIP와 CP-SAT solver들은 더 광범위한 배열에 대한 문제도 다룰 수 있기에 대부분의 경우, 이들이 최고의 옵션이다.

 

Cost matrix

노동자들과 일의 비용들이 아래 표로 주어졌다.

아래 섹션들에서 linear sum assignment solver를 사용한 assignment problem을 푸는 파이썬 프로그램을 보여준다.

 

import numpy as np
from ortools.graph.python import linear_sum_assignment

def LinearSumAssignmentSolver():
    #define the data
    costs = np.array([
        [90,76,75,70],
        [35,85,55,65],
        [125,95,90,105],
        [45,110,95,115],
    ])

    #let's transform this into 3 parallel vectors(start_nodes, end_nodes, arc_costs)
    #np.meshgrid : 1차원 좌표 배열에서 N차원 직사각형 격자를 만드는 함수로 2차원 그리드를 만들 것이라면 그리드로 지정할 x, y범위를 파라미터로 넘겨준다.

    end_nodes_unraveled, start_nodes_unraveled = np.meshgrid(
        np.arange(costs.shape[1]), #4 (첫번째 튜플 내부의 갯수), array([0,1,2,3])
        np.arange(costs.shape[0])  #4 (전체 튜플의 갯수), array([0,1,2,3])
    )
    start_nodes = start_nodes_unraveled.ravel()
    end_nodes = end_nodes_unraveled.ravel()
    arc_costs = costs.ravel()

    #배열은 cost matrix이며 i,j entry는 노동자 i가 j일을 수행할 때의 비용이다.
    #matrix의 행에 따르면 4명의 노동자들이 있고, 열에 따르면 4개의 일이 있다.

    #create the solver
    #여기서는 linear assignment solver를 사용한다.
    assignment = linear_sum_assignment.SimpleLinearSumAssignment()

    #add the constraints
    #노동자와 일에 대해 반복문으로써 solver에게 비용을 더하는 코드이다.
    assignment.add_arcs_with_cost(start_nodes, end_nodes, arc_costs)

    #invoke the solver
    status = assignment.solve()

    if status == assignment.OPTIMAL:
        print(f'Total cost = {assignment.optimal_cost()}\n')
        for i in range(0, assignment.num_nodes()):
            print(f'Worker {i} assigned to task {assignment.right_mate(i)}.'+
                  f' Cost = {assignment.assignment_cost(i)}')
    elif status == assignment.INFEASIBLE:
        print('No assignment.INFEASIBLE:')
    elif status == assignment.POSSIBLE_OVERFLOW:
        print('Some input costs are too large and may cause an integer overflow.')

LinearSumAssignmentSolver()

 

 

아래 그래프에서 dashed edge들로 정답을 보여준다.

dashed edge 옆에 있는 숫자들이 그것들의 비용이다. 이 assignment에 대한 전체 wait time은 dashed edge들의 비용을 모두 더한 것으로 총 265이다. 

 

이 그래프 이론에서, 왼쪽 모든 노드에 오른쪽 노드가 하나씩 매치된 bipartite graph(동일한 집합끼리 간선이 연결되지 않은 것)의 edge들의 집합을 perfect matching이라고 부른다. 

 

Solution when workers can't perform all tasks

이전 예시에서, 우리는 모든 노동자들이 모든 일들을 수행할 수 있다고 가정하였다. 그러나 그것은 항상 유효하지 않다.

노동자가 다양한 이유들로 인해 한두가지 일을 수행할 수 없을지도 모른다.

그러나 위의 코드에서 이에 대해 수정하는 것은 어렵지 않다.

 

예를 들어, 노동자0이 3번 일을 수행할 수 없다고 가정하자.

프로그램에서 이를 계정에 기록되도록 수정하는 법은 다음과 같다.

1. 비용 matrix의 0,3 entry를 'NA'로 바꾼다.

costs = np.array([
    [90,76,75,'NA'],
    [35,85,55,65],
    [125,95,90,105],
    [45,110,95,115],
])

 

2. solver에게 비용을 부여하는 코드에서, if cost[worker][task] != 'NA' 코드를 추가한다. 

for worker in range(0, costs.shape[1]):
    for task in range(0, costs.shape[0]):
        if costs[worker][task] != 'NA':
            assignment.AddArcWithCost(worker, task, costs[worker][task])

 

전체 비용은 original problem보다는 더 높아졌다. 이는 original problem에서는 optimal solution으로 노동자 0이 3번째 일에 할당되었는데, 수정된 문제에서는 assignment가 허용되지 않기 때문에  놀랄 일은 아니다. 

 

만약 더 많은 노동자들이 일을 수행할 수 없는 일이 일어나는 것을 보고자 한다면, 어떠한 일을 수행할 수 없는 추가적인 노동자들을 표시하기 위해 아래와 같이 비용 matrix에서 'NA'로 더 많은 entry들을 대체시키면 된다. 

cost = [[90, 76, 'NA', 'NA'],
        [35, 85, 'NA', 'NA'],
        [125, 95, 'NA','NA'],
        [45, 110, 95, 115]]

위와 같이 수행한다면, negative 결과를 얻게될 것이다. 

 

이것은 각 노동자들이 다 다른 일들을 수행해야하는데, 각 노동자들에게 일을 부여할 방법이 없기 때문이다.

아래 그래프에서 그 이유를 볼 수 있을 것이다. 

(비용 matrix에 따라 'NA'의 값에 대한 edge는 존재하지 않는다.)

 

노동자 0,1,2에 대한 노드들이 0,1번째 일에만 연결되어있기에 노동자들에게 일을 구분시켜 할당할 수가 없다. 

 

The Marriage Theorem

이는 그래프 이론에서 잘 알려진 결과로 The Marriage Theorem이라고도 부른다. 이는 bipartite graph에서 왼쪽 노드 각각에 오른쪽에 있는 것을 할당할 수 있을 때를 말한다. 이러한 assignment의 경우 perfect matchinng이라고 부른다. 

간단히 말해서, 이 이론은 왼쪽(앞의 예와 같은) 모서리가 오른쪽에 더 작은 노드 집합으로 이어지는 노드의 부분집합이 없다면 이것이 가능하다고 말한다. 

 

더 정확히 말하면, 이 이론은 그래프에서 왼쪽에 있는 노드의 어떠한 부분집합 S에 대해, 그래프의 오른쪽에 있는 노드 집합이 적어도 S만큼 클 경우에만 완벽하게 일치한다고 말한다. 

 

Reference : 

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

선형 합 할당 문제 해결사  |  OR-Tools  |  Google Developers