A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

기술 요약: 길이 제한 사이클 분할 문제(LCCP)를 위한 수치적으로 안전한 분기-가격-및-절단(Branch-Price-and-Cut) 알고리즘

1. 문제 정의

**길이 제한 사이클 분할 문제(Length-Constrained Cycle Partition Problem, LCCP)**는 무방향 그래프 $G=(V, E)$ 상에서 정의된 그래프 최적화 문제이다. 목적은 모든 노드 $i$가 정확히 한 번씩 포함되도록 하는 서로 소인 사이클들로 노드 집합 $부$를 최소한의 개수로 분할하는 것이다.

각 노드 $i$에는 임계 시간 $q_i > 0$이 할당되며, 각 엣지 $\{i, j\}$에는 이동 시간 $t_{i,j} \ge 0$이 있다. 사이클 $C$가 **길이 적합(length-feasible)**하다는 것은 사이클의 총 이동 시간이 해당 사이클에 포함된 모든 노드의 임계 시간보다 작거나 같음을 의미한다:
$$t(C) := \sum_{\{i,j\} \in C} t_{i,j} \le \min_{i \in C} \{q_i\}$$
이 문제는 NP-난해(NP-hard) 문제로 알려져 있으며(TSP로부터 환원 가능), 다항 시간 근사 알고리즘이 존재하지 않는다. 기존의 최첨단 접근 방식들은 밀러-터커-젬린(MTZ) 또는 서브투어 제거 제약(Subtour Elimination Constraints)을 기반으로 한 컴팩트 혼합 정수 계획법(MIP) 정식화를 활용하였으며, 최대 52개의 노드를 가진 인스턴스를 해결할 수 있었다.

2. 방법론

저자들은 집합 분할(Set Partitioning, SP) 정식화에 기반한 정밀한 분기-가격-및-절단(Branch-Price-and-Cut, BPC) 알고리즘을 제안한다.

2.1 집합 분할 정식화

이 문제는 길이 적합한 사이클 전체를 변수로 나타내는 집합 분할 문제로 모델링된다. $\Omega$를 모든 길이 적합한 사이클의 집합이라 하자. 이 정식화는 모든 $i \in V$에 대하여 커버링 제약 조건 $\sum_{C \in \Omega} a^C_i \lambda_C = 1$을 만족하면서 $\sum_{C \in \Omega} \lambda_C$를 최소화한다. $\Omega$의 크기가 지수적으로 커질 수 있으므로, 저자들은 선형 계획법(LP) 완화(relaxation)를 동적으로 해결하기 위해 열 생성(Column Generation) 기법을 사용한다.

2.2 가격 결정 문제 (LCPCCP)

핵심적인 계산 작업은 **길이 제한 보상 수집 사이클 문제(Length-Constrained Prize-Collecting Cycle Problem, LCPCCP)**이며, 이는 음의 축약 비용(negative reduced cost)을 갖는 사이클을 찾는 과정이다. 이 문제는 강한 NP-난해(strongly NP-hard) 문제이다. 저자들은 이를 다음과 같이 해결한다:

• 동적 계획법 (DP): 방문한 노드, 축약 비용, 총 이동 시간, 그리고 경로의 최소 임계 시간을 추적하는 라벨 설정 알고리즘을 사용한다.
• 양방향 탐색 (Bidirectional Search): 그래프의 무방향 특성을 활용하여, 시작 노드 $s$로부터 라벨을 $t(\ell) < q(\ell)/2$까지만 확장한다. 이후 전방 및 후방 탐색에서 얻은 비지배(non-dominated) 라벨들을 병합하여 완전한 사이클을 형성한다. 이는 단방향 탐색에 비해 탐색 공간을 크게 줄여준다.
• 지배 규칙 (Dominance Rules): 특정 노드에서 다른 라벨이 더 낮거나 같은 축약 비용, 더 낮거나 같은 이동 시간, 그리고 방문 노드의 부분 집합을 가지고 있다면 해당 라벨을 제거(pruning)한다.
• ng-완화 (ng-Relaxation): 비원소 사이클(노드를 재방문하는 경우)을 처리하기 위해, 동적 이웃 확장(dynamic neighborhood expansion)을 사용하는 ng-경로 완화 기법을 사용한다. 이는 초기 탐색 단계에서 원소성을 엄격하게 강제하는 복잡성을 피하면서 유효한 하한(lower bound)을 제공한다.
• 탐욕 휴리스틱 (Greedy Heuristic): 음의 듀얼 노드를 제거하거나 양의 듀얼 노드를 삽착하여 개선된 사이클을 찾는 빠른 휴리스틱을 먼저 실행함으로써, 비용이 많이 드는 DP 반복의 필요성을 줄인다.

2.3 구조적 특징 활용

• 삼각 부등식 (Triangle Inequality): 삼각 부등식이 국소적으로 성립하는 노드들에 대해, 저자들은 집합 커버링(set covering) 제약으로 전환한다. 이를 통해 듀얼 변수를 비음수로 제한하여, 가격 결정 과정에서 듀얼 값이 0인 노드를 제거하고 선제적인 프루닝을 가능하게 한다.
• 대칭성 파괴 (Symmetry Breaking): 서로 다른 시작 노드로부터 동일한 사이클이 생성되는 것을 방지하기 위해, 탐색 시 시작 노드의 임계 시간보다 크거나 같은 노드만을 방문하도록 제한한다 (인덱스 타이브레이킹 포함).

2.4 절단 평면 (Cutting Planes)

알고리즘은 두 종류의 절단을 통합한다:

