Unit Commitment Neural Integer Solver with Unrolling Acceleration via Constraint-to-Constraint Strong Neural Branching
제약 간 상호작용을 고려한 발전기 기동정지계획 신경망 기반 정수계획 솔버
- 주제(키워드) mixed-integer programming , branch-and-bound , strong branching , constraint programming , graph neural networks , unit commitment , power systems
- 발행기관 서강대학교 일반대학원
- 지도교수 김홍석
- 발행년도 2026
- 학위수여년월 2026. 2
- 학위명 석사
- 학과 및 전공 일반대학원 전자공학과
- 실제URI http://www.dcollection.net/handler/sogang/000000082606
- UCI I804:11029-000000082606
- 본문언어 영어
- 저작권 논문은 저작권에 의해 보호받습니다.
초록(요약문)
Branching is a key decision-making component of the branch-and-bound (B&B) algorithm for solving large-scale mixed-integer programming (MIP) problems, and its quality has a direct impact on overall computational efficiency. Strong branching (SB) is known to provide the most accurate branching decisions; however, its requirement for repeatedly solving linear relaxations for each candidate variable results in excessively high computational costs, which limits its applicability to large-scale or real-time applications. In this paper, we propose UNISUA, a graph neural network (GNN)-based integer solver framework that introduces a novel strong neural branching (SNB) policy and a constraint- to-constraint (C2C) layer, thereby explicitly capturing interactions among constraints to overcome this limitation. Each MIP instance is represented as a variable–constraint bipartite graph, and the C2C layer is designed to learn both the structural and functional relationships between constraints. The proposed model employs a sequential variable-to-constraint, constraint-to-constraint, and constraint-to-variable message passing architecture. We leverage a composite loss that combines cross-entropy and margin-based ranking terms to effectively imitate the full strong branching rule. The framework is evaluated on the power system unit commitment (UC) problem, a representative large-scale MIP characterized by tightly coupled binary variables and network constraints. Experimental results on IEEE case118 data demonstrate that the proposed method achieves optimality with significantly reduced solution time compared with the bipartite GCNN and SCIP’s built-in SB policy. More interestingly, the model does not require retraining to be applicable to unseen IEEE case300 systems, or totally different problems such as knapsack benchmarks, which underscores its generalization characteristics.
more초록(요약문)
혼합 정수 계획(Mixed-Integer Programming, MIP) 문제를 해결하기 위한 Branch-and-Bound(B\&B) 알고리즘에서 분기(branching)는 핵심적인 의사결정 요소로 작용하며, 분기 품질은 전체 계산 효율에 직접적인 영향을 미친다. Strong Branching(SB) 규칙은 가장 정확한 분기 결정을 제공하는 기법으로 알려져 있으나, 각 후보 변수에 대해 반복적으로 선형 완화(Linear Relaxation) 문제를 해결해야 하므로 계산 비용이 매우 크다는 한계를 지닌다. 이로 인해 SB 규칙은 대규모 문제나 실시간 적용이 요구되는 환경에서는 활용이 제한된다. 본 논문에서는 이러한 한계를 극복하기 위해, 제약 조건 간 상호작용을 명시적으로 학습하는 Strong Neural Branching(SNB) 정책을 새롭게 제안하고, 이를 통합한 그래프 신경망(Graph Neural Network, GNN) 기반 정수 최적화 프레임워크 Unit Commitment Neural Integer Solver with Unrolling Acceleration(UNISUA)을 제시한다. 각 MIP 인스턴스는 변수-제약 이분 그래프로 표현되며, 제약 조건 간의 구조적 및 기능적 관계를 학습하기 위해 새로운 Constraint-to-Constraint(C2C) 계층을 도입한다. 제안된 모델은 변수-제약, 제약-제약, 제약-변수 순으로 구성된 메시지 패싱 구조를 통해 전역적인 문제 구조를 효과적으로 반영한다. 또한, 교차 엔트로피 손실과 마진 기반 순위 손실을 결합한 복합 손실 함수를 활용하여 SB 규칙의 분기 결정 특성을 효과적으로 모사하도록 설계되었다. 제안된 프레임워크는 이진 변수와 네트워크 제약이 강하게 결합된 대표적인 MIP 문제인 발전기 기동정지계획(Unit Commitment, UC) 수립 문제를 대상으로 평가되었다. IEEE case118 인스턴스를 이용한 실험 결과, 제안된 방법은 기존의 bipartite GCNN 및 SCIP 내장 SB 규칙과 비교하여, 현저히 단축된 계산 시간으로 최적해를 도출함을 확인하였다. 또한, 본 모델은 추가적인 재학습 없이도 더 큰 규모의 새로운 계통인 IEEE case300 인스턴스 뿐만 아니라 배낭 문제(knapsack problem)와 같은 구조적으로 상이한 문제에서도 효과적으로 적용 가능함을 보였으며, 이는 제안된 프레임워크의 우수한 일반화 성능을 시사한다.
more목차
I. Introduction 1
II. Background 5
2.1 Mixed-Integer Linear Programming 5
2.2 Branch-and-Bound Algorithm 6
2.3 Branching Rules 7
2.4 Unit Commitment 8
III. Proposed Framework 12
3.1 Graph Representation 12
3.1.1 Variable-Constraint Bipartite Graph 12
3.1.2 Constraint-to-Constraint Adjacency Graph 13
3.2 Proposed Neural Network Architecture (UNISUA) 16
3.3 Construction of Input Dataset 18
3.4 Loss Function 19
IV. Experiment 21
4.1 Setup and Baselines 21
4.2 Instance Difficulty Analysis Based on Root-Node LP Statistics 22
4.3 Model Performance 24
4.4 Performance on Unseen IEEE case300 System 27
4.5 Performance on Unseen Knapsack Problems 30
V. Discussion 33
VI. Conclusion 35
Appendix A Hyperparameter Sensitivity Analysis 36
A.1 Sensitivity Analysis of C2C Adjacency Weights (λ1,λ2) 36
A.2 Sensitivity Analysis of the Loss Weight (λ) 38
Appendix B Detailed Evaluation Pipeline of the UNISUA Framework 39
Appendix C Definition of Root Node Difficulty for UC Instances 41
C.1 Feature Vector 41
C.2 Preprocessing 42
C.3 Weighted Difficulty Score 42
C.4 Difficulty Grouping 43
Bibliography 44
