할당 문제

할당 문제는 기본적인 조합 최적화 문제입니다.가장 일반적인 형태의 문제는 다음과 같습니다.

문제 인스턴스에는 여러 에이전트와 여러 태스크가 있습니다.임의의 에이전트를 임의의 태스크 수행에 할당할 수 있으며 에이전트 태스크 할당에 따라 비용이 달라질 수 있습니다.할당의 총 비용을 최소화할 수 있도록 각 태스크에 최대 1개의 에이전트를 할당하고 각 에이전트에 최대 1개의 태스크를 할당하여 가능한 한 많은 태스크를 수행해야 합니다.

또는 그래프 이론을 사용하여 문제를 설명합니다.

할당 문제는 가중 초당 그래프에서 가장자리의 가중치 합계가 최소인 주어진 크기의 일치 항목을 찾는 것으로 구성된다.

에이전트와 태스크의 수가 같을 경우 이 문제를 균형 할당이라고 합니다.그렇지 않으면 불균형 ^[1]할당이라고 합니다.모든 작업에 대한 할당의 총 비용이 각 에이전트의 비용 합계(또는 이 경우 각 작업에 대한 비용 합계)와 같을 경우 이 문제를 선형 할당이라고 합니다.일반적으로, 추가 자격증 없이 과제 문제를 말할 때 선형 균형 과제 문제를 의미합니다.

예

한 택시 회사에 이용 가능한 택시(대리점)가 3대 있고, 가능한 한 빨리 픽업되기를 원하는 고객(업무)이 3명 있다고 가정합니다.이 회사는 신속한 픽업을 자랑하기 때문에 각 택시에 대해 특정 고객을 픽업하는 "비용"은 택시가 픽업 지점에 도달하는 데 걸리는 시간에 따라 달라집니다.이것은 균형 잡힌 할당 문제입니다.그 해결책은 택시와 고객을 조합하여 총비용을 최소화하는 것입니다.

자, 택시는 4대 있지만 손님은 3대뿐이라고 가정해 봅시다.이것은 불균형한 할당 문제입니다.이 문제를 해결하는 한 가지 방법은 택시에 할당된 비용이 0인 네 번째 더미 태스크를 발명하는 것이다.이를 통해 문제를 균형 잡힌 과제 문제로 줄일 수 있으며, 이 문제는 일반적인 방법으로 해결되어도 여전히 문제에 대한 최선의 해결책을 제공할 수 있습니다.

에이전트보다 더 많은 태스크, 여러 에이전트를 할당해야 하는 태스크(예를 들어 한 대의 택시에 들어가는 것보다 더 많은 고객 그룹)를 허용하거나 비용을 최소화하는 대신 수익을 극대화하기 위해 유사한 조정을 수행할 수 있습니다.

형식적 정의

할당 문제(또는 선형 할당 문제)의 정식 정의는 다음과 같습니다.

A와 T의 크기가 동일한 두 집합이 주어진 경우, 무게 함수 C: A × T → R. 비용 함수가 다음과 같이 되도록 bijectionf : A → T를 구한다.

(\displaystyle \sum _{a\in A}C(a,f(a)})})

최소화됩니다.

일반적으로 가중치 함수는 제곱 실수치 행렬 C로 간주되므로 비용 함수는 다음과 같이 기록된다.

(\displaystyle \sum _{a\in A}C_{a,f(a)})

최적화해야 할 비용 함수와 모든 제약 조건이 선형 항만 포함되기 때문에 문제는 "선형"입니다.

알고리즘

과제 문제에 대한 간단한 해결책은 모든 과제를 확인하고 각각의 비용을 계산하는 것입니다.에이전트가 n개이고 작업이 n개일 경우 서로 다른 할당이 n!(n의 요인) 있기 때문에 매우 비효율적일 수 있습니다.다행히 n의 시간 다항식 문제를 푸는 알고리즘이 많이 있다.

