NVIDIA cuOpt: 프라이멀 휴리스틱(Primal Heuristics)을 활용한 혼합 정수 최적화 가속화 기술

NVIDIA cuOpt는 대규모의 복잡한 의사결정 문제에 대해 신속하고 고품질의 해답을 제공하도록 설계된 GPU 가속 기반 최적화 엔진입니다. 혼합 정수 계획법(Mixed Integer Programming, MIP)은 문제를 해결하는 주요 기법 중 하나로, 일련의 선형 제약 조건으로 모델링되며 일부 변수는 정수 값만 가질 수 있는 특징이 있습니다. MIP로 모델링할 수 있는 문제 유형은 생산 계획, 공급망, 운송, 스케줄링, 금융 등 매우 방대합니다.

NVIDIA cuOpt는 제약 조건이 복잡한 대규모 문제에 대해 저지연, 고품질의 최적화를 구현하도록 설계된 GPU 가속 솔버입니다. cuOpt의 핵심은 연속 변수와 정수 변수가 혼합된 선형 제약 조건을 기반으로 의사결정 과정을 공식화하는 MIP를 활용하는 데 있습니다. 이를 통해 공급망 네트워크 최적화, 경로 및 배차 최적화, 인력 및 작업 스케줄링, 생산 계획, 퀀트 금융 등 다양한 분야에 적합합니다.

MIP 솔버를 위한 가속 프라이멀 휴리스틱은 전체 솔루션 공간을 전수 조사하지 않고도 실행 가능한 고품질의 해(Feasible solution)를 찾아내는 알고리즘입니다. 이 기술이 필요한 이유는 크게 두 가지입니다. 첫째, 실제 산업 현장의 많은 MIP 문제는 규모가 너무 크거나 시간에 민감하여 기존 솔버로는 제때 답을 찾기 어렵기 때문입니다. 둘째, 분기 한정법 알고리즘에서 탐색 공간을 가지치기하여 효율성을 높여주기 때문입니다. 가속 휴리스틱은 병렬 처리와 더 스마트한 탐색 전략을 활용해 해결 시간을 단축하며, 이를 통해 기업은 갑작스러운 변동 상황에 신속히 대응하고 저지연 의사결정을 내릴 수 있습니다.

본 포스팅에서는 NVIDIA cuOpt가 GPU 가속을 통해 어떻게 MIP 문제에 대한 고품질의 솔루션을 제공하는지 설명합니다. 특히 프라이멀 휴리스틱을 활용하여 MIPLIB 벤치마크 세트의 4가지 공개 인스턴스(liu.mps, neos-3355120-tarago.mps, polygonpack4-7.mps, bts4-cta.mps)에서 새로운 해를 발견한 사례를 공유합니다. 시연된 결과는 주요 오픈 소스 CPU 솔버와 비교했을 때 해의 품질과 실행 가능한 해를 찾아내는 성능 면에서 실질적인 개선이 이루어졌음을 보여줍니다.

대규모 MIP 문제에서 신속하고 고품질인 해가 중요한 이유

MIP는 NP-hard 문제군에 속합니다. 이는 최악의 경우, 어떤 알고리즘으로도 모든 문제를 빠르게 해결할 수 없음을 의미합니다. 하지만 이러한 복잡성에도 불구하고, 상용 MIP 솔버들은 대규모 문제 인스턴스에 대해 최적해를 일상적으로 도출해내고 있습니다.

그러나 특정 문제들은 여전히 해결이 매우 까다롭거나 방대한 계산 시간을 필요로 합니다. MIP 모델은 현실 세계의 문제를 반영하며 운영 비용과 직결되는 경우가 많기 때문에, 더 크고 복잡한 문제를 효율적으로 해결할 수 있는 알고리즘을 개발하는 것은 20세기 중반부터 이어져 온 오랜 과제였습니다. 그동안 분기 한정법, 절단평면법, 피지빌리티 펌프와 같은 프라이멀 휴리스틱, 그리고 최신 병렬 처리 기술에 이르기까지 이론적·계산적으로 중대한 비약이 이루어졌습니다.

현실의 문제는 대개 유동적이며 데이터가 실시간으로 변합니다. 따라서 솔버는 반복적이고 점진적인 방식을 사용해야 하며, 이 과정의 모든 단계에서 속도는 필수적입니다. 유연한 작업장 스케줄링(Flexible Job-shop Scheduling)과 그 변형 모델들, 로트 크기 결정, 항공사나 철도의 승무원 스케줄링 등이 시간에 매우 민감한 대표적인 MIP 사례들입니다. 이에 따라 NVIDIA cuOpt는 프라이멀 휴리스틱 개발에 상당한 노력을 기울여 왔으며, 이를 통해 오픈 소스 솔버보다 훨씬 짧은 시간 안에 고품질의 해를 찾아내는 성과를 거두고 있습니다.

MIP에서 고품질의 실행 가능한 해를 구하는 방법

현재까지 가장 성공적인 프라이멀 휴리스틱 중 하나는 피지빌리티 펌프(FP)이며, 매년 이 아이디어를 기반으로 한 새로운 논문들이 발표되고 있습니다. FP의 핵심 아이디어는 비교적 간단합니다. 실행 가능 영역으로의 투영과, 도메인 전파를 통해 분수 형태로 남은 변수들을 반올림하는 과정을 반복하는 것입니다.

NVIDIA는 GPU 성능을 극대화하고 FP 알고리즘의 두 가지 주요 병목 현상을 해결하기 위해 기존 알고리즘을 개선하는 것부터 시작했습니다.

1. 선형 계획법(LP) 문제로 모델링되는 투영 단계
2. 투영 이후 진행되는 도메인 전파 단계

