arXiv:2602.13155v3 cs.LG

그래프 신경망을 통한 균일 시설 입지 문제 근사 학습

Learning to Approximate Uniform Facility Location via Graph Neural Networks

Chendi Qian, Christopher Morris, Stefanie Jegelka, Christian Sohler

제출 2026-09-24

한국어 초록

신경망, 특히 메시지 전달 신경망(MPNN)은 어려운 조합 최적화(combinatorial optimization) 문제를 해결하기 위한 휴리스틱으로 점차 널리 활용되고 있습니다. 그러나 많은 학습(training) 기반 방법론들은 지도 학습, 강화학습(reinforcement learning), 또는 그래디언트(gradient) 추정기에 의존하여 높은 계산 비용, 불안정한 학습, 또는 제한적인 이론적 보장만을 제공하는 한계가 있습니다. 전통적인 근사 알고리즘은 최악 조건 보장을 제공하지만 미분 불가능하며 자연적인 입력 분포의 구조에 적응할 수 없습니다. 본 연구에서는 클러스터링, 요약, 물류, 공급망 등에 응용되는 문제인 균일 시설 입지(Uniform Facility Location, UniFL) 문제를 통해 이러한 상충 관계를 조사합니다. 솔버의 지도 신호나 이산 완화(discrete relaxation) 없이도 근사 알고리즘 원리를 통합하는 완전 미분 가능한 MPNN을 제안합니다. 제안된 모델(model)은 증명 가능한 근사 보장을 지니며, 경험적으로 표준 근사 알고리즘보다 향상된 성능을 보여 정수 선형 계획법(integer linear programming)과의 격차를 좁힙니다.

원문 초록

Neural networks, particularly message-passing neural networks (MPNNs), are increasingly used as heuristics for hard combinatorial optimization problems. Yet many learning-based methods rely on supervision, reinforcement learning, or gradient estimators, causing high computational cost, unstable training, or limited guarantees. Classical approximation algorithms provide worst-case guarantees but are non-differentiable and cannot adapt to structure in natural input distributions. We study this tradeoff through Uniform Facility Location (UniFL), a problem with applications in clustering, summarization, logistics, and supply chains. We propose a fully differentiable MPNN that incorporates approximation-algorithmic principles without solver supervision or discrete relaxations. The model has provable approximation guarantees and empirically improves on standard approximation algorithms, narrowing the gap to integer linear programming.

제출 이력

확인된 버전만 표시합니다. 전체 제출 이력은 arXiv 원문에서 확인하세요.

  1. arXiv:2602.13155v3제출 시각 미확인

함께 살펴볼 논문

공통 태그를 근거로 연결했습니다. 실제 인용 관계나 논문의 우수성을 뜻하지 않습니다.

arXiv:2607.09737v2physics.chem-ph공통 태그 Combinatorial Optimization, Graph Neural Network

Q-Score: 분자 도킹을 위한 양자 네이티브 스코어링 함수

Q-Score: A Quantum-Native Scoring Function for Molecular Docking

분자 도킹은 소분자가 단백질에 결합하는 방식을 예측하며, 신약 개발의 핵심 병목 단계이다. 고전적인 스코어링 함수는 경험적 쌍별 접촉을 합산하는 방식으로, 결합 특이성을 결정하는 궤도 전하 이동과 같은 양자역학적 효과를 반영하지 못한다. 본 연구에서는 Q-Score를 제안한다. Q-Score는 GNN으로 예측된 궤도 전자 공여-수용 에너지를 가중 그래프로 인코딩하고, Digitized-Counterdiabatic QAOA를 통해 최대 가중치 정점 클리크 문제를 풀어 결합을 스코어링한다. 각 상호작용 앵커는 하나의 큐비트에 대응되며, 호환성 제약 조건은 에지로 표현된다. 11개의 단백질 타겟에 대해 DC-QAOA는 10큐비트에서 8개의 타겟에서 정확한 최적해를 복원한다. AI 생성 분자 1,000개에 대해 Q-Score는 Spearman rho 0.05로 고전적 스코어링과 직교하며, rho 0.90으로 궤도 품질에 의해 주도되고, 분자량 바이어스가 없으며, 무작위 대비 두 배의 비율로 강한 궤도 상호작용을 농축시킨다. DC-QAOA는 52%의 정확률과 함께 평균 근사 비율 0.94를 달성한다. IBM Eagle에서 1,000개의 회로 실행을 통해 NISQ 하드웨어상 6큐비트 문제의 해결 가능성이 확인되었다.

