EnerGNN은 학습한 에너지를 MIP로 정확히 최소화해 제약을 지킨 해를 찾는다

무엇인가

이 논문은 이진 결정 변수로 표현되는 조합 최적화에서 학습한 에너지 함수를 명시적 하드 제약 아래에서 정확히 최소화하는 방법을 다룬다. 학습 기반 조합 최적화는 보통 해를 직접 예측하거나 예측으로 탐색 공간을 줄이고, 에너지 기반 모델은 근사 추론에 의존해 왔다. 저자들은 신경망이 학습한 목적함수와 실행가능성 제약을 분리하면 같은 에너지를 서로 다른 제약 집합 위에서 재사용할 수 있다고 본다. 이는 운영·물리·논리 제약이 강한 실제 의사결정에서 예측 모델의 출력이 제약을 위반하는 문제를 줄이려는 시도다.

어떻게 동작하나

EnerGNN의 구조는 세 부분이다. 변수와 제약 또는 상호작용을 잇는 이분 그래프에서 메시지 패싱 GNN 인코더가 변수·제약·전역 임베딩을 만들고, 이 인코더는 인스턴스당 한 번만 계산되어 최적화 중 고정된다. 최적화 호환 readout은 선택된 변수 임베딩의 합, 문제별 선형 특징, 전역 임베딩을 결합해 구성 의존 표현을 만들며, 이 구성 요소는 결정 변수에 대해 아핀하거나 보조변수로 정확히 선형화된다. 마지막 ReLU MLP 에너지 헤드는 이 표현을 스칼라 에너지로 바꾸며, 조각별 선형이므로 혼합정수선형 제약으로 정확히 인코딩될 수 있다. 추론은 Neural-MIP라고 부르는 혼합정수계획으로 수행된다. 훈련된 GNN 인코더는 상수로 두고, readout과 ReLU 헤드를 보조 변수와 선형 제약으로 펼친 뒤 명시적 제약 아래에서 학습된 에너지를 최소화한다. 사전 활성값 범위는 구간 경계 전파로 구해 Big-M에 사용하고, 활성 상태가 고정된 뉴런은 제거해 모델 크기를 줄인다. 이렇게 하면 해는 인코딩된 제약을 만족하고, 학습된 에너지에 대해서는 전역 최적이다.

무엇과 다른가

훈련은 솔버가 생성한 실행가능·실행불가능 후보 구성들로 이루어진다. 실행가능 후보에는 기준해 대비 상대적 primal gap을, 실행불가능 후보에는 정규화된 제약 위반량을 붙인다. 목표 분포는 실행가능 후보 중 gap이 작을수록 높은 확률을 주고 실행불가능 후보에는 0을 주며, 모델 분포는 exp(-E/T)로 정의해 두 분포의 KL 발산을 줄인다. 여기에 실행가능 후보의 에너지를 gap에 맞추는 Huber 보정 손실과, 실행불가능 후보의 에너지를 log(1+위반량)에 맞추는 보조 손실을 더한다. 이론적으로 readout이 정확히 표현되고 에너지 헤드가 ReLU망이면 에너지 전체가 MIP로 표현되며, readout에 결정 변수가 들어가면 1개 은닉층 ReLU만으로도 이진 변수 간 임의의 이차 상호작용을 표현할 수 있다고 주장한다. 같은 에너지를 제약만 바꿔 다시 풀 수 있어 제로샷 제약 주입이 가능하지만, 새 실행가능 집합이 원래 경계 계산 영역을 벗어나면 경계를 다시 계산해야 한다.

어떻게 쓰나

실험은 Quadratic Knapsack, Combinatorial Auctions, CAR T세포 치료 공급망인 CART 세 가지다. QKP는 150개 이진 선택 변수와 0.30 상호작용 밀도, CA는 175개 입찰 변수를 250개로 확장해 평가했고, CART는 16개 후보 시설, 2개 운송 모드, 130일 일정, 10~650명 수요를 가진 1단계 시설 입지 문제를 다룬다. 비교 대상은 원문제를 푸는 Full MIP, 예측으로 탐색을 제한하는 Predict+Search·Neural Diving·ConPaS, 선형 점수와 MIP를 결합한 Linear+MIP, 그리고 같은 readout에 선형 헤드를 쓴 EnerGNN(Linear) 절제다. 지표는 평균 primal gap, 실행시간, 실행가능성, 최적해 대비 1% 이내 비율이다.

전제와 한계

