Tensor-Network Formulation of the Traveling Salesman Problem and Variants

본 논문은 볼츠만 가중 계층과 카운팅 필터를 사용하여 순차적 주변 규칙을 통해 최적 경로를 식별하는 텐서 네트워크 형식을 여행하는 세일즈맨 문제 및 그 변형에 도입하며, 이는 특수화된 고전 솔버에 대한 우월한 대안이라기보다는 소규모 산업 응용을 위한 휴리스틱으로 기능한다.

핵심

이 논문은 간단한 언어와 창의적인 비유를 사용하여 설명합니다.

큰 그림: 새로운 유형의 계산기로 '외판원' 퍼즐 해결하기

당신은 외판원이라고 상상해 보세요. 10 개, 20 개, 심지어 100 개의 도시가 표시된 지도가 있습니다. 모든 도시를 정확히 한 번씩 방문하고 집으로 돌아와야 하지만, 연료와 시간을 절약하기 위해 가능한 한 최단 거리로 이동하고 싶습니다. 이것이 바로 유명한 **외판원 문제 (TSP)**입니다.

문제는 도시가 늘어날수록 가능한 경로의 수가 폭발적으로 증가한다는 점입니다. 마치 우주의 나이보다 더 오래 걸릴 정도로 급격히 커지는 키 더미 속에서 완벽한 열쇠를 찾는 것과 같습니다. 이것이 바로 컴퓨터가 이 문제를 풀기 어려워하는 이유입니다.

이 논문은 **텐서 네트워크 (Tensor Networks)**를 사용하여 이 문제를 해결하는 새로운 방법을 제시합니다. 텐서 네트워크를 컴퓨터 프로그램이 아니라 거대한 다층 필터 시스템으로 생각하세요.

비유: '금가루' 체

거대한 모래주머니에 금가루가 섞여 있다고 상상해 보세요.

• 모래: 모든 나쁘고 길며 비효율적인 경로를 나타냅니다.
• 금: 완벽하고 가장 짧은 경로를 나타냅니다.
• 목표: 모든 입자를 개별적으로 살펴보는 것 없이 금을 모래에서 분리하는 것입니다.

저자들은 이를 수행할 기계 (텐서 네트워크) 를 만들었습니다:

1. 초기 혼합 (중첩): 먼저 기계는 '중첩 (superposition)'을 생성합니다. 마치 모든 가능한 경로의 복사본을 동시에 마법처럼 만들어내는 것과 같습니다. 이는 각기 다른 경로를 따라가는 수백만 개의 자신 버전이 존재하는 것과 같습니다.
2. 가중치 부여 (온도): 다음으로 기계는 '온도' ($\tau$) 를 적용합니다. 이를 열램프로 생각하세요.
   • 길고 비효율적인 경로 (모래) 는 뜨거워져 빛으로 변하며 사라집니다.
   • 짧고 효율적인 경로 (금) 는 차갑고 무겁게 남습니다.
   • 기계는 수학 (볼츠만 인자) 을 사용하여 나쁜 경로가 좋은 경로보다 더 빠르게 사라지도록 만듭니다.
3. 필터 (규칙): 이것이 가장 중요한 부분입니다. 어떤 경로든 될 수는 없습니다; 같은 도시를 두 번 방문할 수 없습니다. 저자들은 특별한 **계수 필터 (Counting Filters)**를 만들었습니다.
   • 각 도시마다 보안 요원이 있다고 상상해 보세요. 여행자가 이미 방문한 도시를 다시 방문하려 하면, 보안 요원은 그 특정 경로의 문을 확 닫습니다.
   • 이러한 필터는 '희소 (sparse)'합니다. 즉, 모든 가능성을 수동으로 확인하지 않고도 잘못된 경로를 차단하는 데 매우 효율적입니다.
4. 결과 (마진): 열과 필터를 통과한 후 기계는 모든 것을 압축합니다. "첫 번째 도시를 볼 때, 승리하는 경로의 일부일 가능성이 가장 높은 도시는 어디인가?"라고 묻습니다. 그 도시를 선택하여 고정하고, 두 번째 도시, 그리고 그 다음 도시로 이 과정을 반복하여 전체 경로를 완성합니다.

그들이 실제로 한 일 (실험)

저자들은 이 방법이 모든 문제를 즉시 해결하는 만능 열쇠라고 주장하지 않았습니다. 그들은 그 한계를 매우 솔직하게 인정했습니다.

