[논문] 프록시 벤더스 분해
개요
Benders 분해는 복잡한 변수를 고정했을 때 크게 단순해지는 하위 문제들을 갖는 대규모 혼합정수 최적화 문제를 해결하기 위한 기본적인 프레임워크이다. 그러나 고전적인 Benders 분해는 매우 유사한 하위 문제들을 반복해서 풀며, 반복마다 진동(zigzagging) 현상이 발생해 대규모 환경에서 수렴이 느려지는 경우가 많다. Benders 하위 문제들의 반복 구조와 파라메트릭 특성에 착안하여, 본 논문에서는 하위 문제 최적화를 반복적인 정확한 해결 대신 인증된 최적화 프록시로 대체하는 새로운 분해 프레임워크인 **프록시 Benders 분해(Proxy‑BD)**를 제안한다. 제안된 프록시는 자체 지도(self‑supervised) 방식의 predict‑project‑and‑complete 메커니즘을 통해 이중(dual) 실현 가능한 해를 생성하고, 이를 이용해 이론적으로 타당한 Benders 컷을 만든다. 이 프레임워크는 예측 품질과 무관하게 투영‑완성(certification) 레이어를 통해 분해의 이론적 타당성을 유지한다. 프록시가 만든 컷에 대한 공식적인 특성을 규정하고, 브랜치‑앤‑Benders‑컷(branch‑and‑Benders‑cut) 알고리즘 등 현대적인 분해 기법에도 자연스럽게 확장한다. 대규모 시설 위치(Facility Location) 및 네트워크 설계(Network Design) 문제에 대한 실험 결과, Proxy‑BD는 하위 문제의 계산 부담을 크게 줄이면서도 거의 최적에 근접한 해 품질을 유지한다. 2000 × 2000 규모의 대규모 무용량 시설 위치 인스턴스에서, Proxy‑BD는 중간 최적성 차이(optimality gap)를 0.5 % 이하로 낮추고, 최대 161배의 중간 속도 향상(median speedup)을 달성했으며, 가장 큰 인스턴스에서는 생성된 컷 수를 240배 이상 감소시켰다. 계산 효율성은 재조정(Recourse) 복잡도가 증가할수록 일관되게 향상되었으며, 이는 프록시 기반 추론이 대규모 분해 환경에서 반복적인 정확한 하위 문제 최적화보다 훨씬 더 유리하게 확장됨을 시사한다.
주요 기여
본 논문은 다음 분야의 연구를 제시한다.
- math.OC
- cs.LG
방법론
자세한 방법론은 전체 논문을 참고하시기 바란다.
실용적 함의
본 연구는 math.OC 분야의 발전에 기여한다.
저자
- Changkun Guan
- El Mehdi Er Raqabi
- Mathieu Tanneau
- Pascal Van Hentenryck
논문 정보
- arXiv ID: 2606.07403v1
- 분류: math.OC, cs.LG
- 발표일: 2026년 6월 5일
- PDF: PDF 다운로드