FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization

이 논문은 합성 데이터의 한계를 넘어 실세계 구조와 대규모 규모를 반영하는 새로운 벤치마크 'FrontierCO'를 제안하고, 이를 통해 기존 최적화 솔버와 비교 평가한 머신러닝 기반 솔버들의 실제 성능과 한계를 체계적으로 분석합니다.

핵심

1. 문제: "인형 놀이터"에서만 실력을 보여준 AI 들

지금까지 AI 가 조합 최적화 문제를 푼다는 연구들은 대부분 가상의 인형 놀이터에서 이루어졌습니다.

• 상황: 연구자들은 AI 에게 "도시가 100 개 있는 지도에서 가장 짧은 길을 찾아라"라고 시켰습니다.
• 문제: 이 100 개의 도시는 AI 가 훈련할 때 본 것과 똑같은 모양으로, 너무 단순하고 규칙적이었습니다. 마치 유치원생에게만 맞춰진 쉬운 퀴즈를 풀게 한 것과 같습니다.
• 현실: 실제 세상 (공장, 물류, 통신망) 은 훨씬 더 복잡합니다. 도시가 수백만 개일 수도 있고, 도로가 막히거나, 예상치 못한 장애물이 생길 수도 있습니다.
• 결론: AI 는 유치원 퀴즈는 잘 풀지만, 실제 세상에서 벌어지는 거대하고 복잡한 문제를 만나면 당황해서 엉망이 됩니다.

2. 해결책: FRONTIERCO (진짜 시험지)

이 논문은 **"FRONTIERCO"**라는 새로운 시험지를 만들었습니다. 이 시험지는 다음과 같은 특징이 있습니다.

• 실전 감수: 실제 대회 (DIMACS, TSPLib 등) 에서 쓰이던 진짜 문제들을 가져왔습니다.
• 규모의 차이: 기존 시험지가 "도시 100 개"였다면, FRONTIERCO 는 **"도시 1,000 만 개"**나 "정점 800 만 개" 같은 거대한 문제를 다룹니다.
  • 비유: 기존 시험지가 "한 블록을 걷는 것"이었다면, FRONTIERCO 는 "전 세계를 한 번에 돌아다니는 것"을 요구합니다.
• 난이도 조절:
  • 쉬운 세트: 과거에는 어려웠지만, 지금은 인간 전문가들이 쉽게 푼 문제 (AI 가 기본기를 보여줄 수 있는 곳).
  • 어려운 세트: 아직 인간도 완벽하게 풀지 못하거나, 풀기 위해 엄청난 시간이 걸리는 문제 (AI 의 한계를 시험하는 곳).

3. 실험: AI vs 인간 전문가

이 새로운 시험지를 통해 16 가지의 다양한 AI 방법 (신경망, 대형 언어 모델 등) 과 최고의 인간 전문가들이 만든 프로그램을 대결시켰습니다.

🏆 결과 요약: 인간이 여전히 압도적입니다.

1. 규모가 커질수록 AI 는 무너집니다.

   • 작은 문제에서는 AI 가 인간과 비슷하게 잘 풀기도 했지만, 문제가 거대해지자 AI 는 길을 잃거나 아예 답을 못 냈습니다.
   • 비유: 작은 미로에서는 AI 가 잘 빠져나왔지만, 서울 전체를 미로처럼 만들자 AI 는 미로 속에서 헤매다 지쳐버렸습니다.

2. AI 는 '구조'를 이해하지 못합니다.

   • AI 는 주로 국소적인 (작은 부분의) 패턴만 봅니다. 하지만 실제 문제는 전체적인 구조를 이해해야 풀립니다.
   • 비유: AI 는 나무 한 그루의 잎사귀는 잘 보지만, 숲 전체의 흐름은 보지 못합니다.

3. LLM(대형 언어 모델) 의 흥미로운 발견.

   • 어떤 AI 는 인간 전문가보다 더 좋은 답을 내기도 했습니다. 하지만 이는 운에 가깝습니다.
   • LLM 은 다양한 알고리즘을 조합해 코드를 짜지만, "이 코드가 왜 좋은지"를 깊이 있게 이해하지 못합니다.
   • 비유: LLM 은 요리 레시피 책에서 무작위로 재료를 섞어 새로운 요리를 만들지만, 왜 그 조합이 맛있는지 과학적으로 설명하지는 못합니다. 때로는 천재적인 요리를 만들지만, 실패할 확률도 매우 높습니다.

4. 핵심 교훈: 왜 이 연구가 중요한가?

이 논문은 우리에게 **"AI 가 아직은 인간 전문가를 완전히 대체할 준비가 되지 않았다"**는 사실을 냉정하게 알려줍니다.

