할당

가장 잘 알려진 조합 최적화 문제 중 하나는 할당 문제입니다. 예를 들어 작업자 그룹이 일련의 태스크를 수행해야 하고 각 작업자와 태스크에 작업자를 태스크에 할당하는 비용이 있다고 가정해 보겠습니다. 문제는 총 비용을 최소화하면서 두 명의 작업자가 동일한 태스크를 수행하지 않고 각 작업자를 최대 한 개의 태스크에 할당하는 것입니다.

이 문제는 작업자 4개와 태스크 4개가 있는 아래 그래프로 시각화할 수 있습니다. 에지는 작업에 작업자를 할당할 수 있는 모든 방법을 나타냅니다. 에지의 라벨은 작업자를 태스크에 할당하는 비용입니다.

할당은 에지의 하위 집합에 해당하며, 각 작업자에는 최대 한 개의 가장자리가 바깥쪽으로 선행되어 있고, 동일한 태스크로 이어지는 가장자리가 두 작업자가 없는 에지의 하위 집합에 해당합니다. 가능한 할당 하나가 아래에 표시됩니다.

할당 총비용은 70 + 55 + 95 + 45 = 265입니다.

다음 섹션에서는 MIP 솔버와 CP-SAT 솔버를 모두 사용하여 할당 문제를 푸는 방법을 보여줍니다.

과제 문제 해결을 위한 기타 도구

OR-Tools는 할당 문제를 해결하기 위한 몇 가지 다른 도구도 제공하며 이는 MIP 또는 CP 솔버보다 빠를 수 있습니다.

• 선형 합계 대입 문제 해결사
• 최소 비용 흐름 문제 해결사

그러나 이러한 도구는 간단한 유형의 할당 문제만 해결할 수 있습니다. 따라서 다양한 문제를 처리할 수 있고 대부분의 애플리케이션에서 충분히 빠른 일반 문제 해결자의 경우 MIP 및 CP-SAT 솔버를 사용하는 것이 좋습니다.