NVIDIA는 FP 알고리즘에서 투영의 정밀도가 그리 중요하지 않다는 점을 발견했습니다. 정밀도를 낮춰도 유사한 결과를 얻었기 때문입니다. 여기서 착안하여 심플렉스 알고리즘 대신 1차 근사 방법을 사용할 수 있겠다고 판단했고, 다행히 cuOpt 프레임워크에는 이미 PDLP(Primal-Dual hybrid gradient) 알고리즘이 구현되어 있었습니다.

NVIDIA는 이전 투영 단계의 프라이멀 및 듀얼 솔루션을 사용하여 PDLP 알고리즘을 웜 스타트 방식으로 실행했습니다. FP 과정뿐만 아니라 루트 노드에서도 PDLP를 사용한 덕분에 반복 계산 속도가 훨씬 빨라졌고, 대규모 문제도 더 효과적으로 해결할 수 있었습니다. 두 번째 병목 현상을 해결하기 위해, 벌크 반올림과 동적 변수 순위 지정 같은 대폭적인 개선 사항을 적용하여 GPU 버전의 도메인 전파 알고리즘을 구현했습니다. 이러한 병목들을 제거한 후, 초점은 FP 내의 사이클링 문제를 해결하는 것으로 옮겨졌습니다.

사이클링은 동일한 단계가 반복되는 현상으로, 대개 탐색 공간의 다른 영역을 찾기 위해 무작위성을 도입하여 해결합니다. 하지만 우리는 사이클을 끊는 동시에 목적 함수를 개선하기 위해 Local-MIP 알고리즘을 선택했습니다. 효율성을 위해 Local-MIP를 GPU 상에서 구현했으며, 그 결과 표준 CPU 버전보다 뛰어난 성능을 보였습니다.

또한 매 반복마다 목적 함수 컷오프를 추가하여 새로운 최적 실행 해를 찾아냈습니다. 이와 관련된 자세한 내용은 NVIDIA가 발표한 논문에서 확인하실 수 있습니다.

이러한 개선을 통해 실행 가능한 해를 찾기 위한 진보된 프라이멀 휴리스틱이 탄생했습니다. 아래 표는 실행 가능한 해의 개수(3회 실행 평균)와 목적 함수 갭(최적해와 당사 휴리스틱이 찾은 해 사이의 정규화된 차이) 측면에서, 최신 FP 변형 모델 및 Local-MIP와 당사 방식을 비교한 결과입니다.

표 1. GPU 실행 가능성 및 프라이멀 갭 결과 (출처: [2510.20499] 혼합 정수 계획법을 위한 GPU 가속 프라이멀 휴리스틱)

앞서 언급한 개선 사항 외에도, 모델을 더욱 정교화하기 위해 세 가지 새로운 진화 알고리즘을 도입했습니다. 이 진화 알고리즘은 탐색의 정체가 감지될 때 적용되어 프라이멀 갭을 추가로 3% 더 줄여주는 효과를 냈습니다. 또한, 절단평면을 제외한 단순 분기 한정법 방식에 다이빙 스레드와 subMIP 기반 진화 알고리즘을 결합함으로써 더욱 큰 성능 향상을 거둘 수 있었습니다. 이제 이 방식과 널리 사용되는 오픈 소스 솔버들의 성능을 비교해 보겠습니다.

MIP 솔버 벤치마크 결과

해당 그래프들은 정교한 절단평면 알고리즘과 문제별 맞춤형 방법론을 탑재한 솔버들과 비교해도 비약적인 속도 향상이 있었음을 보여줍니다. 이는 향후 성능이 더욱 개선될 여지가 충분하다는 점뿐만 아니라, 기존의 어떤 솔버든 앞서 상세히 설명한 GPU 가속 프라이멀 휴리스틱을 추가하여 성능을 보강할 수 있다는 가능성을 시사합니다.

GPU가 MIP 해결을 실용적으로 만드는 방식

신속하고 실행 가능한 MIP 해 도출은 의사결정 인텔리전스 파이프라인에서 핵심적인 역할을 합니다. 이를 Palantir Ontology나 NVIDIA Nemotron 추론 에이전트와 같은 시스템과 통합하면, 수많은 운영 모델에 걸쳐 시나리오 생성 및 평가를 병렬로 수행할 수 있습니다. cuOpt에 포함된 오픈 소스 GPU 가속 MIP 솔버는 단 몇 초 만에 실행 가능한 해를 계산해 내며, 이를 통해 하위 에이전트들은 상황 변화에 맞춰 대안을 시뮬레이션하고 계획을 재최적화할 수 있습니다. 이러한 기능은 정적인 최적화 단계를 대규모 적응형 의사결정을 지원하는 연속적인 피드백 프로세스로 전환해 줍니다.

MIP 휴리스틱 솔버 시작하기

MIP 휴리스틱은 문제 공간을 전수 조사하지 않고도 신속하게 실행 가능한 해를 제공합니다. 이를 통해 기업은 항만 지연, 장비 고장, 급격한 수요 급증과 같은 실제 현장의 돌발 변수에 빠르게 대응하고 대안을 테스트할 수 있습니다. NVIDIA cuOpt는 GPU 가속을 통해 이러한 휴리스틱을 대규모 환경에서도 실용적으로 활용할 수 있게 하며, 더 빠른 해 도출과 목적 함수 갭 감소를 실현하여 지속적이고 적응적인 의사결정 파이프라인을 구축하도록 돕습니다. 지금 바로 NVIDIA cuOpt GitHub를 방문하여 여러분의 최적화 문제를 위한 다양한 MIP 활용 사례와 예제를 직접 체험해 보시기 바랍니다.