arXiv:2609.25149v2cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

최대 독립 집합을 위한 Dual-GNN 다중 수준 조 정

Dual-GNN Multilevel Coarsening for Maximum Independent Set

최대 독립 집합(maximum independent set, MIS) 문제는 스케줄링, 자원 할당, 네트워크 분석 등에 응용되는 기본적인 NP-hard 조합 최적화(combinatorial optimization) 문제이다. 정확 솔버(exact solver)는 고품질 해 또는 최적성 증명(optimality certificate)을 제공할 수 있으나, 계산 비용은 그래프 크기에 따라 급격히 증가한다. 반면 수작업 휴리스틱(hand-crafted heuristic)은 보장을 희생하는 대신 확장성(scalability)을 개선한다. 학습 기반 방법은 그래프 인스턴스 간 구조적 패턴을 활용하는 대안을 제공하지만, 독립 집합을 직접 예측하면 대규모 그래프에서 전역 조율(global coordination)이 어려워질 수 있다. 우리는 대신 학습을 이용해 다중 수준 그래프 조 정(multilevel graph coarsening)을 안내하고, 최종 의사 결정에는 조합 탐색(combinatorial search)을 유지한다. Dual-GNN 다중 수준 조 정 프레임워크는 Partition GNN으로 후보 수축(contraction)을 점수화하고, Representative GNN으로 각 최종 클러스터에 대해 상위 k개의 지역 독립 집합 상태를 선택한다. 최대 2,000개 정점(vertex)을 갖는 Erdős–Rényi 그래프 실험에서 유리한 품질–실행 시간 트레이드오프(quality–runtime trade-off)를 보여준다. 인증된 최적해가 있는 500정점 인스턴스에서, 본 방법은 평균 독립 집합 크기 19.20을 달성하며 이는 최적값 19.30의 99.5%에 해당한다. 정확 해법의 평균 벽시계 시간(wall-clock time) 643.57초를 3.41초로 줄여 약 189배 속도 향상(speedup)을 얻는다. 1,000 및 2,000 정점의 더 큰 그래프에서는 평가된 모든 방법 중 최고의 평균 해 품질을 달성한다. 또한 가장자리 확률(edge probability) $p=0.35$인 Erdős–Rényi 그래프에서만 학습했음에도, 학습된 조 정 정책은 보지 못한 그래프 밀도와 구조적으로 다른 그래프 계열 모두에 효과적으로 일반화(generalize)된다.

arXiv:2609.28085v1cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

잡 샵 스케줄링을 위한 GNN 기반 강화학습에서의 커리큘럼 러닝

Curriculum Learning with GNN-based Reinforcement Learning for Job Shop Scheduling