• 소규모 테스트: 그들은 작은 지도 (5~12 개 도시) 에서 그들의 방법을 테스트했습니다.
• 보정: 그들은 '온도' 설정 ($\tau$) 이 중요하다는 것을 발견했습니다. 너무 낮으면 나쁜 경로가 충분히 사라지지 않고, 너무 높으면 컴퓨터가 작은 수학 오류에 혼란을 겪습니다. 그들은 각 지도 크기에 따라 이 설정을 신중하게 조정해야 했습니다.
• 결과:
  • 설정을 완벽하게 조정했을 때, 그들의 방법은 이러한 작은 지도에서 약 95% 의 확률로 완벽한 경로를 찾았습니다.
  • 표준 컴퓨터 방법 (예: 'Greedy'또는 'Simulated Annealing') 과 비교했을 때, 그들의 방법은 종종 완벽한 경로를 찾는 데 더 우수했습니다.
  • 그러나 그들은 매우 큰 지도의 경우 수학이 여전히 너무 무거워진다고 (지수적 복잡성) 인정했습니다. 이는 기존 방법과 마찬가지입니다. 이것은 '다항식 시간'의 기적이 아니라, 수학을 수행하는 다른 매우 구조화된 방식일 뿐입니다.

현실 세계 테스트: 직무 재배치 문제

이 이론이 실제 세계에서 작동하는지 확인하기 위해, 그들은 ONCE(스페인의 시각장애인 조직) 를 위한 실제 산업 문제에 이를 적용했습니다.

• 문제: 그들은 작업에 배정된 근로자와 빈 일자리가 있었습니다. 근로자를 새로운 직무로 이동시키는 것이 전체 팀의 생산성을 높일지 확인해야 했습니다.
• 전환점: 이것은 정확히 '이동' 문제가 아니지만 유사합니다: 중복 예약 없이 고유한 사람을 고유한 직무에 배정해야 합니다.
• 결과: 그들은 텐서 네트워크 방법을 양자 어닐러와 디지털 어닐러라는 두 가지 강력한 도구에 비교했습니다.
  • 총 생산성 증가 측면에서 결과는 동일했습니다.
  • 유일한 차이는 두 옵션이 수학적으로 동등한 '동점 해' 상황에서 발생했습니다. 기계들은 단순히 무작위로 다른 옵션을 선택했을 뿐입니다.
  • 결론: 이는 그들의 방법이 실제 세계에서 작동하며 특정 작업에서 전문 도구를 능가하지 않더라도 산업 소프트웨어에 통합될 수 있음을 증명했습니다.

결론

이 논문은 라우팅 및 할당 퍼즐을 해결하기 위한 새로운 수학 도구 세트를 제시합니다.

• 장점: 복잡한 규칙 (예: "같은 도시를 두 번 방문하지 마라") 을 처리하는 매우 명확하고 모듈식 방식을 제공하며, 소규모 문제에서 완벽한 솔루션을 찾을 수 있습니다. 이는 제약 조건을 확인하는 데 지치지 않는 매우 조직적이고 규칙을 준수하는 조력자를 가진 것과 같습니다.
• 단점: 거대한 문제를 마법처럼 쉽게 만들지는 않습니다. 문제가 커질수록 수학은 여전히 지수적으로 더 어려워집니다. 잘 작동하려면 신중한 조정 (보정) 이 필요합니다.
• 교훈: 이는 이러한 문제를 생각하는 강력한 새로운 방식이며 특정 소규모 산업 작업에 대한 견고한 도구이지만, 아직까지 모든 기존 초고속 솔버를 대체할 수는 없습니다.

간단히 말해: 그들은 나쁜 경로를 필터링하고 가장 좋은 경로를 찾을 수 있는 정교한 체를 만들었지만, 금을 얻으려면 여전히 올바른 설정을 입력해야 합니다.

기술 요약

기술적 요약: 외판원 문제 및 변형에 대한 텐서 네트워크 공식화