• 과거의 착각: "AI 가 작은 문제에서 잘하니까, 큰 문제에서도 잘할 거야"라고 생각했습니다.
• 현실: 작은 문제와 큰 문제는 완전히 다른 게임입니다.
• 미래: AI 는 인간 전문가가 만든 도구를 보조하는 역할 (예: 인간의 아이디어를 더 빠르게 검증하거나, 간단한 부분을 처리) 로는 훌륭하지만, 복잡한 실전 문제를 혼자서 해결하는 '슈퍼 영웅'이 되려면 아직 갈 길이 멉니다.

5. 결론: 더 단단한 AI 를 위한 첫걸음

FRONTIERCO 는 AI 연구자들에게 **"진짜 세상에서 통하는지 증명해 보라"**는 엄격한 기준을 제시합니다.

• 비유: 과거의 AI 연구가 "인형 놀이터에서 장난감 자동차 경주"였다면, FRONTIERCO 는 "실제 레이스 트랙에서 프로 레이서와 경주"를 시킨 것입니다.
• 이 시험지를 통해 AI 개발자들은 자신의 모델이 어디가 약한지 정확히 알게 되었고, 앞으로 더 강력하고 현실적인 AI 를 만드는 데 필요한 방향을 잡게 되었습니다.

한 줄 요약:

"지금까지 AI 는 유치원 퀴즈만 잘 풀었는데, FRONTIERCO 라는 진짜 시험지로 그 한계를 확인했고, 아직은 인간 전문가가 훨씬 낫지만 AI 가 인간을 돕는 새로운 길을 찾고 있습니다."

기술 요약

1. 문제 제기 (Problem)

조합 최적화 (Combinatorial Optimization, CO) 문제는 물류, 스케줄링, 네트워크 설계 등 다양한 분야에서 핵심적인 역할을 하지만, 대부분 NP-난해 (NP-hard) 문제입니다. 기존 연구에서는 기계학습 (ML) 기반 솔버가 전통적인 휴리스틱이나 정밀 솔버를 대체하거나 보완할 수 있다는 기대가 있었으나, 다음과 같은 한계로 인해 실제 성능에 대한 엄밀한 평가가 이루어지지 않았습니다.

• 규모의 한계: 기존 ML 평가는 주로 소규모 (예: TSP 노드 수 100~1,000 개) 인 합성 데이터 (Synthetic Data) 에 의존했습니다.
• 현실성 부족: 합성 생성기는 실제 세계의 불규칙한 구조 (irregular structure) 나 경쟁 대회 수준의 난이도를 반영하지 못합니다.
• 일반화 능력 미흡: ML 솔버는 훈련 데이터와 동일한 분포의 테스트 데이터에서 잘 작동하지만, 구조가 복잡하거나 규모가 급격히 커지는 실제 환경에서는 성능이 급격히 저하됩니다.

이러한 배경 하에, 실제 세계의 구조와 극단적인 규모 (Large-scale) 에서 ML 기반 CO 솔버의 성능을 평가할 수 있는 새로운 벤치마크의 필요성이 대두되었습니다.

2. 방법론 (Methodology)

저자들은 FRONTIERCO라는 새로운 벤치마크를 제안하며, 이를 통해 8 가지 주요 CO 문제와 16 가지 ML 솔버를 평가했습니다.

2.1 FRONTIERCO 벤치마크 구성

• 문제 범위: 5 가지 카테고리, 총 8 가지 문제 (MIS, MDS, TSP, CVRP, CFLP, CPMP, FJSP, STP) 를 포함합니다.
• 데이터 소스: 합성 데이터가 아닌, TSPLib, DIMACS 챌린지, PACE 챌린지, CFLP 테스트베드 등 실제 경쟁 및 공개 리포지토리에서 가져온 데이터를 사용합니다.
• 난이도 구분:
  • Easy Set: 과거에는 어려웠으나 현재 최상위 (SOTA) 고전 솔버로 해결 가능한 사례.
  • Hard Set: 최적해가 알려지지 않았거나 계산적으로 매우 부담스러운 오픈 문제 (예: 1000 만 노드 규모의 TSP, 800 만 노드 규모의 MIS).
• 규모: 기존 ML 평가 (TSP 10k 노드 등) 를 훨씬 초과하는 규모로 확장 (TSP 최대 1000 만 노드, MIS 최대 800 만 노드).
• 평가 지표: **Primal Gap(1 차 갭)**을 사용하며, 실행 불가능한 해 (Infeasible solution) 에 대해서는 100% 갭을 부여하여 실패를 명확히 구분합니다.

2.2 평가 대상 솔버

• 고전 솔버 (Baseline): KaMIS, LKH-3, HGS, Gurobi, CPLEX, SCIP-Jack 등 각 문제별 SOTA 고전 솔버.
• ML 기반 솔버 (16 개):
  • Neural Solvers: DiffUCO, SDDS, RLNN, LEHD, DIFUSCO, SIL, DeepACO 등 (그래프 신경망, 강화학습, 확산 모델 기반).
  • Symbolic/LLM Agents: FunSearch, Self-Refine, ReEvo 등 (LLM 을 활용한 알고리즘 생성 및 자기 개선).

