단치그-울프 분해 (Dantzig-Wolfe Decomposition)
한 줄 정의: 블록 구조를 가진 대형 선형계획을 부분문제 해들의 볼록결합으로 재구성해 열생성으로 푸는 분해기법입니다.
쉽게 풀면
여러 공장이 각자 제약을 갖고 있고, 공장들을 묶는 공동 제약(예: 공동 예산)이 조금 있는 큰 문제를 생각해 봅시다. 단치그-울프 분해는 각 공장의 문제는 따로 풀게 하고, 본부(주문제)는 공장들이 제안한 계획안을 섞어 공동 제약을 맞춥니다. 본부가 가격 신호를 보내면 공장들은 더 좋은 계획안을 새로 제안하는 식으로 반복합니다.
왜 중요한가
대규모 수송·생산·승무원 스케줄링 문제에서 핵심 해법이며, 정수계획에서는 분지가격법의 뼈대가 됩니다. 분해 기법 논문에서 벤더스 분해, 라그랑지 완화와 함께 대표 방법으로 비교됩니다.
논문에서는 이렇게 쓰입니다
"공장별 생산 제약을 부분문제로 분리하는 Dantzig-Wolfe 분해를 적용하여 LP 완화의 하한을 개선하였다."
공장별 구조를 이용해 주문제와 부분문제로 나누었고, 그 결과 더 강한 한계값을 얻었다는 뜻입니다.
조금 더 깊게 보면
1960년 단치그(George Dantzig)와 울프(Philip Wolfe)가 발표했습니다. 부분문제의 실행가능영역을 극점(과 극방향)의 결합으로 표현하므로 변수가 매우 많아지는데, 이를 모두 나열하지 않고 쌍대가격을 이용해 필요한 열만 추가하는 것이 열생성입니다. 정수계획에 적용하면 부분문제의 정수 구조 덕분에 LP 완화 한계가 원래 모형의 완화보다 강해질 수 있으며, 이 한계는 같은 제약을 완화한 라그랑지 쌍대 한계와 같습니다.
주의할 점
열생성법 항목은 변수를 필요할 때만 추가하는 일반적 계산 기법을, 이 항목은 그 기법이 적용되는 특정한 문제 재구성 방식을 다룬다는 점이 다릅니다. 벤더스 분해는 변수를 나누고 제약(행)을 추가하는 반면, 단치그-울프 분해는 제약 구조로 나누고 열을 추가한다는 점도 구분해야 합니다.