[기술 요약] 혼합 이진 이차 계획법(MBQP)을 위한 머신러닝 기반 프라이멀 휴리스틱

1. 문제 정의 (Problem Statement)

본 논문은 조합 최적화(Combinatorial Optimization) 분야의 난제 중 하나인 **혼합 이진 이차 계획법(Mixed Binary Quadratic Programs, MBQP)**을 해결하기 위한 연구를 다룹니다.

• MBQP의 특성: 목적 함수에 이차항(Quadratic terms)이 포함되어 있어 비선형성을 띠며, 이진 변수 제약 조건으로 인해 조합적 복잡성이 매우 높습니다. 이는 기존의 혼합 정수 선형 계획법(MILP)보다 훨씬 풀기 어려운 문제입니다.
• 기존 연구의 한계: 최근 머신러닝(ML)을 활용해 MILP의 해를 예측하고 가속화하는 연구는 활발히 진행되었으나, 비선형성이 포함된 MBQP에 특화된 ML 기반 방법론은 상대적으로 미비했습니다.
• 목표: 대규모 MBQP 문제에서 고품질의 실행 가능한 해(Feasible solution)를 빠르게 찾아내기 위한 **ML 가이드 프라이멀 휴리스틱(ML-guided primal heuristics)**을 개발하는 것입니다.

2. 제안 방법론 (Methodology)

연구진은 기존 MILP용 ML 방법론을 MBQP에 맞게 확장 및 개선한 프레임워크를 제안합니다.

A. 신경망 아키텍처 (Neural Network Architecture)

• 3부 그래프 표현 (Tripartite Graph Representation): MBQP의 구조를 반영하기 위해 제약 조건 노드(C), 변수 노드(V), 이차항 노드(Q)의 세 가지 유형으로 구성된 그래프 구조를 도입했습니다.
• 그래프 어텐션 네트워크 (GAT): 4단계의 메시지 패싱(Message Passing) 과정을 통해 변수, 제약 조건, 이차항 간의 복잡한 상호작용을 학습하여 각 이진 변수의 최적 할당 확률을 예측합니다.

B. 손실 함수 (Loss Function) - 핵심 기여

기존의 두 가지 접근법을 결합하여 성능을 극대화했습니다.

1. 가중 교차 엔트로피 (Weighted Cross-Entropy, WCE): 해의 품질(목적 함수 값)에 따라 가중치를 부여하여, 더 좋은 해를 가질 확률을 높이도록 학습합니다.
2. 대조 학습 (Contrastive Learning, CL): 좋은 해(Positive)와 나쁜 해(Negative)를 구분하도록 학습하여 변수 할당의 변별력을 높입니다.
3. 제안된 결합 손실 (Combined CL + WCE): 논문은 Proposition 1을 통해 CL 손실이 특정 변수 집합(좋은 해와 나쁜 해에서 값이 동일한 변수들)에 대해서는 예측 성능을 개선하지 못한다는 점을 수학적으로 증명했습니다. 이를 해결하기 위해, CL이 놓치는 변수들에 대해 WCE 기반의 분류(Classification)를 적용하는 결합 손실 함수를 제안했습니다.

C. 데이터 수집 (Data Collection)

• Randomized Relax-Search: 고품질의 학습 데이터를 얻기 위해 제안된 새로운 휴리스틱입니다. 비선형 계획법(NLP) 완화 해(Relaxation solution)를 기반으로 변수를 무작위로 고정(Fixing)하는 서브 문제를 생성하여, 다양하고 우수한 해(S+)와 품질이 낮은 해(S-)를 효과적으로 수집합니다.

D. 추론 (Inference)

• Neural Diving (ND): ML 모델이 예측한 확률이 높은(확신이 있는) 변수들을 고정하여 문제를 작은 크기의 서브 MBQP로 축소시킨 후, 기존 솔버(SCIP 등)로 빠르게 해결합니다.

3. 주요 기여 (Key Contributions)

1. MBQP 특화 모델: MILP 중심의 연구를 넘어 비선형 MBQP를 위한 최초의 ML 가이드 프라이멀 휴리스틱 프레임워크를 구축했습니다.
2. 새로운 그래프 구조 및 데이터 수집법: MBQP의 이차항 특성을 반영한 3부 그래프 구조와 Randomized Relax-Search 알고리즘을 제안했습니다.
3. 손실 함수 혁신: CL과 WCE의 한계를 수학적으로 분석하고, 이를 결합하여 예측 정확도와 일반화 성능을 높인 새로운 손실 함수를 설계했습니다.

4. 실험 결과 (Results)

• 벤치마크 성능: 합성 데이터(CBQP, QMKP, CQKP) 및 실제 데이터(WFLOP) 실험 결과, 제안된 CL+WCE 방법은 기존의 상태 최첨단(SOTA) 솔버(SCIP) 및 기존 휴리스틱(RENS, Undercover 등)보다 **Primal Gap(PG)**과 Primal Integral(PI) 측면에서 압도적인 성능을 보였습니다.
• 교차 지역 일반화 (Cross-regional Generalization): 풍력 발전소 배치 최적화(WFLOP) 문제에서, 특정 지역 데이터로 학습한 모델이 학습하지 않은 다른 지역(Hawaii, Great Lakes 등)의 데이터에서도 기존 방법론보다 훨씬 뛰어난 일반화 성능을 보임을 입증했습니다.
• 솔버 독립성: Gurobi와 같은 상용 솔버를 사용했을 때도 동일하게 우수한 성능을 유지하여 방법론의 견고함을 증명했습니다.

5. 의의 (Significance)

본 연구는 비선형 조합 최적화 문제에 머신러닝을 적용하는 새로운 지평을 열었습니다. 특히, 단순히 기존 모델을 적용하는 것에 그치지 않고, 문제의 수학적 구조(Proposition 1)를 분석하여 손실 함수를 개선함으로써 학습 효율성과 실제 산업 현장(풍력 발전 등)에서의 일반화 가능성을 동시에 확보했다는 점에서 학술적/실무적 가치가 매우 높습니다.