🔢 mathematics

A Surface-Based Formulation of the Traveling Salesman Problem

이 논문은 에지 선택 대신 삼각형 집합을 선택하여 경계면이 TSP 경로를 형성하도록 하는 새로운 표면 기반의 정확한 MILP 모델을 제시하며, 이는 서브투어 제거 대신 오일러 특성 제약과 트리 제약을 통해 전역 및 국소 연결성을 보장한다고 요약할 수 있습니다.

원저자: Yılmaz Arslanoğlu

게시일 2026-03-03

📖 3 분 읽기🧠 심층 분석

CC BY 4.0

원저자: Yılmaz Arslanoğlu

원본 논문은 CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/) 라이선스로 제공됩니다. ✨ 이것은 아래 논문에 대한 AI 생성 설명입니다. 저자가 작성하거나 승인한 것이 아닙니다. 기술적 정확성을 위해서는 원본 논문을 참조하세요. 전체 면책 조항 읽기

여행하는 세일즈맨의 새로운 여정: "면"으로 길을 찾다

이 논문은 고전적인 수학 문제인 **여행하는 세일즈맨 문제 (TSP)**를 해결하는 완전히 새로운 방식을 제안합니다. 보통 이 문제는 "어떤 도시를 거쳐야 가장 짧은 길을 갈 수 있을까?"를 **선 (Edge)**으로 생각하지만, 이 연구는 **면 (Surface, 즉 삼각형)**으로 접근합니다.

이 복잡한 아이디어를 일상적인 비유로 쉽게 설명해 드리겠습니다.

1. 기존의 방식: "레고 블록을 이어 붙이기" vs 새로운 방식: " Origami (종이 접기)"

기존의 방식 (선 중심):
전통적인 방법은 도시들 사이를 연결하는 **선 (도로)**을 하나하나 고르는 것입니다. 마치 레고 블록을 하나씩 이어 붙여 원형의 터널을 만드는 것과 같습니다. 문제는 "이 선들이 모두 연결되어 있고, 한 번만 지나가야 한다"는 규칙을 지키기 위해 매우 복잡한 수학적인 장벽 (서브투어 제거 등) 을 세워야 한다는 점입니다.

이 논문의 방식 (면 중심):
이 연구자는 "도로를 그리는 대신, 지도 위에 삼각형 모양의 조각들을 붙여서 하나의 큰 면 (표면) 을 만들어보자"고 제안합니다.

비유: imagine you have a pile of triangular paper pieces. You want to fold them into a specific shape.
핵심 아이디어: 이 삼각형 조각들을 잘게 붙여서 하나의 **연속된 면 (Surface)**을 만듭니다. 그리고 그 면의 **가장자리 (경계)**만 보면, 그것이 바로 세일즈맨이 지나야 할 최적의 여행 경로가 됩니다.

한 줄 요약: "도로를 그리는 게 아니라, 삼각형 조각들을 붙여 '지도'를 만들고, 그 지도의 테두리가 답이 됩니다."

2. 어떻게 작동할까요? "내부 비용은 사라지고, 바깥 길이 남는다"

이 방법의 가장 멋진 점은 수학적 마법과 같은 비용 계산 방식에 있습니다.

상황: 우리가 선택한 삼각형 조각들이 서로 붙어 있다고 칩시다.
내부 선 (Shared Edges): 두 삼각형이 붙어 있는 선은 내부에 있습니다. 이 선은 여행 경로가 아닙니다.
바깥 선 (Boundary): 삼각형 뭉치에서 밖으로 튀어나온 선들만이 여행 경로입니다.

이 연구자는 수학적으로 이렇게 설정했습니다:

삼각형 하나를 고르면 **보상 (이익)**을 줍니다.
선 하나를 고르면 비용을 부과합니다.
하지만 두 삼각형이 붙어 있는 선은 서로의 보상이 상쇄되어 비용이 0이 됩니다.

결과: 내부에 숨겨진 선들은 모두 사라지고, 최종적으로 남는 비용은 오직 '가장자리'의 길이만 됩니다. 즉, 컴퓨터는 "가장자리가 가장 짧은 면"을 찾으면 자동으로 "가장 짧은 여행 경로"를 찾게 되는 것입니다.

3. 왜 삼각형인가? "구멍 없는 도넛 만들기"

단순히 삼각형들을 아무렇게나 붙이면 안 됩니다. 여행 경로는 **하나의 고리 (원)**여야 하므로, 만들어진 면은 구멍이 없어야 합니다.

