Learning to Cut: Reinforcement Learning for Benders Decomposition

요약

본 논문은 불확실성 하의 2단계 확률적 프로그램을 해결하는 데 사용되는 Benders 분해(BD)의 느린 수렴 문제를 개선하기 위해 RLBD(Reinforcement Learning for BD) 프레임워크를 제안합니다. 이 프레임워크는 신경망 기반 정책을 사용하여 절단(cut)을 적응적으로 선택하며, REINFORCE 알고리즘과 같은 정책 경사 방법을 통해 훈련됩니다. 실험 결과, RLBD는 계산 효율성을 크게 향상시키고 다양한 차원의 문제에서도 강력한 일반화 성능을 입증했습니다.

핵심 포인트

• Benders 분해(BD)는 불확실성 하의 의사결정 문제를 해결하는 데 유용하지만, 절단 증가에 따라 수렴 속도가 느려지는 문제가 있습니다.
• RLBD 프레임워크는 신경망 기반 정책을 활용하여 필요한 절단을 적응적으로 선택함으로써 BD의 효율성을 개선합니다.
• 정책은 REINFORCE 알고리즘과 같은 정책 경사 방법을 사용하여 훈련됩니다.
• 실험 결과, RLBD는 기존 방식(LearnBD) 대비 계산 효율성 측면에서 상당한 개선을 보였으며 일반화 성능이 뛰어남을 입증했습니다.