열생성법 (Column Generation Method)
쉽게 풀면
가능한 조합의 수가 너무 많아서 처음부터 모든 경우를 나열하는 것 자체가 불가능한 문제가 있습니다. 예를 들어 배송 경로 후보나 근무 스케줄 조합이 수백만 가지에 이를 수 있습니다. 열생성법은 이런 상황에서 처음부터 모든 후보를 다 준비해두는 대신, 일단 일부 후보만으로 문제를 풀어본 뒤 "지금 상태에서 추가하면 개선 효과가 있는 후보가 있는가"를 확인해 그런 후보만 골라 하나씩 새로 추가해가는 방식입니다. 더 이상 도움이 되는 후보가 없을 때까지 이 과정을 반복하면, 모든 후보를 처음부터 다 고려하지 않고도 최적해를 찾을 수 있습니다.
왜 중요한가
승무원 배정, 차량경로문제, 절단 재고 최적화처럼 실행 가능한 조합의 수가 매우 커지는 문제는 산업공학에서 자주 등장합니다. 열생성법은 이런 대규모 문제를 처음부터 전부 나열하지 않고도 필요한 부분만 점진적으로 탐색해 풀 수 있게 해주기 때문에, 실무 규모의 최적화 문제를 다루는 연구에서 핵심적인 해법으로 활용됩니다.
논문에서는 이렇게 쓰입니다
처음부터 모든 근무 조합을 나열하지 않고, 유용한 조합만 순차적으로 찾아 추가하며 문제를 풀었다는 의미입니다.
자재를 낭비 없이 자르는 방법의 조합이 매우 많은 상황에서, 유효한 절단 패턴을 필요할 때마다 새로 찾아내며 최적의 조합을 구했다는 뜻입니다.
조금 더 깊게 보면
열생성법은 일부 변수만 포함한 제한된 문제를 먼저 풀고, 그 해의 쌍대 정보를 이용해 새로 추가할 가치가 있는 변수를 판별하는 하위 문제를 반복적으로 푸는 구조로 진행됩니다. 이 하위 문제는 흔히 동적계획법이나 최단경로문제와 같은 별도의 최적화 문제로 표현되며, 더 이상 개선 가능한 변수가 없을 때 알고리즘이 종료됩니다. 정수계획법 문제에서는 열생성법을 분지한정법과 결합한 분지-가격결정법의 형태로 활용하기도 합니다.
주의할 점
열생성법은 하위 문제를 효율적으로 풀 수 있는 구조를 가진 문제에서 특히 효과적이며, 하위 문제 자체가 복잡한 경우에는 전체 알고리즘의 성능이 기대만큼 나오지 않을 수 있습니다.