2.3 실험 설정

• 모든 솔버는 단일 CPU 코어 (고전/ML) 또는 단일 GPU (Neural) 에서 1 시간 (3600 초) 의 시간 제한 하에 실행됩니다.
• 훈련/검증 데이터는 ML 솔버 간 공정한 비교를 위해 표준화된 생성기를 사용하여 생성했습니다.

3. 주요 기여 (Key Contributions)

1. 실제 구조와 극단적 규모의 벤치마크: 8 가지 문제에 대해 경쟁 대회 및 실제 리포지토리 데이터를 기반으로 한, 기존 ML 평가보다 수백 배에서 수천 배 큰 규모의 통합 평가 스위트 제공.
2. 통일된 평가 (Unified Evaluation): 16 가지 ML 솔버와 SOTA 고전 솔버를 동일한 프로토콜 하에 직접 비교.
3. 실증적 통찰 (Empirical Insights): 현재 ML 접근법의 근본적인 한계와 잠재력을 규명하고, 향후 연구 방향을 제시.

4. 결과 (Results)

FRONTIERCO 를 통한 평가 결과, 다음과 같은 핵심 발견이 도출되었습니다.

• ML 과 고전 솔버 간의 성능 격차: 모든 문제 유형과 난이도에서 ML 기반 솔버는 인간이 설계한 SOTA 솔버보다 현저히 낮은 성능을 보였습니다. 특히 Hard Set에서 이 격차는 더욱 벌어졌습니다.
  • 예시: 기존 논문에서 LEHD 는 TSP 에서 0.72% 의 갭을 보였으나, FRONTIERCO 의 Easy Set 에서는 10%, Hard Set 에서는 77% 의 갭을 기록하며 성능이 급격히 저하되었습니다.
• 확장성 (Scalability) 문제:
  • 신경망 솔버는 대규모 인스턴스에서 메모리 부족 (OOM) 이나 추론 시간 초과를 자주 겪었습니다.
  • TSP 1000 만 노드와 같은 극대규모에서 LEHD 는 1 시간 내에 해를 찾지 못했습니다.
  • 신경망은 국소적 구조 (Local structure) 에 의존하는 경향이 있어, 비유클리드 (Non-Euclidean) 또는 전역적 구조가 중요한 문제 (예: MIS, STP) 에서 성능이 떨어졌습니다.
• LLM 기반 에이전트의 양면성:
  • 잠재력: FunSearch 나 Self-Refine 같은 LLM 에이전트는 특정 Hard Set (예: CVRP) 에서 기존 SOTA 솔버 (HGS) 를 능가하는 알고리즘을 자동 생성하여 발견했습니다.
  • 불안정성: LLM 기반 솔버는 알고리즘의 효과를 스스로 평가하는 능력이 부족하여, 실행마다 성능 편차 (Variance) 가 매우 컸습니다. 또한, 검증하기 어려운 문제나 대규모 인스턴스에서는 비효율적인 알고리즘을 생성하여 리소스 낭비를 초래하기도 했습니다.
• 신경 모듈의 기여도: 신경 모듈이 기존 휴리스틱 (예: 2-OPT) 보다는 성능을 향상시켰지만, 이미 강력한 고전 솔버 (예: LKH-3, Gurobi) 에 비하면 그 개선 폭은 미미했습니다.

5. 의의 및 결론 (Significance)

• 현실적 평가의 필요성 강조: 기존 ML 연구가 합성 데이터와 소규모 인스턴스에 치중하여 실제 적용 가능성을 과장해 왔음을 지적합니다. FRONTIERCO 는 ML 솔버가 실제 산업 현장에서 경쟁하기 위해 극복해야 할 '진짜 장벽'을 제시합니다.
• 연구 방향 제시:
  • Neural Solvers: 단순한 엔드 - 투 - 엔드 (End-to-End) 접근보다는 고전 솔버와 결합된 하이브리드 방식이나, 더 컴팩트한 아키텍처 설계가 필요함을 시사합니다.
  • LLM Agents: 알고리즘 생성 능력은 뛰어나지만, 생성된 알고리즘의 타당성을 검증하는 내부 추론 능력 (Internal Reasoning) 과 안정성 향상이 시급합니다.
• 오픈 소스: FRONTIERCO 벤치마크와 관련 코드는 공개되어 (Hugging Face, GitHub) 향후 ML 기반 CO 솔버 연구의 표준 평가 기준으로 활용될 것입니다.

결론적으로, 이 논문은 ML 기반 조합 최적화 솔버가 아직은 고전적 방법론을 대체할 단계가 아니며, 실제 세계의 복잡성과 규모를 고려한 엄격한 평가 없이는 진정한 진전을 논할 수 없음을 강력히 주장합니다.