할당 문제는 운송 문제의 특수한 경우이며, 이는 최소 비용 흐름 문제의 특수한 경우이며, 다시 선형 프로그램의 특수한 경우입니다.심플렉스 알고리즘을 사용하여 이러한 문제를 해결할 수 있지만 각 전문화에는 솔루션 공간이 더 작기 때문에 특수 구조를 활용할 수 있도록 설계된 보다 효율적인 알고리즘이 있습니다.

균형 잡힌 할당

균형 할당 문제에서, 양분 그래프의 두 부분은 n으로 표시된 동일한 수의 정점을 가집니다.

균형 배정을 위한 최초의 다항 시간 알고리즘 중 하나는 헝가리 알고리즘이었다.이것은 글로벌 알고리즘입니다.증강 경로(불일치한 정점 간에 번갈아 경로)를 따라 매칭이 개선되는 것을 기반으로 합니다.Fibonacci 힙을 사용하는 경우의 런타임 $O(mn+n^{2}\log n)$ 는 O $O(mn+n^{2}\log n)$ n + $O(mn+n^{2}\log n)$ $O(mn+n^{2}\log n)$ log $O(mn+n^{2}\log n)$ n $)\displaystyle$ O $(mn+n^{2$ $}\log$ n $O(mn+n^{2}\log n)$ ^[2] 여기서 m은 에지의 수입니다.이것은 현재 이 문제에 대한 강력한 다항식 알고리즘 중 가장 빠른 런타임입니다.모든 가중치가 정수일 경우 실행시간은 O $O(mn+n^{2}\log \log n)$ n + $O(mn+n^{2}\log \log n)$ $O(mn+n^{2}\log \log n)$ log $O(mn+n^{2}\log \log n)$ log $O(mn+n^{2}\log \log n)$ n $)\$ $displaystyle$ O $(mn+n^{2$ )로 향상할 수 있습니다. $}\log$ \ $log$ n $O(mn+n^{2}\log \log n)$ 단, 그 결과 알고리즘은 ^[3]약차만 발생합니다.가중치가 정수이고 모든 가중치가 최대 C(여기서 C> 1은 일부 정수)인 경우 문제는 Weight ^[4]^[5]^[6]Scaling이라는 방법으로 O $O(m{\sqrt {n}}\log(n\cdot C))$ n $O(m{\sqrt {n}}\log(n\cdot C))$ $O(m{\sqrt {n}}\log(n\cdot C))$ ( $O(m{\sqrt {n}}\log(n\cdot C))$ C $)\display$ O $(m {\sqrt {n}}\log$ n\ $cdot$ C)로 $O(m{\sqrt {n}}\log(n\cdot C))$ 해결할 수 있습니다.

글로벌 메서드 외에 로컬업데이트 검색에 기반한 로컬 메서드도 있습니다(완전 증강 경로가 아닌).이러한 메서드는 점근적 런타임 보증이 더 나쁘지만 실제로는 더 잘 작동합니다.이러한 알고리즘을 옥션알고리즘, 푸시릴라벨 알고리즘 또는 프리플로우 푸시 알고리즘이라고 부릅니다.이들 알고리즘 중 일부는 ^[7]동일한 것으로 나타났다.

일부 로컬 메서드는 그래프에서 완벽한 일치를 허용한다고 가정합니다.그렇지 않으면 이러한 메서드 중 일부는 ^[1]^{: 3}영원히 실행될 수 있습니다.이 문제를 해결하는 간단한 기술적 방법은 매우 큰 가중치를 가진 인공 에지를 추가하여 입력 그래프를 완전한 초당 그래프로 확장하는 것이다.이러한 중량은 가능한 솔루션에서 인위적인 가장자리가 나타나지 않도록 기존의 모든 일치의 중량을 초과해야 한다.

Mulmuley, Vazirani ^[8]및 Vazirani에서 알 수 있듯이 최소 무게 완전 일치 문제는 그래프의 인접 행렬에서 마이너 매칭을 찾는 것으로 변환됩니다.분리 보조항목을 사용하여 그래프에서 최소 체중 완전 일치를 최소 확률로 찾을 수 있습니다.1⁄2. 정점이 n개인 그래프에서는 O $O(\log ^{2}(n))$ 2 $O(\log ^{2}(n))$ ( $O(\log ^{2}(n))$ $){displaystyle$ O $(\log$ ^{ $2}(n)})$ 시간이 $O(\log ^{2}(n))$ $O(\log ^{2}(n))$ 합니다.

