대규모 매개변수 혼합 정수 계획법(Parametric Mixed-Integer Programs)을 위한 백도어, 머신러닝 및 최적화의 결합

대규모 최적화 문제(Large-scale optimization problems)는 종종 유사한 구조적 조건 하에서 반복적으로 해결되며, 이는 상당한 계산 오버헤드(computational overhead)를 초래합니다. 이러한 현상은 전력 시스템, 운송 및 공급망 네트워크와 같은 응용 분야에서 발생하며, 여기서는 기저 구조는 고정되어 있는 반면 매개변수(parameters)는 섭동(perturbations)에 따라 빈번하게 변합니다. 본 논문은 계산 복잡성의 대부분을 유발하는 변수들의 부분 집합인 백도어(backdoor) 개념을 활용하여 대규모 일반 혼합 정수 문제(mixed-integer problems)의 해결을 가속화하는 최적화 학습(Learning to Optimize, LTO) 프레임워크를 제안합니다. 제안된 BIPC 프레임워크는 세 단계로 구성됩니다. 1단계는 분포 내의 일련의 인스턴스(instances)에 대한 백도어를 찾아내는 식별 절차입니다. 2단계는 지도 학습(supervised learning)을 사용하여, 인스턴스가 주어졌을 때 유계 영역(bounded-domain) 백도어 변수의 값과 광범위 영역(wide-domain) 백도어 변수의 구간을 예측하는 머신러닝(machine learning) 모델을 개발합니다. 이러한 예측은 예측값이 백도어 변수를 제약하는 반면 다른 변수들은 자유롭게 남겨두는 축소된 최적화 문제(reduced optimization problem)를 정의합니다. 3단계는 이 축소된 문제를 최적화하며, 필요한 경우 실행 가능성(feasibility) 또는 최적성 보장(optimality guarantees)을 복구하기 위해 수정 단계(correction step)를 적용합니다. 실제 세계의 대규모 문제에 대한 실험 결과, 해의 품질(solution quality) 손실은 제한적인 수준에서 유지하면서 해결 시간(solution time)을 대폭 단축함을 보여주었습니다. 이 프레임워크를 통해 조직은 예상치 못한 사건, 수요 변동 또는 운영 변경과 같은 빈번한 섭동이 존재하는 상황에서도 대규모 최적화 문제를 효율적으로 해결할 수 있습니다. 이러한 변화는 문제 구조보다는 매개변수에 영향을 미치기 때문에, BIPC는 고품질의 실행 가능한 해를 빠르게 제공할 수 있으며, 기존 최적화 파이프라인(optimization pipelines)에 머신러닝을 통합하는 실용적인 접근 방식을 제공합니다.