잡 샵 스케줄링 문제(job shop scheduling problem)는 까다로운 조합 최적화(combinatorial optimization) 문제이며, 최근 그래프 신경망(GNN)을 활용한 강화학습(RL) 접근법은 문제 인스턴스로부터 스케줄링 정책을 직접 학습하는 데 유망함을 보여주었다. 그러나 대규모 인스턴스에 대한 학습은 여전히 연산 비용이 많이 들고, 다양한 인스턴스 크기에 걸친 일반화는 여전히 어려운 과제로 남아 있다. 본 논문에서는 잡 샵 스케줄링 문제에서 그래프 신경망 기반 강화학습을 위한 커리큘럼 러닝(curriculum learning)을 연구하며, 세 가지 타깃 크기인 20 x 20, 25 x 25, 30 x 30에 대해 단일 크기 학습(single-size training)과 비교한다. 커리큘럼 환경에서는 정책을 먼저 더 작은 인스턴스에서 학습시킨 후 점진적으로 더 큰 타깃 크기에 적응시켜, 초기 단계에서 학습된 스케줄링 동작이 더 큰 인스턴스에서의 학습을 뒷받침하도록 한다. 모델은 모든 평가 크기에 걸친 일반화와 타깃 크기에 대한 특화(specialization)를 모두 고려하여, 최적성 갭(optimality gap)을 사용해 8 x 8부터 30 x 30까지의 미확인(unseen) 인스턴스에서 평가된다. 실험 결과에 따르면 커리큘럼 러닝은 실제 학습 소요 시간(wall-clock training time)을 일관되게 단축하며, 타깃 크기가 커질수록 그 이점이 더 커지는 것으로 나타났다. 가장 강력한 이점은 30 x 30에서 관찰되었는데, 커리큘럼 러닝은 모든 평가 크기에 걸친 평균 최적성 갭을 약 8.1%포인트 줄이고, 타깃 크기의 평균 최적성 갭을 약 8.6%포인트 줄였으며, 학습 시간을 약 50시간 절약했다.

arXiv:2607.22356v1cs.LG공통 태그 Combinatorial Optimization, Graph Neural Network

심층 강화학습을 활용한 라스트마일 픽업 통합 주문 배차 및 경로 최적화

Integrated Order Dispatching and Routing for Last-Mile Pickup via Deep Reinforcement Learning

최근 몇 년간 라스트마일 픽업 운영의 복잡성이 증가하면서 물류 플랫폼에서 빠르고 정확한 의사결정에 대한 필요성이 커졌다. 이 과제는 근본적으로 두 가지 핵심적이고 긴밀히 결합된 의사결정 과정, 즉 주문 배차와 경로 최적화에 의해 촉발된다. 이들을 개별적으로 해결하면 상호 의존성을 간과하게 되며, 완전한 end-to-end 학습은 희소 보상(sparse reward)으로 인해 대규모이고 가변적인 규모의 인스턴스에서 불안정하고 비용이 많이 든다. 이 문제를 해결하기 위해, 학습된 경로 오라클(routing oracle)과 실시간 배차 휴리스틱을 결합하는 통합 최적화 프레임워크를 제안한다. 경로 최적화 하위 문제에 대해서는 Look-Ahead Courier-Personalized 디코더를 갖춘 Dynamic-Residual Graph Attention Network 인코더를 개발한다. 배차 하위 문제에 대해서는 경로 오라클이 지도하는 국소 탐색(local search) 기반 배차 휴리스틱을 개발하며, 오라클은 실시간 확장성을 유지하면서 후보 배송 기사를 선택하기 위한 근최적 해를 제공한다. Cainiao Logistics의 실제 데이터셋을 활용한 광범위한 실험을 통해 오프라인 평가와 온라인 롤링 호라이즌(rolling-horizon) 시뮬레이션을 포함하여 접근법의 성능을 검증했다. 실험 결과, 제안 방법은 해 품질과 해결 시간 측면에서 다른 벤치마크를 능가하며, 실시간 대규모 라스트마일 픽업 문제 해결에 물류 기업을 효과적으로 지원할 수 있음을 보여준다.

arXiv:2607.20554v1cs.AI공통 태그 Combinatorial Optimization, Graph Neural Network

Learning-to-Optimize 그래프 신경망을 통한 스마트 도시 NR-V2X 네트워크 AI 기반 다중 홉 릴레이 선택

AI-Driven Multi-Hop Relay Selection for Smart Urban NR-V2X Networks via Learning-to-Optimize Graph Neural Networks