• 부분 집합 행 절단 (Subset Row Cuts, SRCs): 노드들의 부분 집합에 적용되어 해당 노드들을 커버하는 사이클의 수를 제한한다.
• 클리크 절단 (Clique Cuts, CCs): 사이클의 충돌 그래프(conflict graph)를 기반으로 한다.
  저자들은 가격 결정 문제 내에서 이러한 절단들을 준수하는 방식을 조사하였다. 클리크 절단의 경우 복잡성을 피하기 위해 가격 결정 과정에서 무시하는 반면, 부분 집합 행 절단은 라벨에 추가적인 자원(resource)을 부가함으로써 준수하며, 이는 특정 어려운 인스턴스에서 수렴성을 향상시킨다.

2.5 수치적 안전성 (Numerical Safety)

핵심적인 기여 중 하나는 **수치적으로 안전한 경계(numerically safe bounds)**의 구현이다. 부동 소수점 산술은 반올림 오차로 인해 불가능한 듀얼 해를 초래할 수 있다. 저자들은 다음과 같은 듀얼 복구 메커니즘을 제안한다:

1. 부동 소수점 듀얼 값을 큰 정수로 스케일링한다.
2. 정수 산술을 사용하여 듀얼 타당성을 정확하게 검증한다.
3. 만약 타당하지 않다면, 스케일링 계수를 줄이고 다시 시도한다.
   이는 분기 과정에서 사용되는 하한이 수학적으로 엄밀함을 보장하여, 수치적 오류로 인해 알고리즘이 최적성을 잘못 판단하는 것을 방지한다.

2. 6 분기 및 휴리스틱

• 분기 (Branching): 주로 엣지를 솔루션에 포함하거나 제외하는 **엣지 분기(Edge Branching)**를 사용한다. 노드 쌍에 대한 라이언-포스터(Ryan-Foster) 분기도 테스트되었으나, 이 특정 문제 구조에서는 덜 견고한 것으로 나타났다.
• 휴리스틱: 지배 규칙을 완화하여 고품질의 프라이멀 솔루션을 빠르게 찾는 브랜치 앤 프라이스 변형을 사용하며, 이는 정밀 솔버의 웜 스타트(warm start)로 사용된다.

3. 주요 기여

1. 집합 분할 정식화: 집합 분할 기반 접근 방식이 이전의 컴팩트 정식화(평균 루트 갭 30.3%)에 비해 현저히 타이트한 LP 완화(평균 루트 갭 0.4%)를 제공함을 입증하였다.
2. 양방향 DP 가격 결정: 무방향 그래프의 대칭성을 활용하여 탐색 공간을 줄이는 효율적인 양방향 탐색 LCPCCP 가격 결정 알고리즘을 도입하였다.
3. 수치적 안전성: 부동 소수점 솔버와 듀얼 검증을 위한 정밀 정수 산술을 결합하여, 브랜치 앤 프라이스 환경에서 증명 가능한 정확한 하한을 얻는 프레임워크를 제공한다.
4. 알고리즘 통합: 탐욕적 가격 결정, ng-완화, 대칭성 파괴, 그리고 특정 절단 관리를 하나의 응집된 솔버로 결합하였다.

4. 계산 결과

알고리즘은 14개에서 100개의 노드를 가진 84개의 벤치마크 인스턴스를 대상으로 이전의 최첨단 방식인 bnc-sec와 비교 테스트되었다.

• 성능: 제안된 브랜치-가격-및-절단 알고리즘(특히 withsrc+pricing 구성)은 이전 최적 방식이 40개를 해결한 것에 비해 52개의 인스턴스를 최적해까지 해결하였다.
• 규모: 최대 76개의 노드를 가진 인스턴스를 성공적으로 해결하여, 이전의 한계였던 52노드를 넘어 14개의 미해결 인스턴스를 해결하였다.
• 속도: 브랜치 앤 프라이스 코어는 이전 최적 방식보다 평균 14.7배 빠르다.
• 루트 노드 효율성: 해결된 52개 인스턴스 중 49개가 분기 없이 루트 노드에서 해결되었으며, 이는 LP 완화의 강력함을 보여준다.
• 수치적 안전성 오버헤드: 수치적으로 안전한 버전은 안전하지 않은 버전과 동일한 수의 인스턴스를 해결했으나, 속도는 약 40% 느렸다(기하 평균 7.6초 vs 4.5초). 그러나 안전하지 않은 버전에서 잘못된 결과는 발견되지 않았으며, 이 오버헤드는 정확성 보장을 고려할 때 적절한 수준이다.

5. 의의 및 주장

본 논문은 집합 분할 정식화가 성능의 핵심 동력이며, 대부분의 인스턴스를 루트 노드에서 해결할 수 있게 하는 타이트한 경계를 제공한다고 주장한다. 양방향 탐색과 대칭성 파괴가 실행 시간을 줄이는 데 가장 영향력 있는 알고리즘 구성 요소로 식별되었다.

저자들은 이 방법이 최첨단 기술을 크게 개선했음에도 불구하고, 76노드를 초과하는 인스턴스는 여전히 미해결 상태로 남아 있으며 가격 결정 루틴이 여전히 계산상의 병목임을 겸허히 언급하였다. 향후 개선을 위해서는 더 강력한 듀얼 경계나 더 확장 가능한 가격 결정 알고리즘(예: GPU 가속)이 필요할 수 있다고 제안한다. 이 연구는 수치적으로 안전하고 구조를 활용하는 기술을 결과적으로 결합함으로써, 정밀한 방법론이 어떻게 더 크고 복잡한 인스턴스를 처리할 수 있는지 증명하며 LCCP 해결의 새로운 기준을 세웠다.