MIT와 ETH 취리히의 연구진은 새로운 데이터 기반 머신러닝 기법을 통해 전 세계적인 물류 시스템, 전력망 운영 등과 같은 복잡한 최적화 문제에 새로운 해법을 제시하고 있습니다. 이들이 개발한 기술은 현재 패키지 배송 경로, 백신 배포, 전력망 관리와 같은 어려운 자원 배분 문제에서 더 빠르고 효과적인 해결책을 도출할 수 있도록 도와줄 것으로 기대됩니다.
1. AI와 최적화 문제의 만남
연말이 다가오면 페덱스와 같은 배송 회사는 대규모 배송 최적화 문제에 직면하게 됩니다. 이를 해결하기 위해 혼합 정수 선형 프로그래밍(MILP) 솔버라는 특수 소프트웨어가 사용되는데, 이 솔버는 문제를 작은 조각으로 나누고 가장 좋은 해결책을 찾기 위해 다양한 알고리즘을 적용합니다. 그러나 이 과정은 해결책을 얻는 데 몇 시간에서 며칠까지 걸릴 수 있습니다.
MIT와 ETH 연구진은 MILP 솔버가 해결하는 중간 단계에서 과도한 시간 소모를 줄일 수 있는 방법을 찾아냈습니다. 특정 유형의 문제에 대해 최적화된 해결책을 찾을 수 있도록 필터링 기법을 적용하고 머신러닝을 활용하여 이를 보다 빠르고 효율적으로 해결할 수 있게 된 것입니다.
2. 데이터 기반 기법의 주요 장점
이 데이터 기반 기법은 MILP 솔버의 속도를 30~70% 향상시키면서도 정확도를 유지합니다. 이를 통해 사용자는 최적의 솔루션을 더 빠르게 얻거나 특히 복잡한 문제의 경우 더 나은 해결책을 제한된 시간 내에 도출할 수 있습니다. 이는 데이터가 풍부한 상황에서 더욱 유리하게 작용하며, 페덱스와 같은 기업이 과거 데이터를 활용해 문제 해결 시간을 줄일 수 있습니다.
전문가의 의견: 데이터와 머신러닝의 결합
연구의 주 저자이자 MIT의 민첩한 환경 엔지니어링과 데이터 시스템 교수인 캐시 우(Cathy Wu) 교수는 최적화 분야에서 기계 학습과 전통적인 접근 방식을 결합하여 양질의 해결책을 얻을 수 있는 가능성에 대해 강조했습니다.
3. 복잡한 최적화 문제 해결의 난제와 도전 과제
MILP 문제는 다양한 가능성을 가지고 있지만, 그 중에서도 특정 해를 찾아내는 데 필요한 시간은 거의 무한대에 가깝습니다. 예를 들어 여행하는 판매원이 여러 도시를 최단 경로로 방문하고 귀환하려는 문제를 해결하려고 할 때, 그 경우의 수는 우주에 있는 원자 수보다 많을 수 있습니다.
4. 필터링과 머신러닝을 통한 문제 해결
연구진은 MILP 솔버의 중요한 단계 중 하나인 ‘분리자(Separator)’ 선택을 데이터 기반으로 최적화할 수 있는 방법을 찾아냈습니다. 이 필터링 메커니즘은 130,000개가 넘는 가능성에서 20개의 옵션으로 줄이며, 이후 머신러닝 모델이 최적의 분리자 조합을 선택합니다.
이 모델은 사용자의 최적화 문제에 특정된 데이터 세트로 학습하여, 각기 다른 문제에 대해 최적화된 알고리즘 조합을 자동으로 선택할 수 있게 설계되었습니다. 페덱스와 같은 기업이 과거 데이터를 활용하여 학습된 모델을 통해, 이전 문제 해결 경험을 바탕으로 효율성을 극대화할 수 있습니다.
5. 향후 연구 방향과 발전 가능성
우 교수와 연구진은 앞으로 이 기법을 보다 복잡한 MILP 문제에 적용하고, 더 적은 데이터 세트로 학습한 모델을 보다 큰 최적화 문제에 적용하는 방법을 연구할 계획입니다. 이 연구는 Mathworks, 미국 국립 과학 재단(NSF), MIT 아마존 과학 허브 및 MIT 연구 지원 위원회가 지원했습니다.
분리자의 개념은 다양한 분야에서 적용 가능합니다. 분리자는 본래 최적화 문제에서 불필요한 탐색을 줄이고 필요한 부분만 남겨 빠르고 효율적인 해결책을 찾는 데 도움을 주기 때문에, 이와 같은 구조의 문제를 해결해야 하는 다른 분야에서도 유용하게 사용할 수 있습니다.
다음은 운동경기와 비즈니스 등 여러 분야에서의 적용 가능성을 예로 든 것입니다.
6. 운동 경기에서의 분리자 적용
- 전략 최적화: 축구나 농구 같은 스포츠에서는 다양한 전략과 플레이를 선택해야 하는데, 분리자는 이러한 선택지 중 불필요하거나 성공 가능성이 낮은 전술을 배제하여 더 효과적인 전략을 선택하는 데 도움을 줄 수 있습니다.
- 선수 위치 최적화: 팀 스포츠에서는 선수 위치와 동선이 중요한데, 분리자를 통해 가장 효율적인 위치와 경로를 분석하고 추천함으로써 경기 중 선수 배치를 최적화할 수 있습니다.
- 운동 데이터 분석: 피트니스 또는 개인 운동 기록 데이터를 분석할 때도 분리자를 적용하여 유의미한 데이터를 중심으로 분석을 진행함으로써, 개인의 운동 성과를 높일 수 있는 최적의 훈련법을 추천하는 데 도움을 줄 수 있습니다.
7. 비즈니스 분야에서의 분리자 적용
- 고객 세분화: 분리자를 활용해 고객 데이터를 분석하면 불필요한 분석 범위를 줄이고 핵심 고객층을 식별하는 데 도움이 됩니다. 이를 통해 맞춤형 마케팅 전략을 세우거나 특정 고객군에게 맞춘 프로모션을 진행할 수 있습니다.
- 물류 및 공급망 최적화: 기업의 물류 및 재고 관리에서도 분리자는 최적의 배송 경로를 찾고 불필요한 물류 단계를 줄이는 데 유용합니다. 이를 통해 배송 시간과 비용을 절감할 수 있습니다.
- 프로젝트 관리 최적화: 비즈니스 프로젝트에서 여러 과제가 얽혀 있을 때, 분리자를 사용해 필수적인 과제를 중심으로 작업을 진행하도록 설정하면 프로젝트 완료 시간을 단축하고 리소스를 최적화할 수 있습니다.
8. 기타 분야
- 금융 투자: 분리자를 사용해 여러 투자 옵션 중에서 목표 수익률이나 위험을 기준으로 불필요한 옵션을 배제하고 최적의 투자 포트폴리오를 구성할 수 있습니다.
- 의료 진단: 의료 데이터에서 분리자를 사용하면 필요한 진단 요소에 집중하여 정확한 진단과 치료법을 제시하는 데 도움이 될 수 있습니다. 예를 들어, 특정 질병의 초기 진단을 위해 필요 없는 검사를 줄이고 가장 유의미한 검사에 집중할 수 있습니다.
- 교육 분야: 학생의 성향과 학습 데이터를 분석할 때 분리자를 사용해 개별 학습자의 학습 효율을 높일 수 있는 맞춤형 학습 경로를 제시할 수 있습니다.
분리자는 경로를 최적화하거나 선택지를 줄여야 하는 모든 문제에서 활용할 수 있는 범용적인 도구입니다. 운동 경기에서 전략을 최적화하거나, 비즈니스에서 고객 분석과 물류 관리를 개선하는 등 복잡한 문제를 빠르고 효과적으로 해결할 수 있도록 돕는 강력한 방법으로 사용될 수 있습니다.
‘분리자(Separator)’는 MILP 솔버가 문제를 해결할 때 사용하는 여러 가지 알고리즘 중 하나로, 문제의 검색 범위를 줄여주는 역할을 합니다. 최적화 문제에서는 가능한 많은 해결 방법을 탐색해야 하는데, 이 과정에서 분리자가 불필요한 경우의 수를 걸러내고 꼭 필요한 경우만 남겨줌으로써 시간과 자원을 절약할 수 있게 합니다.
하지만 MILP 솔버에 적용 가능한 분리자는 수만 가지가 넘기 때문에, 최적의 분리자 조합을 찾는 것 자체가 또 다른 복잡한 문제로 남아 있습니다. 연구진은 이 과정을 효율화하기 위해 ‘필터링 메커니즘’을 도입하여 가능한 분리자 조합을 20개 정도로 줄인 후, 최적의 조합을 찾기 위해 데이터 기반의 머신러닝 모델을 활용했습니다. 이 모델은 이전의 최적화 문제 해결 데이터를 학습함으로써, 사용자에게 적합한 분리자 조합을 찾아내어 더욱 빠르게 문제를 해결할 수 있도록 돕습니다.
간단히 말해, 연구진은 많은 분리자 중에서 가장 효과적인 조합을 자동으로 찾아낼 수 있는 방법을 개발하여, MILP 솔버가 복잡한 최적화 문제를 더 빠르고 효율적으로 해결할 수 있도록 한 것입니다.