Column Generation 과 Dantzig-Wolfe Decomposition

Column Generation 을 한 문장으로 정의하면?

Column generation은 많은 수의 변수 (제약식의 수 보다 변수의 수가 훨씬 클때)를 다뤄야하는 LP/ILP 문제를 풀기 위한 알고리즘이다.

 

왜 "Column" Generation 이라 부르는가?

Column generation 은 변수의 개수가 많은 linear programming (LP) 를 다룰때 사용하기 적절한 방법이다. 대표적인 LP 문제를 써보면 아래와 같이 쓸 수 있다. Constraints 를 표현하는 행렬 A 가 m by n 형태라고 할때 우리는 n 은 변수의 개수를 의미하고 m 은 제약식의 개수를 의미한다 (무슨 의미인지 모르겠다면 LP 의 기초를 먼저 공부하자). 이때 A 의 입장에서 다시 서술해보면 n (변수) 은 column, m (제약식) 은 row 에 대응된다. 따라서 변수를 생성한다는 의미에서 column generation 이라 부르는 것이다. 

reference: http://www.science4all.org/article/column-generation/

기본 발상이 궁금해

 

이 알고리즘의 기본 발상은 Divide and conquer (나누어 정복하라!) 에 따른다. 대부분의 문제에서 모든 decision variables 들이 최종해에 포함되지 않는다. 따라서 아주 작은 개수의 column(variable)으로 이루어진 subproblem에서 시작해서 필요한 column들만을 더해나가면서 얻은 해가 원래 문제의 해와 일치했을때 알고리즘을 종결하자는게 기본 발상이다. 전체 변수 중 초기 변수들, 추가되는 변수들, 한번도 고려되지 않는 변수들을 아래와 같이 시각화 해볼 수도 있다. Master Problem 이 Original problem 의 전체 변수들보다 훨씬 적은 것을 알 수 있다.

reference: https://www.youtube.com/watch?v=h0sO2ZhLRwI&t=192s

 

그래서, Column generation 이 정확히 뭔데?

변수의 개수가 너무 많기 때문에 이를 일부만 고려하자는 것이 기본이다. (대부분의 LP 에서 basis 들은 전체 변수의 small subset 이라는 점에 근거한다.) 상위 문제와 하위 문제로 나누어 진행되는데 상위 문제 (Master problem) 에서는 전체 변수중 일부분만 고려한다. 아래 왼쪽의 그림을 보면 변수를 Generated Columns 와 Non-generated columns 로 나누어 Master problem 에서는 Generated columns 만 가지고 LP 문제를 푸는 것을 확인할 수 있다. 

reference: http://www.science4all.org/article/column-generation/

그 후 Subproblem 에서는 고려되지 않은 변수 중 promising 한 변수를 선정해 Master problem 의 subset 에 추가해준다. 이 과정은 sensitiviey analysis 를 통해 진행되는데 non-generated variable 변수 하나를 basis에 추가했을때의 reduced cost 를 계산해서 이것이 음수면 그 변수가 Master problem 의 최적값을 낮추는데 도움된다고 보고 추가한다. 

 

Column Generation 과 Dantzig-Wolfe Decomposition의 차이는 무엇인가?

Column Generation 은 linear programming 전반에 적용될 수 있는 아이디어이다. 특히 이전에 설명했듯 exponentially larger number of variables 이 있을때 변수의 개수를 줄이기 위해 사용되는 방법이다. Dantzig-Wolfe Decomposition 은 integer linear programming (ILP) 에 Column Generation 의 발상을 적용한 것이다. ILP 을 푸는데의 세가지 어려움을 생각해보면 1) 변수의 개수 2) 제약식의 개수 3) integrality gap 이다. integrality gap 이란 변수가 정수여야한다는 없을때 (LP relaxation 상황)에 비해 정수 제약이 있을때 목적 함수 값의 상대적 변화를 의미한다. 이 차이가 클수록 ILP 를 푸는데 더 오랜 시간이 소요된다. 이 integrality gap 이 큰 경우 이것을 변수의 개수가 많은 ILP 식으로 재정의해서 column generation 기법을 활용해 풀 수 있는데 이것을 Dantzig-Wolfe Decomposition 이라 한다. 

 

마지막으로, python 으로 Dantzig-Wolfe Decomposition 을 구현하는데 도움이 될만한 링크를 첨부한다. 

https://github.com/fzsun/cutstock-gurobi/blob/master/cutstock_grb.py

GitHub - fzsun/cutstock-gurobi: Cutting stock code for gurobi + python

 

References

This post is all based on the references below. 

http://www.science4all.org/article/column-generation/

Column Generation and Dantzig-Wolfe Decomposition

https://www.youtube.com/watch?v=h0sO2ZhLRwI&t=192s