실험 과정에서 Maximum Weight Bipartartite Matching 을 할 필요가 있었다.
이것은 OR에서 Linear Assignment Problem (LAP) 이라고 부른다.
이 과정에서 처음 알게 된 방식이 Kuhn의 Hungarian Method [Kuhn1955] 이다.
Hungarian Method는 처음으로 polynomial time에 LAP를 해결
이 알고리즘은 Munkress에 의해 개선되었고 Lawler의 구현에서는 O(n^3) 알고리즘으로 개선되었다.
(n은 node 개수, m은 edge 개수)
현재 실험에서 다루고 있는 문제 (n=10^3~10^4, m = n^2) 를
Hungarian Method로 실험해 보면 시간이 정말 오래 걸려서 끝나지 않는다. :)
현재 LAP의 optimal solution을 찾는 알고리즘 중에서 time complexity 측면에서는 O(n^0.5 m log (nC)) 알고리즘이 가장 빠른 알고리즘으로 알려져 있다. 여기에는 Gabow and Tarjan 의 Priman-Dual Scaling 알고리즘과 Goldberg and Kennedy의 Push-Relabeling 알고리즘이 있다.
먼저 Gabow and Tarjan 알고리즘을 사용해보려 했으나 Fibonacci Heap을 쓰는 등 복잡한 메모리 관리가 필요하고 이미 구현되 코드가 공개되어 있지 않아서 사용하지 않고 가장 빠르다고 주장하는 Goldberg와 Kennedy의 알고리즘을 적용하기로 하였다. 이 알고리즘은
코드가 공개되어 있었다.
이 코드는 DIMACS 포맷을 사용하고 있다.
DIMACS 포맷 중에서 assignment problem을 위한 코드를 사용해야 했는데
포맷의 스펙은 DIMACS Challenge
사이트에 나와 있다.
예제는
lpsolve 홈페이지에 나온 것이 낫다.
입력을 DIMACS 포맷으로 변환시킨 후
Windows에서 cygwin으로, 그리고 Linux에서 코드를 컴파일하여 사용해 보았다.
이 코드는 perfect matching을 가정하고 있기 때문에 결국 입력을 complete bipartite graph로 변환시켜서 넣을 수밖에 없었다. m=n^2이 되어 edge개수가 많아진다. edge 입력할 때 'a 1 2 100'과 같이 각 edge를 다 표시하게 하기 때문이다.
Windows(32bit)에서는 node가 2000개정도 넘어가면서부터 out of memory가 나온다.
Linux(64bit)에서는 좀 낫지만 node가 6000개 넘어가면서부터 out of memory가 나오는듯 하다.
어쨌든 n을 줄여가면서 돌리는데는 성공.
그리고, O(n^3)인 Jonker-Volgenant의 알고리즘을 사용해 보았다.
googling 중에 발견한 Nathan Brixius의 블로그
글에서 이게 제일 빠르다고 하였기 때문이다.
이 코드는
MagicLogic에서 받을 수 있다.
일단 compile은 Visual C++ 6.0에서 잘 된다.
LAP 예제를 만드는 main 프로그램에서 예전 라이브러리를 쓰기 때문에 Visual Studio 2005로 돌리기 위해 약간만 수정하였다.
입력은 dimension과 matrix만 넣어주면 잘 돌아간다.
Goldberg-Kennedy 코드는 maximize version인 반면 Jonker-Volgenant cost minimize 버전이기 때문에 cost matrix로 바꾸기 위해서 각 element를 max 값에서 빼주고 돌려야 한다.
결과는 정말 좋다. Goldberg-Kennedy 코드보다 메모리를 훨씬 적게 사용하면서 속도도 훨씬 빠른 것을 알 수 있었다.
이유가 무엇인지 생각해 보니 Goldberg-Kennedy 코드는 O(n^0.5 m log(nC))에서
m = n^2가 되고 C는 지금 Scale Factor를 1000으로 잡기 때문에 n가 거의 C가 되는 것이다.
그래서 다시 정리하면 time complexity가 O(n ^ 2.5 log n^2) = O(n ^ 2.5 log n)
time complexity 차이는 log n 정도 차이가 나지만
메모리 사용 효율 측면에서 차이가 큰 것 같다.
물론 Sparse Matrix에서는 Goldberg-Kennedy 방법이 좋을 것 같은 생각이 든다.