밀집된 도시 환경에서 스마트 모빌리티를 위해 신뢰성 높고 저지연 NR-V2X 통신이 필수적이다. 그러나 제한된 도로변 유닛(RSU) 밀도, 빈번한 비시선(non-line-of-sight) 조건, 그리고 고도로 동적인 차량 토폴로지로 인해 많은 연결·자율주행 차량(CAV)이 안정적인 단일 홉 연결을 유지하지 못하는 경우가 많다. 다중 홉 릴레이 보조 통신이 인프라 커버리지를 확장할 수 있지만, 실질적인 흐름(flow), 용량, 연결성 제약 하에서 릴레이 링크를 실시간으로 선택하는 것은 여전히 어렵다. 혼합 정수 선형 계획(MILP)은 최적의 다중 홉 릴레이 결정을 제공하지만, 계산 복잡도가 네트워크 밀도에 따라 급격히 증가하여 실시간 적용이 제한된다. 이를 해결하기 위해, 실시간 NR-V2X 릴레이 선택을 위한 그래프 신경망(GNN) 기반 Learning-to-Optimise(L2O) 프레임워크를 제안한다. 차량 통신 상태를 속성 그래프(attributed graph)로 모델링하며, CAV와 RSU를 노드로, 후보 무선 링크에는 전파 인식(propagation-aware) 특성을 부여한다. 오프라인 MILP 오라클이 최적의 지도(supervision)를 제공하고, 엣지 인식(edge-aware) Graph Isomorphism Network(GINE)가 오라클 결정을 거의 일정한 추론 지연으로 근사한다. 통합 SUMO--GEMV2 시뮬레이션 파이프라인으로 생성된 대규모 도시 데이터셋에 대한 실험 결과, 제안 방법은 MILP 오라클과 유사한 연결성을 달성하면서 실행 시간을 수 자릿수만큼 단축한다. 이 프레임워크는 기존 차량 자산을 활용하고 스마트 시티 환경에서 확장 가능한 실시간 NR-V2X 운용을 지원함으로써, 도시 V2X 연결성을 비용 효율적으로 향상시킨다.

arXiv:2607.21188v1cs.AI공통 태그 Combinatorial Optimization, Graph Neural Network

머신러닝을 활용한 단일 상수 곱셈의 효율적 SAT 인코딩을 위한 우수 규칙 식별

Identifying Good Rules for Efficient SAT Encodings of Single-Constant Multiplication Using Machine Learning

단일 상수 곱셈(Single Constant Multiplication, SCM) 문제는 하드웨어 설계에서 기본적인 NP-hard 최적화 작업으로, 고정 상수를 덧셈, 뺄셈, 비트 시프트만을 사용하여 분해하는 것을 목표로 한다. 동적 프로그래밍 방법은 SCM에 대해 근최적 SAT 인코딩을 생성할 수 있지만, 큰 상수에 대해서는 인코딩 비용이 여전히 높다. 우리는 분해 과정에서 연산자 선택을 안내하는 우수 규칙을 식별함으로써 SCM SAT 인코딩을 가속화하는 신경-기호(neuro-symbolic) 프레임워크를 제안한다. 우리 접근법은 상수 분해로부터 유망한 연산자 유형을 예측하기 위해 그래프 신경망(graph neural network) 모델을 사용하고, 그 결과 신뢰도 점수를 활용하여 기호적 탐색에서 no-good 선택을 가지치기(prune)한다. 보지 못한 17–32비트 상수에 대한 실험 결과는 인코딩 시간이 1~2자릿수 감소하고, 메모리 사용량이 97% 이상 감소하며, 분기(branching)가 한 자릿수 감소함을 보여주면서, 덧셈 측면에서 근최적 인코딩 품질을 유지한다. 이 결과는 학습 기반 기호적 전략이 SCM 인코딩의 확장성과 효율성을 크게 개선할 수 있음을 보여준다. 우리의 코드와 데이터는 https://github.com/Chufeng-Jiang/SCM_MLDP 에서 공개적으로 이용 가능하다.

토론

이 논문과 연결된 포럼 글이 아직 없습니다.