문제 정의
본 논문은 외판원 문제 (TSP) 와 시간 의존 TSP(TDTSP), 작업 재할당 문제 (JRP), 비반복 제약, 우선순위 규칙, 그룹 제약, 병목 목적 함수를 포함하는 여러 일반화 문제를 다룬다. TSP 는 $N$개의 노드를 정확히 한 번씩 방문하고 출발점으로 돌아오는 최단 경로를 찾는 것으로 정의되며, 이는 알려진 NP-난해 문제이다. Held-Karp($O(N^2 2^N)$) 및 분기 한정법과 같은 정확한 알고리즘이 존재하지만, 지수적 복잡성으로 인해 산업적 규모의 사례에 대한 확장성에 한계가 있다. 반면, 유전 알고리즘, 지역 탐색과 같은 휴리스틱은 최적성 보장이 없는 근사 해를 제공한다. 저자들은 emerging 양자 알고리즘 (QAOA, VQE) 이 현재 하드웨어 잡음 (NISQ 시대) 에 의해 제한받고 있음을 지적하며, 양자 시스템의 특성을 모방하는 고전적 기법의 탐구를 동기부여한다.

방법론
핵심 기여는 후보 경로를 텐서 곱 공간의 상태들로 표현하는 텐서 네트워크 (TN) 공식화이다. 이 방법은 세 가지 주요 메커니즘을 통해 작동한다:

1. 텐서 네트워크 구성:

   • 초기화 ('+'): 각 시간 단계에 대한 모든 가능한 노드 할당의 균일 중첩을 생성한다.
   • 최적화 ('S'): $\tau$를 감쇠 인자, $C(\vec{y})$를 경로 비용으로 하는 허수 시간 진동 연산자 $U = e^{-\tau C(\vec{y})}$를 적용한다. 이는 양자 시스템에서 바닥 상태 (ground state) 를 찾는 것과 유사하게 고비용 구성을 지수적으로 억제한다.
   • 제약 필터링 ('F'): 제약 조건을 강제하기 위해 행렬 곱 연산자 (MPO) 계층을 도입한다. 표준 TSP 의 경우, 이러한 계층은 각 노드가 정확히 한 번 나타나는지 확인하는 카운팅 필터로 작용한다. 이러한 필터는 특정 노드가 방문되었는지 추적하기 위해 이진 결합 지수를 활용하여, 리비 - 치비타 기호 제약 $|\epsilon_{y_0, \dots, y_{\hat{N}-1}}|^2$을 효과적으로 구현한다.
   • 추출 ('+'): 트레이스 계층이 진폭을 합산하여 주변 가중치를 생성한다.

2. 순차적 주변 추출:
   해는 반복적으로 추출된다. 경로의 고정된 접두사에 대해, 알고리즘은 다음 위치의 각 후보 노드 $a$에 대한 주변 가중치 $Z_p(a; \tau)$를 계산한다. $\tau \to \infty$의 극한과 정확한 산술 연산에서, 이 가중치를 최대화하는 노드는 최적 경로의 일부임이 보장된다 (명제 3.2). 알고리즘은 최대화하는 노드를 선택하고 접두사를 업데이트한 후 경로를 완성할 때까지 이를 반복한다.

3. 일반화:
   프레임워크는 필터 및 진동 계층을 수정하여 다양한 TSP 변형에 맞게 조정된다:

   • DNSNN(단계/노드 수 다름): 필터는 노드가 $N^0$에서 $N^f$ 사이로 나타날 수 있도록 허용한다.
   • NMTSP(비마르코프): $K$개의 이전 단계에 의존하는 비용을 처리하기 위해 고차 MPO 를 사용한다.
   • BTSP(병목): 비용 진동을 대신하여 encounter 한 최대 간선 비용을 추적하는 계층으로 대체한다.
   • PTSP(그룹 제약): 필터는 각 클래스당 정확히 하나의 노드를 방문하도록 강제한다.
   • TSPP(우선순위): 로컬 사영 연산자는 필요한 선행 노드가 아직 나타나지 않은 경우 해당 노드를 억제한다.
   • JRP(작업 재할당): "이동 없음" 상태가 반복 가능하고 특정 공석이 고유한 선형 할당 문제로 모델링된다.

