[OR-Tools 스터디] Assignment

가장 잘 알려져있는 combinatorial optimization 문제 중 하나는 assignment problem이다.

예제 : 노동자 그룹들이 일련의 일들을 수행할 필요가 있다고 가정하고, 각 노동자들과 일에 있어서 노동자에게 일을 부여하는 것에 비용이 든다. 문제는 총 비용을 최소화하면서 두 명의 작업자가 동일한 일을 수행하지 않고, 각 노동자 별로 최소 하나의 일이 부여되어야한다는 것이다. 

 

이 문제를 아래의 그래프와 같이 표현할 수 있는데, 여기서는 4명의 노동자와 4개의 일이 있다. 각 가장자리에는 노동자 별로 일을 할당하는 모든 가능한 경우의 수를 보여준다. 가장자리의 레이블들은 노동자별로 할당된 일들의 비용이다. 

가장자리 부분에 해당하는 assignment는 각각의 노동자들이며, 이들은 적어도 하나의 가장자리를 가지고 있으며, 두 노동자가 같은 일에 해당하는 가장자리가 존재하지 않는다. 한가지 가능한 assignment는 아래와 같다. 

assignment의 전체 비용은 70 + 55 + 95 + 45 = 265이다.

 

다음 섹션에서는 MIP solver와 CP-SAT solver를 사용하여 assignment problem을 어떻게 푸는지에 대해 다룰 것이다.

 

Other tools for solving assignment problems

OR-Tools은 또한 assignment 문제를 풀기위한 몇가지 도구들을 제공해준다. 이들은 MIP나 CP solver보다 빠를 수 있다.

• Linear sum assignment solver
• Minimum cost flow solver

그러나 이 도구들은 단순한 종류의 assignment problem만 해결할 수 있다. 따라서 광범위하게 다양한 문제들을 다루는 일반적인 solver에 있어서는 MIP와 CP-SAT solver를 추천한다. 

 

Reference :

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

과제  |  OR-Tools  |  Google Developers