불균형 할당

불균형 할당 문제에서, 이분 그래프의 큰 부분은 n개의 정점을 가지며 작은 부분은 r<n개의 정점을 가진다.또한 그래프에서 최대 일치의 카디널리티를 나타내는 상수도 있습니다.목표는 정확히 s 사이즈의 최소 비용 일치를 찾는 것입니다.가장 일반적인 경우는 그래프가 단측-완벽 일치(즉, 크기 r의 일치)를 허용하는 경우이며, s=r이다.

불균형 할당은 균형 할당으로 축소할 수 있습니다.The naive reduction is to add $n-r$ new vertices to the smaller part and connect them to the larger part using edges of cost 0.단, 이를 $n(n-r)$ 는 n $n(n-r)$ - $n(n-r)$ r ){ $displaystyle$ n $(n-r)}$ 개의 $n(n-r)$ 새로운 에지가 $n(n-r)$ 합니다.보다 효율적인 절감을 더블링 기법이라고 합니다.여기서, 원래의 그래프 G의 2개의 카피, 즉 정방향 카피 Gf와 역방향 카피 Gb로부터 새로운 그래프 G'를 구축한다.역방향 복사가 "플립"되므로 G'의 양쪽에 n+r 정점이 있습니다.복사 사이에 두 가지 종류의 링크 ^[1]^{: 4–6}엣지를 추가해야 합니다.

Large-to-Large: Gf의 큰 부분의 각 정점에서 대응하는 정점에 Gb 단위로 제로 비용 에지를 추가합니다.
소-소: 원래 그래프에 단측-완벽 일치가 없는 경우 Gf의 작은 부분에 있는 각 정점에서 Gb 단위의 대응하는 정점에 매우 높은 비용 에지를 추가합니다.

