Proxy Benders Decomposition (Proxy-BD)

Benders decomposition (Benders 분해)는 복잡한 변수(complicating variables)를 포함하는 대규모 혼합 정수 최적화 문제(mixed-integer optimization problems)를 해결하기 위한 근본적인 프레임워크로, 해당 변수들을 고정했을 때 훨씬 쉬운 하위 문제(subproblems)를 생성할 수 있습니다. 그러나 전통적인 Benders decomposition은 매우 유사한 하위 문제를 반복적으로 해결하며, 반복 과정에서 종종 지그재그(zigzagging) 동작을 보여 대규모 설정에서 느린 수렴(convergence)을 초래합니다. Benders 하위 문제의 반복적인 구조와 매개변수적 특성(parametric nature)에 착안하여, 본 논문은 하위 문제 최적화를 반복적인 정확한 해결(exact solves) 대신 인증된 최적화 프록시(certified optimization proxies)로 대체하는 새로운 분해 프레임워크인 Proxy Benders decomposition (Proxy-BD)을 소개합니다. 제안된 프록시는 증명 가능한 유효한 Benders cuts를 생성하기 위한 쌍대 타당해(dual-feasible solutions)를 도출하는 자기 지도 학습 기반의 predict-project-and-complete 메커니즘을 따릅니다. 이 프레임워크는 투영 및 완성 인증 레이어(projection-and-completion certification layer)를 통해 예측 품질과 무관하게 분해의 이론적 타당성을 보존합니다. 프록시에 의해 유도된 cuts에 대한 공식적인 특성 정의가 확립되었으며, 이 프레임워크는 branch-and-Benders-cut 알고리즘을 포함한 현대적인 분해 방식(decomposition schemes)으로 자연스럽게 확장됩니다. 대규모 시설 입지(facility location) 및 네트워크 설계(network design) 문제에 대한 계산 실험 결과, Proxy-BD는 최적에 가까운 해의 품질을 유지하면서도 하위 문제의 계산 노력을 실질적으로 줄임을 입증했습니다. 최대 2000x2000 규모의 대규모 비용 제한 없는 시설 입지(uncapacitated facility location) 인스턴스에서 Proxy-BD는 중앙값 최적성 격차(median optimality gaps) 0.5% 미만을 달성하였고, 최대 161배의 중앙값 속도 향상(median speedups)을 기록했으며, 가장 큰 인스턴스에서는 생성된 cuts의 수를 240배 이상 줄였습니다. 계산 이득은 recourse 복잡성이 증가함에 따라 일관되게 증가하며, 이는 프록시 기반 추론이 대규모 분해 설정에서 반복적인 정확한 하위 문제 최적화보다 훨씬 더 유리하게 확장(scale)됨을 나타냅니다.