4. 근사 및 복잡성:
   전체 텐서 네트워크의 정확한 수축은 지수적이며, 조밀한 계층별 수축의 경우 $O(\hat{N}^4 2^{\hat{N}})$로 확장된다. 더 큰 인스턴스를 처리하기 위해 저자들은 다음을 제안한다:

   • 계층 제거: 복잡성을 줄이기 위해 제약 계층의 부분집합만 적용하여 결과를 휴리스틱으로 취급한다.
   • 희소 - 지역 수축: 지역 필터 텐서의 결정론적이고 희소한 특성을 활용하여 지수적 확장성을 변경하지 않고 다항식 계수를 줄인다 (예: $O(\hat{N}^4 2^{\hat{N}})$에서 $O(\hat{N}^3 2^{\hat{N}})$로).
   • 유한-$\tau$ 휴리스틱: 수치적 대비와 퇴화가 해의 품질에 영향을 미친다는 점을 인정하면서, 유한 정밀도와 유한 $\tau$를 사용하여 영온 (zero-temperature) 극한을 근사한다.

주요 기여

• 명시적 주변 공식: 영온 및 정확한 산술 연산 극한에서 순차적 주변 규칙을 통해 최적 실현 가능 경로를 식별하는 텐서 네트워크 주변 방정식의 유도.
• 제약 인코딩: 다양한 조합 문제에 적용 가능한 (비반복) 카운팅 제약을 위한 MPO 계층 정의.
• 일반화 프레임워크: 특정 텐서 계층을 변경하여 TSP 변형 (TDTSP, JRP, BTSP 등) 에 TN 형식을 적응시키는 모듈식 구성.
• 휴리스틱 구현: 수치적 대비 및 퇴화에 대한 행동 분석과 함께 보정된 휴리스틱으로 기능하는 유한 정밀도, 유한-$\tau$ 구현.

결과
실험적 연구는 특수 솔버에 대한 계산적 우월성을 주장하기보다는 방법의 정확성과 수치적 행동을 검증하기 위해 작은 합성 인스턴스 ($N \in \{5, \dots, 12\}$) 에 초점을 맞춘다.

• 보정: 허수 시간 매개변수 $\tau$는 크기에 의존한다. 보정 스윕 ($\tau \in \{1, \dots, 40\}$) 은 평가 세트에서 최적 해 비율을 $\tau=1$일 때의 55.56% 에서 95.56% 로 크게 향상시켰다.
• 솔버 비교: 작은 인스턴스에서 보정된 TN 솔버는 95.24% 의 최적성 비율을 달성하여 NetworkX 그리디 (26.67%) 와 시뮬레이션 어닐링 (59.05%) 보다 우수했으나, 정확한 Held-Karp 기준 (100%) 에는 미치지 못했다.
• 계층 제거: 제약 계층을 제거하면 해의 품질이 저하되어 고정확도를 위해서는 전체 필터 세트가 필요함을 확인했다.
• 산업 사례 (JRP): ONCE 작업 재할당 문제에 대한 개념 증명에서 TN 방법은 Azure Digital Annealer 와 누적 비용이 동일한 해를 생성했으며, 여러 최적 할당이 존재하는 퇴화 경우에서만 차이가 있었다.

의의 및 주장
저자들은 방법의 계산 능력에 대해 겸손하게 명시한다. 일반 TSP 에 대해 전문화된 고전 솔버 (Held-Karp, 분기 절단, 또는 할당 전용 알고리즘 등) 에 대한 일반적인 계산적 우월성을 주장하지는 않는다.

• 형식적 표현: 이 작업은 "형식적 정확한 산술 연산 지수 시간 표현"이자 "제어된 근사 및 확장을 위한 플랫폼"으로 제시된다.
• 휴리스틱 성격: 유한-$\tau$ 구현은 수치적 대비 및 퇴화에 의존하는 "보정된 유한 정밀도 휴리스틱"으로 특징지어진다.
• 유용성: 주요 가치는 우선순위, 그룹, 비마르코프 비용과 같은 다양한 제약을 체계적으로 통합하고, 통합된 형식 내에서 근사 기법 (계층 제거, 희소 수축) 을 적용할 수 있는 모듈식 텐서 네트워크 프레임워크에 있다.
• 한계: 이 방법은 최악의 경우 지수적 확장성을 유지한다. 수치적 안정성 문제 (언더플로우, 퇴화 경우에서의 대비 손실) 와 크기 의존적 보정의 필요성이 주요 한계로 지적된다.

요약하자면, 본 논문은 TSP 와 그 변형에 대한 엄격한 텐서 네트워크 형식을 제공하여, 작은 인스턴스에서 최적 해를 복원하고 산업적 제약을 통합할 수 있는 능력을 입증하면서도, 문제의 근본적인 지수적 복잡성을 극복하지는 못함을 인정한다.