전체적으로 최대 $n+r$ + $n+r$ \ $display style$ n $+r$ 엣지가 $n+r$ 새로 필요합니다.결과 그래프는 항상 $n+r$ n + $n+r$ {\ $displaystyle n+r$ 과(와) 완전히 일치합니다.이 그래프에서 최소 비용 완전 일치는 최소 비용 최대 카디널리티 일치(Gf 및 Gb)로 구성되어야 합니다.The main problem with this doubling technique is that there is no speed gain when $r\ll n$ .

불균형 할당 문제는 축소를 사용하는 대신 기존 알고리즘을 직접 일반화하여 해결할 수 있습니다.헝가리 알고리즘은 O $O(ms+s^{2}\log r)$ s + $O(ms+s^{2}\log r)$ $O(ms+s^{2}\log r)$ log $O(ms+s^{2}\log r)$ r $O(ms+s^{2}\log r)$ )(\ $style O(ms+s^{2$ }\ $log$ r $)}$ 강다항 $O(ms+s^{2}\log r)$ 시간에 $O(ms+s^{2}\log r)$ 를 해결하도록 일반화할 수 있습니다.특히 s=r인 경우 실행시간은 O $O(mr+r^{2}\log r)$ r + $O(mr+r^{2}\log r)$ 2 $O(mr+r^{2}\log r)$ $O(mr+r^{2}\log r)$ $){$ $displaystyle$ O $(mr+$ $r^{$ $2}\$ $log$ $O(mr+r^{2}\log r)$ r $O(mr+r^{2}\log r)$ 입니다.무게가 정수인 경우 Torup 메서드를 $O(ms+s^{2}\log \log r)$ 하여 O $(m$ + s $O(ms+s^{2}\log \log r)$ log $O(ms+s^{2}\log \log r)$ $⁡$ r $O(ms+s^{2}\log \log r)$ 의 실행시간을 $얻을$ 수 있습니다 $.$

선형 프로그래밍에 의한 솔루션

과제 문제는 선형 프로그램으로 제시하면 해결할 수 있습니다.편의상 최대화 문제를 제시하겠습니다.각엣지(i $, j,$ j)는 ${\textstyle w_{ij}}$ 에 있고 $j$ 는 T에 있으며 ${\textstyle w_{ij}}$ 는 $ij$ textstyle w_{ij $(i,j)$ 입니다.각 $(i,j)$ 엣지( $)$ 에 $(i,j)$ ${\textstyle x_{ij}}$ 변수 $(\displaystyle($ $i,j))$ 가 ${\textstyle x_{ij}}$ _. 있습니다.따라서 엣지가 일치하는 경우 변수는 1이고 그렇지 않으면 0입니다.

0\leq x_{ij}\leq 1{\text{}i,j\in A,T,}

x_{ij}\in \mathbb {Z}{text{}i,j\in A,T}

매칭의 총중량은 $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ : ( i $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ , $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ ) $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ A × $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ $\sum _{(i,j)\in A\times T}w_{ij}x_{ij}$ j \ $display$ style \ $sum$ _ { ( i , $j$ ) \ $in$ A \ $times$ T $}w$ _ { $ij }x$ _ { $ij$ 입니다.목표는 최대 무게의 완벽한 짝을 찾는 것입니다.

변수가 실제로 완벽한 일치를 나타내도록 하기 위해, 우리는 각 정점이 일치의 정확히 하나의 에지에 인접해 있다는 제약 조건을 추가한다.

\sum _{j\in T}x_{ij}=1{\text{\in A}x_{ij}=1{\text{}j\in T,,}}}j\text{\text}

.

전체적으로 다음 LP가 있습니다.

{maximize}~~\sum _{(i,j)\times T}w_{ij}x_{ij

{text{to}~\sum _{j\in T}x_{ij}=1{\text{for }i}in A,~\sum _{ij}=1{\text{for }j\in T}

0\leq x_{ij}\leq 1{\text{}i,j\in A,T,}

x_{ij}\in \mathbb {Z}{text{}i,j\in A,T}

이것은 정수 선형 프로그램입니다.그러나 연속 선형 프로그램을 해결하기 위한 표준 방법을 사용하여 통합 제약(마지막 제약 조건 삭제) 없이 해결할 수 있습니다.이 공식은 분수 변수 값도 허용하지만, 이 특별한 경우 LP에는 항상 변수가 정수 값을 갖는 최적의 솔루션이 있습니다.이는 분수 LP의 구속 행렬이 완전히 단일이기 때문에 호프만과 게일의 네 가지 조건을 충족합니다.

기타 방법 및 근사 알고리즘

할당 문제에 대한 다른 접근법이 존재하며 Duan과 Pettie에^[9] 의해 검토된다(표 II 참조).이들의 연구는 모든 고정 오차 경계에 대해 선형 시간으로 실행되는 할당 문제(및 보다 일반적인 최대 가중치 일치 문제)에 대한 근사 알고리즘을 제안한다.

일반화

그래프 이론 문제로 표현될 때, 할당 문제는 초당 그래프에서 임의 그래프로 확장될 수 있습니다.가중치 합계가 최대화된 가중 그래프에서 일치 항목을 찾는 해당 문제를 최대 가중치 일치 문제라고 한다.

할당 문제의 또 다른 일반화는 일치시키는 세트의 수를 2개에서 다수로 확장하는 것입니다.따라서 에이전트를 태스크에 일치시키는 것이 아니라 에이전트를 태스크에 일치시키고 시간 간격을 로케이션에 일치시키는 것으로 문제가 확대됩니다.그 결과 Multidimension Assignment Problem(MAP; 다차원 할당 문제)이 발생합니다.

「」를 참조해 주세요.

참고 자료 및 추가 자료

^ ^a ^b ^c ^d Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs" (PDF). HP research labs.
^ Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms". J. ACM. 34 (3): 596–615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.
^ Thorup, Mikkel (2004-11-01). "Integer priority queues with decrease key in constant time and the single source shortest paths problem". Journal of Computer and System Sciences. Special Issue on STOC 2003. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003. ISSN 0022-0000.
^ Gabow, H.; Tarjan, R. (1989-10-01). "Faster Scaling Algorithms for Network Problems". SIAM Journal on Computing. 18 (5): 1013–1036. doi:10.1137/0218069. ISSN 0097-5397.
^ Goldberg, A.; Kennedy, R. (1997-11-01). "Global Price Updates Help". SIAM Journal on Discrete Mathematics. 10 (4): 551–572. doi:10.1137/S0895480194281185. ISSN 0895-4801.
^ Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). "New scaling algorithms for the assignment and minimum mean cycle problems". Mathematical Programming. 54 (1–3): 41–56. doi:10.1007/BF01586040. ISSN 0025-5610. S2CID 18213947.
^ Vargas, Marcos C.; Valencia, Carlos E.; Perez, Sergio L.; Alfaro, Carlos A. (2018-10-08). "The equivalence between two classic algorithms for the assignment problem". arXiv:1810.03562v1 [math.OC].
^ Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). "Matching is as easy as matrix inversion". Combinatorica. 7 (1): 105–113. doi:10.1007/BF02579206. S2CID 47370049.
^ Duan, Ran; Pettie, Seth (2014-01-01). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.

Brualdi, Richard A. (2006). Combinatorial matrix classes. Encyclopedia of Mathematics and Its Applications. Vol. 108. Cambridge: Cambridge University Press. ISBN 978-0-521-86565-4. Zbl 1106.05001.
Burkard, Rainer; M. Dell'Amico; S. Martello (2012). Assignment Problems (Revised reprint). SIAM. ISBN 978-1-61197-222-1.
Bertsekas, Dimitri (1998). Network Optimization: Continuous and Discrete Models. Athena Scientific. ISBN 978-1-886529-02-1.

[:0-1] Lyle Ramshaw, Robert E. Tarjan (2012). "On minimum-cost assignments in unbalanced bipartite graphs" (PDF). HP research labs.

[2] Fredman, Michael L.; Tarjan, Robert Endre (1987-07-01). "Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms". J. ACM. 34 (3): 596–615. doi:10.1145/28869.28874. ISSN 0004-5411. S2CID 7904683.

[3] Thorup, Mikkel (2004-11-01). "Integer priority queues with decrease key in constant time and the single source shortest paths problem". Journal of Computer and System Sciences. Special Issue on STOC 2003. 69 (3): 330–353. doi:10.1016/j.jcss.2004.04.003. ISSN 0022-0000.

[4] Gabow, H.; Tarjan, R. (1989-10-01). "Faster Scaling Algorithms for Network Problems". SIAM Journal on Computing. 18 (5): 1013–1036. doi:10.1137/0218069. ISSN 0097-5397.

[5] Goldberg, A.; Kennedy, R. (1997-11-01). "Global Price Updates Help". SIAM Journal on Discrete Mathematics. 10 (4): 551–572. doi:10.1137/S0895480194281185. ISSN 0895-4801.

[6] Orlin, James B.; Ahuja, Ravindra K. (1992-02-01). "New scaling algorithms for the assignment and minimum mean cycle problems". Mathematical Programming. 54 (1–3): 41–56. doi:10.1007/BF01586040. ISSN 0025-5610. S2CID 18213947.

[7] Vargas, Marcos C.; Valencia, Carlos E.; Perez, Sergio L.; Alfaro, Carlos A. (2018-10-08). "The equivalence between two classic algorithms for the assignment problem". arXiv:1810.03562v1 [math.OC].

[8] Mulmuley, Ketan; Vazirani, Umesh; Vazirani, Vijay (1987). "Matching is as easy as matrix inversion". Combinatorica. 7 (1): 105–113. doi:10.1007/BF02579206. S2CID 47370049.

[9] Duan, Ran; Pettie, Seth (2014-01-01). "Linear-Time Approximation for Maximum Weight Matching" (PDF). Journal of the ACM. 61: 1–23. doi:10.1145/2529989. S2CID 207208641.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

할당 문제

네임스페이스

더

목차

예

형식적 정의