LG AI Research: 조합 최적화 문제를 위한 확산 모델 연구

머신러닝 분야의 권위 있는 학회인 ICML 2024에서 LG AI Research의 Data Intelligence(DI) Lab이 조합 최적화 문제를 해결하기 위한 새로운 접근법을 선보였다.

연구팀은 강화 학습(RL)과 최근 주목받는 생성 모델인 **확산 모델(Diffusion Model)**을 결합한 **CADO(Cost-Aware Diffusion Solvers)**를 제안했다. 이 모델은 비용을 고려한 확산 솔버를 통해 조합 최적화 문제를 효율적으로 해결한다.

**조합 최적화(Combinatorial Optimization)**는 유한한 후보 집합 내에서 특정 목적 함수를 만족하는 최적의 해를 찾는 분야다. 대표적인 예로 모든 도시를 한 번씩 방문하며 총 거리를 최소화하는 **외판원 문제(Traveling Salesman Problem)**가 있다.

이러한 문제는 물류 서비스, 공항 항공기 스케줄링, 유전체 분석 등 산업 전반에서 매우 중요하다. LG AI Research는 현재 PCB(인쇄 회로 기판) 자동 배선 설계 자동화 과제를 수행 중이며, 이를 RSTPP(Rectilinear Steiner Tree Packing Problem) 형태의 조합 최적화 문제로 변환하여 해결하고 있다.

기존의 브루트 포스(Brute-force) 방식은 도시 수가 늘어남에 따라 계산량이 기하급수적으로 증가하는 NP-hard 문제의 한계를 가진다. LG AI Research는 이를 극복하기 위해 확산 모델을 활용한 최신 연구들을 지속적으로 탐구하고 있다.