상상해 보세요. 당신은 전국의 모든 도시를 한 번씩 방문하고 다시 출발지로 돌아오는 최단 경로를 찾아야 하는 택배 기사입니다.
문제: 도시가 10 개라면 길은 몇 가지일까요? 100 개라면? 50 개라면? 도시가 조금만 늘어나도 가능한 경로의 수는 우주에 있는 별의 개수보다도 많아집니다. 이걸 컴퓨터가 다 계산하려면 우주가 멸망할 때까지 걸릴지도 모릅니다.
기존 방식: 모든 가능한 길을 다 그려놓고 하나하나 비교해 보는 방법입니다. (비효율적임)
이 논문의 해결책: "아, 저기 먼 곳으로 가는 길은 절대 최단 경로가 될 수 없겠구나!"라고 미리 추려낸 후, 가장 가까운 이웃 도시들만 연결된 작은 지도를 만들어서 문제를 푸는 것입니다.
🛠️ 이 연구가 한 일: "CAF (비용 기반 간선 필터링)"
연구진은 **'CAF'**라는 이름의 새로운 필터를 개발했습니다. 이를 일상적인 언어로 풀어보면 다음과 같습니다.
현실적인 선택: 우리가 여행할 때, 서울에서 부산으로 바로 가는 비행기보다 서울 - 대전 - 부산 순서로 가는 게 더 효율적인 경우가 많습니다. 즉, 가장 가까운 이웃과만 연결하는 것이 최적의 길일 확률이 높습니다.
수학적 보장: 연구진은 "각 도시마다 가장 가까운 이웃 도시만 절반 (약 50%) 정도 남기고 나머지는 다 지워도, 여전히 모든 도시를 한 번씩 방문하는 길이 반드시 존재한다"는 수학적 이론 (Dirac 의 정리) 을 증명했습니다.
비유: 거대한 숲에서 길을 잃지 않으려면 모든 나뭇가지가 필요할까요? 아니요, 가장 굵고 중요한 가지들만 있어도 길을 찾을 수 있습니다. 연구진은 그 '중요한 가지들'만 남기는 방법을 찾았습니다.
🚀 실험 결과: "고전 컴퓨터 vs 양자 컴퓨터"
이 연구팀은 이 '작은 지도' 전략을 두 가지 방식으로 테스트했습니다.
1. 고전 컴퓨터 (일반적인 슈퍼컴퓨터)
결과: 계산 시간이 약 30~50% 단축되었습니다.
의미: 지도가 작아졌으니, 컴퓨터가 "어디로 갈까?" 고민하는 시간이 줄어든 것입니다. 최적의 답을 찾는 데 실패한 큰 문제에서도, 이 방법을 쓰면 더 좋은 답을 더 빨리 찾아냈습니다.
2. 양자 컴퓨터 (미래의 초고속 컴퓨터)
배경: 양자 컴퓨터는 아직 초기 단계라, 한 번에 처리할 수 있는 정보량 (도시 수) 이 매우 적습니다. 마치 작은 배에 많은 승객을 태우려다 넘어지는 상황과 같습니다.
결과: 이 '작은 지도' 전략을 쓰자, 양자 컴퓨터가 **더 많은 도시 (최대 15 개)**를 처리할 수 있게 되었습니다.
의미: 양자 컴퓨터라는 '작은 배'에 태울 짐을 미리 정리해 주니, 배가 더 멀리, 더 빠르게 갈 수 있게 된 것입니다. 기존에는 해결 불가능했던 문제들을 해결할 가능성을 열었습니다.
💡 결론: 왜 이것이 중요한가요?
이 논문의 핵심 메시지는 **"무조건 다 계산하는 것보다, 현명하게 덜 계산하는 것이 더 빠르고 정확하다"**는 것입니다.
기존: 모든 길을 다 찾아보려다 지쳐버림.
새로운 방법: "가장 유력한 길들만 골라보자" → 계산량이 30% 줄고, 양자 컴퓨터 같은 미래 기술로도 큰 문제를 풀 수 있게 됨.
이 연구는 단순히 여행 경로를 찾는 문제를 넘어, 복잡한 물류, 배송, 심지어 양자 컴퓨터의 한계를 극복하는 데 큰 도움을 줄 수 있는 '현명한 준비'의 중요성을 보여줍니다. 마치 등산할 때 모든 길을 다 가보지 않고, 가장 확실한 등산로만 미리 표시해 두면 훨씬 더 쉽게 정상에 오를 수 있는 것과 같은 이치입니다.
1. 문제 정의 (Problem Definition)
주제: 외판원 문제 (Traveling Salesman Problem, TSP) 는 조합 최적화 분야에서 가장 잘 연구된 문제 중 하나이나, 탐색 공간의 기하급수적 증가와 서브투어 (subtour) 제거를 위한 방대한 수의 제약 조건으로 인해 계산적으로 매우 어렵습니다 (NP-hard).
현재의 한계:
고전적 솔버: 대규모 인스턴스를 해결하는 데 시간이 많이 소요됩니다.
양자 컴퓨팅 (Quantum Annealing): D-Wave 와 같은 양자 어닐러는 하드웨어 연결성 (connectivity) 과 임베딩 요구 사항의 제약으로 인해 매우 작은 인스턴스만 처리할 수 있습니다. 또한, TSP 를 QUBO(Quadratic Unconstrained Binary Optimization) 모델로 변환할 때 제약 조건이 복잡해져 변수와 상호작용 수가 급증하는 문제가 있습니다.
목표: 이러한 한계를 극복하기 위해 최적화 모델의 크기를 줄이면서도 문제의 실현 가능성 (feasibility) 을 유지하는 전처리 전략을 제안하고, 이를 고전적 및 양자 최적화 기법 모두에 적용하여 성능을 평가하는 것입니다.
2. 방법론 (Methodology)
논문은 **비용 기반 아크 필터링 (Cost-Based Arc Filtering, CAF)**이라는 새로운 전처리 방법을 제안합니다.
핵심 아이디어: 완전 그래프 (Complete Graph) 에서 모든 아크 (간선) 를 고려하는 대신, 각 정점 (도시) 에 대해 최저 비용의 이웃 정점들만 선택하여 후보 아크 집합을 축소합니다.
알고리즘 (Algorithm 1):
각 정점 i에 대해 다른 모든 정점 j를 이동 비용 cij의 오름차순으로 정렬합니다.
Dirac 의 정리에 기반하여, 각 정점당 k=⌈n/2⌉개의 가장 가까운 이웃만 선택합니다. (여기서 n은 도시의 수입니다).
선택된 아크들로 구성된 축소된 그래프 G~를 생성합니다.
이론적 보장 (Feasibility Guarantee):
Dirac 의 정리 활용: 그래프 이론의 Dirac 정리에 따르면, 모든 정점의 차수 (degree) 가 n/2 이상이면 해당 그래프는 해밀턴 사이클을 가집니다.
CAF 는 각 정점당 ⌈n/2⌉개의 아크를 유지하므로, 축소된 그래프가 여전히 최소한 하나의 해밀턴 사이클 (유효한 TSP 경로) 을 포함함을 수학적으로 증명합니다. 즉, 전처리 후에도 문제가 실현 가능 (feasible) 합니다.
해결 접근법:
TSP 를 정수 선형 계획법 (ILP) 모델로 공식화합니다.
CAF 를 적용하여 아크 집합을 축소합니다.
고전적 최적화: Gurobi 솔버를 사용하여 CAF 적용 전후의 ILP 모델 성능을 비교합니다.
양자 최적화: D-Wave 의 하이브리드 솔버 (LeapCQMHybrid) 를 사용하여 축소된 모델을 CQM(Constrained Quadratic Model) 프레임워크로 풀어 성능을 평가합니다.
3. 주요 기여 (Key Contributions)
새로운 전처리 전략 (CAF): TSP 모델의 크기를 약 30% 줄이면서도 해밀턴 사이클의 존재를 보장하는 이론적으로 검증된 필터링 방법을 제시했습니다.
양자 최적화에서의 확장성 증대: 기존 양자 TSP 연구가 인위적으로 생성된 매우 작은 인스턴스에 국한되었던 것과 달리, CAF 를 통해 **최대 15 개 도시 (customers)**까지 TSPLIB 벤치마크 인스턴스를 양자 하이브리드 솔버로 해결할 수 있음을 입증했습니다.
실제 벤치마크 데이터 활용: 인공적인 toy 문제가 아닌, TSPLIB 의 표준 벤치마크 (berlin52 등) 를 사용하여 현실적인 평가 환경을 제공했습니다.
고전 및 양자 솔버 모두에 대한 유효성 입증: 전처리 기법이 고전적 솔버의 계산 시간을 단축하고, 양자 솔버의 최적성 갭 (optimality gap) 을 줄이는 데 동시에 기여함을 보였습니다.
4. 실험 결과 (Results)
실험은 TSPLIB 의 berlin52 데이터셋을 기반으로 수행되었으며, 도시 수 (V) 가 5 에서 50 까지 변하는 다양한 인스턴스를 테스트했습니다.
모델 크기 축소 (Table II):
CAF 적용 시 결정 변수 (decision variables) 의 수가 평균 약 30% 감소했습니다.
도시 수가 증가할수록 변수 감소 폭이 커져 모델의 확장성 (scalability) 이 향상됨을 확인했습니다.
고전적 최적화 성능 (Table III):
계산 시간:V≥10인 중간 및 대규모 인스턴스에서 계산 시간이 평균 약 32% 단축되었습니다 (예: V=19에서 257 초 → 139 초).
최적성:V≤20인 경우 CAF 적용 여부와 상관없이 최적해를 모두 찾았으며, 최적 목적 함수 값 (OF) 은 변하지 않았습니다.
한계 극복:V=21에서 시간 제한 (300 초) 을 초과하여 최적성을 증명하지 못했을 때, CAF 를 적용한 경우 더 낮은 목적 함수 값을 얻어 실용적인 이점을 보여주었습니다.
양자 하이브리드 솔버 성능 (Table IV):
해결 가능 범위: CAF 를 통해 최대 V=15까지의 인스턴스를 양자 솔버로 처리할 수 있었습니다.
최적성 갭 (Optimality Gap): CAF 를 적용한 경우, 고전적 솔버 기준 최적해 대비 평균 최적성 갭이 약 29% 감소했습니다 (예: V=13에서 43% → 11%).
계산 효율성: 평균 계산 시간이 약 5~17% 단축되었으며, 특히 V=15에서 성공적으로 해결된 실행 비율이 40% 로 나타났습니다.
5. 의의 및 결론 (Significance & Conclusion)
양자 컴퓨팅의 실용화: 현재 양자 하드웨어의 제한적인 큐비트 수와 연결성을 고려할 때, CAF 와 같은 전처리 기법은 양자 어닐링을 실제 라우팅 문제에 적용하기 위한 필수적인 단계임을 강조합니다.
하이브리드 접근법의 효과: 고전적 전처리와 양자/고전 하이브리드 솔버의 결합은 복잡한 조합 최적화 문제를 해결하는 강력한 패러다임으로 부각되었습니다.
미래 전망: 본 연구는 대규모 TSP 인스턴스를 다루기 위한 모델 축소 기법의 중요성을 보여주었으며, 향후 동적 모델 정제 (iterative solution procedures) 나 다른 축소 기법과의 결합을 통해 더 큰 규모의 문제 해결이 가능할 것으로 기대됩니다.
요약하자면, 이 논문은 **비용 기반 아크 필터링 (CAF)**을 통해 TSP 모델의 복잡성을 줄임으로써, 고전적 솔버의 계산 효율성을 높이고 양자 솔버가 더 큰 규모의 문제를 해결할 수 있는 기반을 마련했다는 점에서 중요한 의의를 가집니다.