OR Tools 이용해서 Assignment Problem 풀어보기

할당 문제(Assignment Problem)는 작업자에게 작업(Task)을 할당하는 최소 비용 방법을 찾는 문제입니다.

예를 들어, 5명의 작업자(0번부터 4번까지)와 4개의 작업(작업0부터 작업3까지)이 주어지고, 각 작업자별 작업 비용을 나타내는 행렬(Matrix)이 주어질 때, 최소 비용으로 4개의 모든 작업을 수행하는 방법을 찾아야 합니다. 이 경우 할당 문제의 접근 방법을 적용할 수 있습니다.

이번 글에서는 Google OR-Tools를 이용하여 MIP(혼합 정수 프로그래밍) 방법을 통해 할당 문제를 해결하는 방법을 살펴보겠습니다.

작업자	작업0	작업1	작업2	작업3
0	90	80	75	70
1	35	85	55	65
2	125	95	90	95
3	45	110	95	115
4	50	100	90	100

Solver 설정

solver = pywraplp.Solver.CreateSolver('SCIP')
Python
복사

Google Or Tools에서 MIP(Mixed Integer Programming)를 위해서 기본적으로 제공하는 SCIP를 생성합니다.

Decision Variable 설정

X = {}
for i in range(num_workers):
    for j in range(num_tasks):
        X[i, j] = solver.IntVar(0, 1, '')
Python
복사

의사 결정 변수(Decision Variable) X를 정의합니다.

X는 0과 1의 두 가지 값을 갖는 2차원 배열로 구성됩니다.

정수형 의사 결정 변수를 정의할 때는 solver.IntVar() 함수를 사용합니다.

작업(Task)을 할당(Assign)하면 해당 의사 결정 변수가 1로 결정된 것으로 간주할 수 있으며,

반대의 경우에는 의사 결정 변수가 0으로 결정된 것으로 생각할 수 있습니다.

Constraint 설정

# Each worker is assigned to at most 1 task.
for i in range(num_workers):
    solver.Add(solver.Sum([X[i, j] for j in range(num_tasks)]) <= 1)

# Each task is assigned to exactly one worker.
for j in range(num_tasks):
    solver.Add(solver.Sum([X[i, j] for i in range(num_workers)]) == 1)
Python
복사

할당 문제(Assignment Problem)를 해결하기 위해서는 두 가지 제약 조건(Constraint)을 정의해야 합니다.

첫 번째 제약 조건은 각각의 작업자가 최대 1개의 업무에만 할당될 수 있다는 것입니다.

두 번째 제약 조건은 각 작업이 반드시 1명의 작업자에게 할당되어야 한다는 것입니다.

Objective Function 설정

objective_terms = []
for i in range(num_workers):
    for j in range(num_tasks):
        objective_terms.append(costs[i][j] * X[i, j])

solver.Minimize(solver.Sum(objective_terms))
Python
복사

목적 함수(Objective Function)는 모든 제약 조건을 만족하면서 비용을 최소화하는 것으로 정의할 수 있습니다.

전체 프로그램 소스

from ortools.linear_solver import pywraplp
def main():
    costs = [
        [90, 80, 75, 70],
        [35, 85, 55, 65],
        [125, 95, 90, 95],
        [45, 110, 95, 115],
        [50, 100, 90, 100],
    ]
    num_workers = len(costs)
    num_tasks = len(costs[0])

    solver = pywraplp.Solver.CreateSolver('SCIP')

    # X[i, j] is an array of 0-1 variables, which will be 1
    # if worker i is assigned to task j.
    X = {}
    for i in range(num_workers):
        for j in range(num_tasks):
            X[i, j] = solver.IntVar(0, 1, '')

    # Each worker is assigned to at most 1 task.
    for i in range(num_workers):
        solver.Add(solver.Sum([X[i, j] for j in range(num_tasks)]) <= 1)

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

    # Objective
    objective_terms = []
    for i in range(num_workers):
        for j in range(num_tasks):
            objective_terms.append(costs[i][j] * X[i, j])
    solver.Minimize(solver.Sum(objective_terms))

    # Solve
    status = solver.Solve()

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

if __name__ == '__main__':
    main()
Python
복사

결과는 아래와 같습니다.

Total cost = 265.0

Worker 0 assigned to task 3. Cost: 70
Worker 1 assigned to task 2. Cost: 55
Worker 2 assigned to task 1. Cost: 95
Worker 3 assigned to task 0. Cost: 45
Python
복사

Keyword: Logistics Optimization, 물류 최적화, 파이썬, Python, 선형계획법, Linear Programming, Mixed Integer Programming, Google OR Tools

Reference

[1] Solving an Assignment Problem by Google, https://developers.google.com/optimization/assignment/assignment_example, Creative Commons Attribution 4.0 License