벤더스분해법 (Benders Decomposition)
쉽게 풀면
큰 전략을 먼저 정하고, 그 전략이 세부적으로 실행 가능한지를 나중에 확인하며 계획을 다듬어가는 상황을 떠올려 보면 됩니다. 예를 들어 어디에 창고를 지을지 먼저 결정하고, 그 창고 위치를 바탕으로 실제 운송 계획이 얼마나 효율적인지를 확인한 뒤, 문제가 있으면 창고 위치 결정을 다시 조정하는 식입니다. 벤더스분해법은 이렇게 문제를 크게 두 부분, 즉 큰 틀을 정하는 주문제와 그 틀 안에서 세부 운영을 최적화하는 하위문제로 나누어, 하위문제에서 얻은 정보를 다시 주문제에 반영하는 과정을 반복하며 전체 최적해를 찾아가는 방법입니다.
왜 중요한가
시설 입지와 운영 계획을 동시에 결정해야 하는 문제처럼, 서로 성격이 다른 결정 변수가 복잡하게 얽혀 있는 대규모 최적화 문제는 한 번에 통째로 풀기 어려운 경우가 많습니다. 벤더스분해법은 이런 문제를 구조적으로 나누어 각각 더 다루기 쉬운 형태로 만들어 풀 수 있게 해주기 때문에, 공급망 설계나 에너지 시스템 계획과 같은 산업공학 응용 연구에서 널리 활용됩니다.
논문에서는 이렇게 쓰입니다
입지 결정이라는 큰 틀과 운송 계획이라는 세부 사항을 나누어 풀되, 서로 정보를 주고받으며 최종 해를 찾았다는 의미입니다.
수요가 불확실한 여러 시나리오를 모두 고려해야 하는 복잡한 문제를 주문제와 하위문제로 나누어 효율적으로 풀었다는 뜻입니다.
조금 더 깊게 보면
벤더스분해법에서는 먼저 주문제를 근사적으로 풀어 잠정적인 결정을 내린 뒤, 이를 고정한 상태에서 하위문제를 풀어 그 해의 쌍대 정보를 이용한 절단부등식을 생성합니다. 이 절단부등식을 다시 주문제에 추가해 다음 반복에서 더 나은 결정을 내리도록 유도하며, 이 과정을 절단부등식이 더 이상 필요 없을 때까지 반복합니다. 확률적 요소가 포함된 문제에서는 각 시나리오별 하위문제를 병렬로 풀 수 있다는 점도 이 방법의 실용적인 장점으로 꼽힙니다.
주의할 점
주문제와 하위문제를 여러 차례 반복해야 하므로 문제 구조에 따라 수렴 속도가 느려질 수 있으며, 절단부등식을 효과적으로 생성하지 못하면 실용적인 시간 안에 최적해에 도달하지 못할 수도 있습니다.