QKP에서 EnerGNN(MLP)은 평균 gap 0.31%, 1% 이내 99%, 실행가능성 100%를 기록했다. ConPaS 0.95%, Neural Diving 1.04%, Predict+Search 1.13%였고, 같은 readout의 선형 헤드 절제는 26.87%로 크게 나빠져 비선형 에너지 헤드의 효과를 보여줬다. CART에서는 평균 gap 0.05%, 전 테스트 인스턴스 1% 이내, 실행가능성 100%, 214.03초를 기록해 Neural Diving의 1.53%와 398.34초보다 약 1.9배, ConPaS의 0.02%와 3404.19초보다 약 15.9배, 단일 MIP보다 17.4배 빨랐다. 시설 구성이 정해지면 선택된 시설만으로 하위 운영 MIP를 구성해 변수와 제약을 약 77% 줄인다. CA는 원 MIP가 Gurobi로 0.14초에 풀려 속도 실험이 아니라 제약 많은 추론을 보는 벤치마크이며, 선형 EnerGNN 헤드가 평균 gap 0.20%, 1% 이내 95%, 실행가능성 100%로 비선형의 0.53%보다 좋았다. 에너지와 primal gap의 순위 상관은 QKP·CART·CA에서 ρ≥0.94였다.

크기 전이에서 CART는 16개 시설로 학습해 12개와 20개에 적용했을 때 평균 gap이 0.98%와 1.23%로, 학습 규모의 0.05%보다 나빠졌지만 실행가능성은 100%였다. CA는 입찰 변수를 175개에서 250개로 늘리면 선형 헤드 기준 평균 gap이 0.20%에서 0.98%로 증가했다. 제로샷 제약 주입에서 CART는 원 최적해에서 선택된 시설 1·2·3개를 비활성화한 1,092개 교란에서도 모두 실행가능했고 평균 gap은 0.21%에서 0.45%로 올랐으며, 1% 이내 비율은 최소 91.23%였다. CA는 선택 입찰의 약 20·40·60%를 제거하고 최고가 거부 입찰을 강제하는 실험에서 평균 gap 0.07~0.21%, 1% 이내 최소 93.36%를 보였다. 같은 조건에서 Neural Diving은 CART 시설 3개 비활성화 시 실행가능성이 49.12%까지 떨어졌고 ConPaS는 더 큰 gap을 보였다. 손실 절제에서는 보정 손실을 빼면 CART 평균 gap이 0.05%에서 0.78%로, CA가 0.53%에서 7.69%로 나빠졌고, 실행불가능 손실의 효과는 상대적으로 작았다.

개발자 관점에서 EnerGNN은 예측 모델이 해를 직접 내놓고 제약을 사후에 맞추는 대신, 반복적으로 풀리는 MIP의 목적함수를 학습해 솔버에 넘기는 패턴이다. 공급망·배치·자원 할당처럼 제약이 자주 바뀌고 실행가능성이 중요한 반복 배포 환경에서, 제약은 MIP에 두고 학습은 목적함수에만 쓰는 분리가 유용하다. 다만 추론이 학습된 에너지에 대한 전역 최적이라는 점은 원래 목적함수에 대한 최적 보장이 아니므로, 실제 gap과 제약 인코딩을 검증해야 한다. 후보 생성과 라벨링의 일회성 오프라인 비용, ReLU망을 펼친 MIP 크기, Big-M 경계의 유효성, 솔버의 혼합정수 성능도 함께 확인해야 한다.

저자들이 밝힌 한계는 명확하다. 결정 의존 에너지 헤드가 MIP로 표현 가능해야 하므로 표현력과 추론 가능성 사이의 트레이드오프가 생긴다. 실험에서는 얕고 작은 헤드로 충분했고, 폭이나 깊이를 늘리면 추론 시간이 크게 늘면서 해 품질은 체계적으로 좋아지지 않았다. 추가 표현력은 최적화 전에 한 번 계산되는 GNN 인코더에 두는 편이 낫다고 본다. 훈련은 솔버가 만든 후보 구성과 라벨에 의존하므로 반복 배포에는 맞지만 일회성 오프라인 비용이 든다. 또한 정확한 추론은 원래 목적함수가 아니라 학습된 에너지에 대한 것이며, 제약 주입은 인코딩된 제약에 대한 실행가능성을 보장할 뿐 분포나 실행가능 집합이 크게 바뀌면 해 품질이 떨어질 수 있다. 비선형 에너지 헤드가 항상 유리하지도 않아, 원래 목적이 선형인 CA에서는 선형 헤드가 더 좋았다.