The simplex based column generation is a well-known method for solving large-sized mathematical programming problems. However, it has a major drawback that it often shows slow convergence. Recently, many acceleration schemes for column generation have been proposed in response to the aforementioned weakness. The stabilized column generation (Du Merle, et al., 1999) and Chebyshev center based column generation (Lee and Park, 2011) are representative accelerations. Both can result in faster convergence, on the other hand, they largely depend on the problems. In particular, the algorithms do not work well for problems where the master problem is relatively hard to solve. This research proposes a column generation technique based on distributed optimization and develops an efficient algorithm using the latest technologies including parallelism. Numerical comparisons are conducted for two applications: bin-packing problem and generalized assignment problem. Computational experiments show that our algorithm outperforms the existing accelerated column generation algorithms in large size problems.

단체법(Simplex Method)을 기반으로 하는 열 생성 기법(Column Generation Method)은 대규모의 수리 모형 문제들을 다루는 잘 알려진 방법이다. 하지만, 이는 최적해로의 수렴 속도가 느리다는 결정적인 단점이 있다. 최근에는 열 생성 기법의 수렴 속도를 높이기 위한 기법들이 많이 제안되고 있다. 대표적인 예로는 안정화 열 생성 (Du Merle, et al., 1999) 기법과 Chebyshev 중점을 기반으로 한 열 생성 (Lee and Park, 2011)가 있다. 기존의 고전적인 방법보다는 수렴속도 측면에서 개선될 수 있지만, 문제에 크게 의존적이다. 특히, 알고리즘들은 주문제(Master Problem)가 상대적으로 어려운 문제들에서 성능이 좋지 않다는 특성이 있다. 본 연구에서는 분산 최적화 기법을 활용한 열 생성 기법을 소개하며 병렬법을 포함한 최신 기술을 접목시킨 효과적인 알고리즘을 제시한다. 수치적 비교에서는 빈 할당 문제와 일반화 할당 문제에 적용한다. 실험 결과에서는 규모가 큰 문제에서 본 논문에서 제시한 알고리즘이 우수한 성능을 보인다.