구멍이 있으면: 여행자가 구멍 안으로 빠지거나, 두 개의 고리가 생길 수 있습니다 (이건 안 됩니다).
이 연구의 해결책: "이 면이 **도넛이 아니라 평평한 접시 (Disk)**처럼 생겼는지"를 수학적으로 검증합니다.
- 전체 연결성: 모든 삼각형 조각이 서로 이어져 있어야 합니다.
- 오일러 특성 (Euler Characteristic): 각 도시 (점) 주변을 둘러싼 삼각형들이 끊어지지 않고 하나의 고리를 이루어야 합니다. "나비 매듭 (Bowtie)"처럼 꼬이거나 구멍이 생기지 않도록 수학적으로 엄격하게 통제합니다.

4. 실제 효과: "정밀한 지도 vs 빠른 나침반"

이 방법은 두 가지 상황에서 쓰입니다.

완벽한 해법 (이론적): 모든 가능한 삼각형 조합을 다 고려하면, 정확한 최적해를 찾을 수 있습니다. 하지만 도시가 조금만 많아져도 계산량이 너무 많아져서 현실적으로 불가능합니다. (모든 길을 다 찾아보는 것과 비슷함)
실용적인 해법 (현실적): 모든 삼각형 대신, **데라네 (Delaunay)**라는 기하학적 규칙에 따라 가장 자연스러운 삼각형들만 골라서 적용합니다.
- 효과: 기존 방법보다 훨씬 빠르고 정확하게 큰 문제를 해결할 수 있습니다. 특히 복잡한 지형이나 데이터가 부족할 때 기존 방법보다 훨씬 강력한 성능을 보여줍니다.

5. 결론: 시선을 바꾸면 문제가 달라진다

이 논문은 **"여행 경로를 직접 그리는 대신, 그 경로를 감싸는 면을 만들어라"**는 발상의 전환을 보여줍니다.

기존: 선을 하나하나 고르며 "연결되었나?"를 걱정했다.
새로운: 면을 붙이며 "구멍이 없나?"를 확인했다.

이는 마치 레고로 성을 짓는 대신, 점토로 성을 빚어서 그 외곽선을 자르는 것과 같습니다. 이 새로운 시각은 복잡한 최적화 문제를 해결할 때, 기존에 없던 강력한 도구와 아이디어를 제공하며, 특히 지도나 공간 데이터가 중요한 분야에서 큰 잠재력을 보여줍니다.

한 마디로: "가장 짧은 길을 찾으려면, 길을 그리는 게 아니라 그 길을 둘러싼 '면'을 만들어보세요!"

논문 요약: TSP 의 표면 기반 공식화 (Surface-Based Formulation)

이 논문은 고전적인 그래프 이론 기반의 TSP(외판원 문제) 접근법을 근본적으로 전환하여, 에지 (간선) 선택 대신 삼각형 집합을 연결하여 2 차원 표면을 구성하는 새로운 혼합 정수 선형 계획법 (MILP) 공식을 제안합니다.

1. 문제 정의 및 기존 접근법의 한계

기존 방식: TSP 는 일반적으로 그래프 $G=(V, E)$ 에서 최소 가중치 해밀턴 순환 (Hamiltonian cycle) 을 찾기 위해 에지 집합을 선택하는 방식으로 모델링됩니다.
한계: 컴팩트한 에지 기반 모델은 국소적인 차수 조건을 만족시키지만, 전역적 연결성 (Global Connectivity) 을 보장하기 위해 지수적인 수의 서브투어 제거 (Subtour Elimination) 제약이나 약한 대체 제약 (MTZ 등) 을 사용해야 합니다. 이는 계산 복잡성을 증가시키고 최적해 탐색을 어렵게 만듭니다.

2. 제안된 방법론: 표면 구성 (Surface-Building Approach)

저자는 순환을 1 차원의 에지 시퀀스가 아닌, **경계가 해밀턴 순환이 되는 2 차원 표면 (Surface)**으로 재정의합니다.

기본 아이디어: 주어진 후보 삼각형 집합 $T$ 에서 연결된 삼각형의 부분집합을 선택하여, 그 결과로 생성된 표면의 **경계 (Boundary)**가 최적의 TSP 경로가 되도록 합니다.
수학적 구조 (Incidence Graph):
- 이분 그래프 (Bipartite Graph): 삼각형 노드 ( $U$ ) 와 에지 노드 ( $W$ ) 로 구성된 이분 그래프를 정의합니다.
- 순수한 목적 함수 (Net Weight): 각 삼각형 선택에 따른 '이익'과 에지 선택에 따른 '비용'을 설정합니다.
  - 내부 에지 (두 삼각형이 공유하는 에지) 는 서로 상쇄되어 비용이 0 이 됩니다.
  - 경계 에지 (표면의 가장자리에 있는 에지) 만이 실제 길이를 기여합니다.
  - 결과적으로 순수 가중치 (Net Weight) 를 최대화하는 것은 경계의 총 길이를 최소화하는 것과 동일합니다.
제약 조건 (Topological Validity):
1. 전역 트리 연결성 (Global Tree Connectivity): 선택된 삼각형과 에지가 하나의 연결된 트리 (Dual Tree) 를 형성해야 합니다. 이는 생성된 표면이 위상적으로 원판 (Disk) 이어야 함을 보장합니다.
2. 카디널리티 (Cardinality): $N$ 개의 정점을 가진 원판 삼각분할을 위해 삼각형 개수는 $N-2$ , 에지 개수는 $2N-3$ 이어야 합니다.
3. 다양체 규칙성 (Manifold Regularity): 각 에지는 최대 2 개의 삼각형과만 인접해야 합니다.
4. 국소 연결성 (Euler Filter): 각 도시 (Vertex) 주변의 인접 삼각형들이 연결되어 있어야 합니다. 이는 오일러 지표 ( $\chi = 1$ ) 를 사용하여 '나비결 (Bowtie)'과 같은 특이점을 방지하고 단일 경로를 보장합니다.

3. 주요 기여 (Contributions)

동치성 증명: 완전 복합체 (Complete Complex, 모든 가능한 삼각형 포함) 에서의 최소 가중치 해밀턴 순환과 이분 인시던스 그래프에서의 최대 가중치 듀얼 트리 (Dual Tree) 간의 동치성을 증명했습니다.
새로운 MILP 공식화: 서브투어 제거 제약 대신 **트리 제약 (Tree Constraint)**과 **오일러 지표 필터 (Euler Characteristic Filter)**를 결합하여 전역 연결성을 보장하는 새로운 공식을 제시했습니다.
입력 독립성: 이 공식은 후보 삼각형 집합 $T$ 를 블랙박스처럼 다룹니다. 완전 집합 ( $K_{All}$ ) 에 적용하면 정확한 해 (Exact) 를 보장하며, 드래네이 (Delaunay) 나 그리디 (Greedy) 같은 희소 삼각분할로 제한하면 효율적인 휴리스틱으로 작동합니다.

4. 실험 결과 및 성능

정확성 검증: $N=10$ 의 비거리적 (Non-metric) 인스턴스나 $N=13$ 의 중첩 육각형 등 다양한 위상적 사례에서 모델이 올바른 표면과 경계를 추출함을 시각적으로 확인했습니다.
성능 비교 (Sparse Inputs):
- Delaunay 삼각분할로 제한된 희소 입력에 대해 기존 Lifted-MTZ 모델과 비교했습니다.
- Surface-Based-Flow 모델 (단일 상품 흐름 기반 트리 제약 사용) 은 berlin52, st70, ch130 등 TSPLIB 인스턴스에서 루트 노드 (Root Node) 에서만 해를 찾거나 (Branch-and-Bound 노드 수 1), 기존 모델보다 훨씬 적은 노드 수로 해를 찾았습니다.
- 예: pcb442 인스턴스에서 Surface-Based-Flow 는 142 개의 노드만 탐색한 반면, Lifted-MTZ 는 23,205 개의 노드를 탐색했습니다.
입력 민감도 분석:
- Tnm199 (난이도 높은 인스턴스): Delaunay 보다 Greedy 삼각분할을 입력으로 사용할 때, Christofides 휴리스틱 (5.69% 갭) 보다 훨씬 우수한 1.85% 의 갭을 달성했습니다. 이는 입력된 기하학적 후보 집합의 질이 해의 질에 직접적인 영향을 미친다는 것을 보여줍니다.
- p100 (병렬선 퇴화): 점들이 병렬선에 분포된 퇴화된 기하 구조에서는 삼각분할 기반의 희소 집합이 실패할 수 있음을 보여주었습니다 (Delaunay: 14.49% 갭, Greedy: 119.63% 갭). 이는 희소화 전략의 한계를 드러냅니다.

5. 의의 및 결론

패러다임 전환: TSP 를 '에지 선택'이 아닌 '표면 구성' 문제로 재정의함으로써, 위상수학적 개념 (Euler characteristic, Disk admissibility) 을 최적화 모델에 직접 통합했습니다.
실용적 가치: 완전한 공간 (모든 삼각형) 에서는 계산적으로 비효율적일 수 있으나, Delaunay 삼각분할과 같은 기하학적 희소 집합을 사용할 때 기존 컴팩트 MILP 모델보다 Branch-and-Bound 탐색 효율이 월등히 높습니다.
미래 전망: 이 접근법은 TSP 해결을 넘어, 추가적인 기하학적 또는 위상적 제약을 기존 에지 기반 모델에 복잡하게 추가하지 않고도 표면 모델에 자연스럽게 통합할 수 있는 강력한 기반을 제공합니다.

이 논문은 TSP 해결을 위한 새로운 수학적 틀을 제시하며, 특히 기하학적 구조를 활용한 희소화 전략과 결합할 때 기존 솔버보다 우수한 성능을 발휘할 수 있음을 입증했습니다.