최소 비용 흐름

1. 개요[편집]

최소 비용 흐름 Minimum-cost flow
입력	용량 $c$ · 단위비용 $a$ · 공급/수요 $b$
최적성 조건	잔여망에 음의 비용 순환이 없음 (동치: 감소비용 $\ge 0$)
대표 해법	연속 최단경로(SSP) · 순환 소거 · 비용 스케일링 · 네트워크 심플렉스
정수성	$c, b$ 가 정수면 최적해도 정수 — 접속행렬이 전체 단모듈
특수화	최단경로 · 최대유량 · 수송 · 할당 · 최소비용 이분매칭
강다항	Tardos(1985) 최초 · Orlin(1993) $O(E\log V(E + V\log V))$
별명	조합 최적화의 스위스 아미 나이프

최소 비용 흐름은 용량이 정해진 방향 네트워크에서 각 노드의 공급·수요를 전부 만족시키면서 간선별 단위비용의 총합을 최소화하는 흐름을 찾는 문제다. 네트워크 흐름 문서가 “용량만 있는” 최대유량을 다뤘다면, 여기에 비용 축을 하나 더 얹은 것이 이 문제이고, 그 한 축이 추가되는 순간 최단경로·최대유량·수송·할당·이분매칭이 전부 이것의 특수 사례로 흡수된다.

이 문서의 골자는 두 문장으로 요약된다. 첫째, 최적성 조건이 «잔여망에 음의 비용 순환이 없다»는 국소 조건 하나로 끝난다. 둘째, 그 조건의 쌍대 형태인 감소비용이 존슨 알고리즘의 퍼텐셜과 같은 물건이라, 매 단계 음수 간선을 지우고 다익스트라 알고리즘을 쓸 수 있게 해 준다. 나머지는 이 두 사실을 어떤 순서로 써먹느냐의 차이일 뿐이다.

2. 문제 정의[편집]

방향그래프 $G=(V,E)$ 에 간선 용량 $c(u,v) \ge 0$, 단위비용 $a(u,v) \in \mathbb{R}$, 노드 수급량 $b(v)$($b(v)>0$ 이면 공급, $<0$ 이면 수요, $\sum_v b(v)=0$)가 주어졌을 때

$$\min \sum_{(u,v)\in E} a(u,v)\,f(u,v) \quad\text{s.t.}\quad \sum_{w} f(v,w) - \sum_{u} f(u,v) = b(v)\ \ \forall v, \qquad 0 \le f \le c$$

이 표준형이다. 단일 출발-도착으로 유량 $F$ 를 보내는 흔한 변형은 $b(s)=F$, $b(t)=-F$, 나머지 0 으로 두면 그대로 얻어지고, 반대로 $b \equiv 0$ 인 형태를 최소비용 순환(min-cost circulation)이라 부른다. 둘은 서로 자유롭게 변환된다 — 그래서 이론 논문은 대개 더 대칭적인 순환 형태로 쓴다.

주의할 자명한 함정 하나. 비용이 음수인 간선에 용량이 없으면 답이 $-\infty$ 다. 실제 문제에서 음수 비용이 나온다면(수익을 음수 비용으로 인코딩하는 경우가 흔하다) 용량 상한이 반드시 유한해야 한다.

3. 잔여망과 최적성 조건[편집]

잔여망 $G_f$ 의 정의는 최대유량 때와 같되 비용이 따라붙는다.

$$c_f(u,v) = c(u,v)-f(u,v),\ \ a_f(u,v)=a(u,v); \qquad c_f(v,u) = f(u,v),\ \ a_f(v,u) = -a(u,v)$$

역방향 간선의 비용이 음수라는 것이 이 이론의 모든 것을 결정한다. 이미 보낸 흐름을 되돌리면 그때 낸 비용을 환불받는 셈이니 당연한데, 덕분에 잔여망에는 원래 그래프가 아무리 착해도 반드시 음수 간선이 생긴다. 다익스트라를 그냥 못 쓰는 이유가 이것이다.

음의 순환 정리. 실행가능한 흐름 $f$ 가 최적이다 $\iff$ 잔여망 $G_f$ 에 비용 합이 음수인 유향 순환이 없다.

한 방향은 쉽다 — 음의 순환이 있으면 그 순환을 따라 잔여용량만큼 흘려 비용을 낮출 수 있으니 $f$ 는 최적이 아니다. 반대 방향은 흐름 분해 정리로 간다. 두 실행가능 흐름의 차 $f^{*}-f$ 는 (수급이 같으므로) $G_f$ 위의 순환들로만 분해되고, 그 분해 조각이 $E$ 개 이하다. $f^{*}$ 가 더 싸다면 조각 중 하나는 반드시 음의 비용이어야 한다.

쌍대 형태가 더 쓸모 있다. 노드마다 퍼텐셜 $\pi(v)$ 를 붙이고 감소비용을

$$a^{\pi}(u,v) \;=\; a(u,v) + \pi(u) - \pi(v)$$

로 정의하면, 존슨 알고리즘에서 본 망원합 성질에 의해 순환의 감소비용 합은 원래 비용 합과 같다. 따라서

$f$ 가 최적이다 $\iff$ $G_f$ 의 모든 잔여 간선에서 $a^{\pi}(u,v) \ge 0$ 이 되는 퍼텐셜 $\pi$ 가 존재한다.

이것이 선형계획 쌍대성의 상보 여유 조건을 흐름의 언어로 쓴 것이다. $\pi$ 는 유량 보존 제약에 붙는 쌍대 변수이고, 조건을 풀어 읽으면 “감소비용이 음수인 간선은 이미 포화돼 있고, 양수인 간선은 흐름이 0이며, 흐름이 중간값인 간선은 감소비용이 정확히 0”이 된다. 경제학적으로는 $\pi(v)$ 가 노드 $v$ 에서의 재화 가격이고, 감소비용은 “그 간선으로 운반할 때의 차익”이다. 차익이 남는 간선이 없는 상태가 최적이라는, 시장 균형과 정확히 같은 그림이다.

4. 연속 최단경로법[편집]

가장 널리 쓰이는 정석. 아이디어는 한 줄이다 — 매 단계 «지금 유량에서 최적인 흐름»을 유지하면서 유량을 조금씩 늘린다.

1. $f \leftarrow 0$, 퍼텐셜 $\pi$ 를 초기화한다.
2. 잔여망에서 감소비용 $a^{\pi}$ 를 가중치로 $s \to t$ 최단경로를 찾는다. 없으면 종료(실행불가능).
3. 그 경로의 병목만큼 흘리고, 거리 $d$ 를 써서 $\pi \leftarrow \pi + d$ 로 갱신한다.
4. 요구 유량을 다 보낼 때까지 반복.

핵심 불변식은 “유량 $k$ 짜리 흐름 중 최적인 것” 을 계속 들고 간다는 것이다. 최소비용으로 $k$ 를 보낸 상태에서 최단(비용) 경로로 증대하면 결과가 유량 $k+\delta$ 의 최적해가 된다. 증명은 다시 흐름 분해다 — 더 싼 $k+\delta$ 흐름이 있다면 그 차이가 순환 또는 경로로 쪼개지는데, 순환은 이미 없고 경로는 우리가 고른 것보다 짧을 수 없다.

퍼텐셜 갱신이 이 알고리즘의 심장이다. 3단계의 $\pi \leftarrow \pi + d$ 를 하면 새로 생긴 역방향 간선까지 포함해 감소비용이 다시 전부 비음수가 된다. 최단경로 위의 간선은 감소비용이 정확히 0 이므로, 그 역방향도 0 이기 때문이다. 그래서 벨만-포드는 딱 한 번(초기 퍼텐셜용)만 돌리고, 이후는 전부 다익스트라 알고리즘 이다. 원래 비용이 전부 비음수면 $\pi \equiv 0$ 으로 시작할 수 있어 벨만-포드 알고리즘조차 필요 없다.

복잡도는 증대 횟수 $\times$ 다익스트라 = $O\big(F\,(E + V\log V)\big)$ 로 유사 다항이다. 유량 값이 입력 크기에 들어가므로 $F$ 가 크면 곤란한데, 두 가지 처방이 있다.

• 용량 스케일링(에드먼즈-카프 1972): 큰 자릿수부터 처리해 증대 횟수를 $O(E\log U)$ 로 묶는다. $U$ 는 최대 용량.
• 비용 스케일링($\varepsilon$-최적성, 골드버그-타잔): “감소비용이 $-\varepsilon$ 이상”이라는 완화 조건에서 시작해 $\varepsilon$ 을 반씩 줄인다. 실무 라이브러리에서 가장 빠른 축이고, 밀어내기-재라벨 골격 위에 얹힌다.

5. 순환 소거법[편집]

정반대 전략. 먼저 실행가능한 흐름을 아무거나 만들고(최대유량 한 번), 잔여망에서 음의 순환을 찾아 없애기를 반복한다. 클라인(1967)의 방법이고, 최적성 조건을 그대로 알고리즘으로 만든 것이라 이해가 제일 쉽다.

문제는 아무 음의 순환이나 고르면 반복 횟수가 유량·비용 크기에 좌우된다는 것. 여기서 골드버그와 타잔(1989)의 최소평균 순환 소거가 나온다 — 매번 간선당 평균 비용이 가장 작은 순환을 골라 없애면 반복 횟수가 그래프 크기만의 함수로 묶여 강다항시간이 된다. 최소평균 순환은 카프의 $O(VE)$ 동적계획법으로 찾는다.¹

역사적으로 최초의 강다항 알고리즘은 타르도시(1985)의 것이고, 실용적 균형점은 오를린(1993)의 향상된 용량 스케일링 $O(E\log V(E+V\log V))$ 다. 그리고 2022년, 최대유량·최소비용 흐름 모두를 거의 선형 시간 $m^{1+o(1)}$ 에 푸는 알고리즘이 나왔다 — 내부에서 동적 최소비용 흐름과 $\ell_1$ 형 내점법을 결합하는 물건이라 아직 구현체가 실무를 대체하지는 못했지만, 이론 쪽에서는 이 문제가 사실상 닫혔다고 본다.²

6. 네트워크 심플렉스[편집]

선형계획법의 단체법을 네트워크 구조에 특화시킨 것으로, 대형 문제에서 여전히 최강 축이다. 열쇠는 기저가 곧 신장트리라는 사실이다.

• 간선을 신장트리 $T$ · 하한에 붙은 집합 $L$ · 상한에 붙은 집합 $U$ 로 삼분할한다. 이 $(T,L,U)$ 하나가 기저해 하나다.
• 퍼텐셜은 트리에서 바로 읽는다 — 루트에 $\pi=0$ 을 주고 트리 간선에서 $a^{\pi}=0$ 이 되도록 내려가면 끝. $B^{-1}$ 을 명시적으로 다룰 일이 없다는 것이 이 방법이 빠른 이유다.
• 진입 간선은 감소비용이 음수인($L$ 에 있으면서) 간선, 퇴출 간선은 그 간선이 트리에 만드는 유일한 순환에서 먼저 막히는 간선.

퇴화(degeneracy)가 심하다는 것이 유일한 골칫거리인데 — 네트워크 문제는 퇴화가 예외가 아니라 기본값이다³ — 커닝햄의 강실행가능 트리(strongly feasible tree) 규칙을 쓰면 순환(cycling)이 원리적으로 차단된다. 최악 케이스는 지수지만 실측 성능은 압도적이라, 상용 LP 솔버들이 네트워크 구조를 감지하면 자동으로 이쪽으로 빠진다.

7. 정수성과 환원[편집]

수급량과 용량이 정수면 최적해 중에 정수인 것이 반드시 있다. 이유는 전체 단모듈성 — 방향그래프의 노드-간선 접속행렬이 항상 TU 이므로 LP 완화의 꼭짓점이 전부 정수점이다. 알고리즘 쪽에서 봐도 같다. SSP 는 매 증대량이 정수고, 네트워크 심플렉스의 기저해는 트리에서 정수 연산만으로 결정된다. 정수 제약을 붙이지도 않았는데 정수해가 나오는 이 성질 덕분에 아래의 이산 문제들이 정수계획법 없이 다항시간에 풀린다.

문제	환원 방법
최단경로	용량 무제한, $b(s)=1$, $b(t)=-1$
최대유량	모든 비용 0, $t \to s$ 에 비용 $-1$ · 용량 $\infty$ 를 걸고 순환 최소화
수송 문제	공급지-수요지 이분 네트워크, 중간 노드 없음
할당 문제	수송 문제에서 모든 공급·수요가 1
최소비용 이분매칭	할당 문제와 동일 — 헝가리안 알고리즘이 이것의 SSP 전용 구현
중국 우편배달부	홀수 차수(또는 불균형) 노드를 수급으로 두고 복제 호를 흐름으로

헝가리안 알고리즘과의 관계는 특히 짚고 갈 만하다. 헝가리안의 “라벨”이 정확히 이 문서의 퍼텐셜 $\pi$ 이고, 라벨 갱신이 $\pi \leftarrow \pi + d$ 이며, “타이트한 간선”이 감소비용 0 인 간선이다. 즉 헝가리안은 $n$ 개 단위 흐름에 대한 SSP 를 손으로 특수화한 것이고, 이분 매칭의 증대경로 논증이 그 안에 그대로 들어 있다. 규모가 크거나 구조가 지저분하면 전용 헝가리안을 짜는 대신 범용 최소비용 흐름 솔버를 부르는 편이 낫다는 실무 조언이 여기서 나온다.

이산 최적수송 문제(칸토로비치 형태)도 정확히 수송 문제이므로 같은 도구가 통한다. 다만 그쪽에서는 규모가 커서 엔트로피 정칙화 + 싱크혼 반복으로 넘어가는 것이 표준이 된 지 오래다 — 정확해를 포기하는 대신 GPU 로 밀어붙일 수 있기 때문이다.

8. 볼록 비용으로 넓히기[편집]

간선 비용이 유량에 따라 늘어나는 볼록 비용 $C_e(f_e)$ 는 여전히 다루기 쉽다. 조각별 선형 볼록 함수라면 한 간선을 기울기가 커지는 순서로 여러 개의 평행 간선으로 쪼개면 그만이다. 최적해가 자연히 싼 조각부터 채우므로 순서를 강제할 필요가 없다는 것이 이 트릭의 묘미다. 오목 비용(규모의 경제)에서는 이 논증이 반대로 뒤집혀 무너지고, 문제는 그 자리에서 NP-난해가 된다.

이 확장이 중요한 이유는 그것이 곧 교통 배정이기 때문이다. 링크 통행시간 $c_e(x)$ 가 증가함수일 때 베크만 등(1956)이 보인 대로 사용자 균형은

$$\min_f \ \sum_e \int_0^{f_e} c_e(x)\,dx \quad \text{(유량 보존 · 비음수)}$$

의 해이고, 이것이 정확히 볼록 비용 최소비용 흐름이다. 즉 혼잡 게임의 비원자적 균형을 계산하는 일이 이 문서의 도구 위에 서 있다. 반대 방향의 연결도 있다 — 대칭 네트워크 혼잡 게임의 순수 내시 균형을 다항시간에 찾는 유일하게 알려진 방법이 로젠탈 퍼텐셜을 목적함수로 놓은 (정수) 최소비용 흐름을 푸는 것이다. 비대칭이 되는 순간 그 방법이 깨지고 문제는 PLS-완비가 된다.

9. 구현에서 밟는 지뢰[편집]

• 퍼텐셜 초기화. 원래 비용에 음수가 있으면 $\pi=0$ 으로 시작하면 안 된다. 벨만-포드를 한 번 돌리거나, DAG 면 위상 순서로 한 번 훑는다. 이걸 빼먹으면 첫 다익스트라부터 조용히 틀린 거리를 준다.
• 도달 불가능 노드. 다익스트라 거리가 $\infty$ 인 노드의 $\pi$ 를 그대로 갱신하면 오버플로하거나 이후 감소비용이 음수가 된다. 갱신에서 제외하는 처리를 반드시 넣는다.
• 정수 vs 부동소수점. 감소비용은 뺄셈이 들어가므로 실수 비용에서는 $-10^{-15}$ 같은 값이 나와 다익스트라의 전제가 깨진다. 가능하면 비용을 정수로 스케일링하고, 안 되면 음수를 0 으로 클램프한다.
• 다중 간선. 같은 $(u,v)$ 쌍의 간선이 여럿이면 인접행렬 표현이 무너진다. 잔여망은 처음부터 간선 배열 + 짝수/홀수 인덱스로 역간선 참조 방식으로 짜는 것이 국룰이다(e ^ 1 이 역간선).
• 실행 가능성 먼저. 공급·수요가 있는 형태에서는 흐름이 아예 존재하지 않을 수 있다. 초대형 소스/싱크를 붙여 최대유량을 한 번 돌려 판정하는 것이 표준 전처리다.
• 무엇을 최소화하는지 확정하라. “최소 비용으로 최대 유량”과 “비용이 최소가 되는 지점까지만 흘리기”는 다른 문제다. 후자는 최단경로 비용이 양수로 돌아서는 순간 멈추면 된다. 요구사항에서 이 둘이 섞여 나오는 일이 놀랄 만큼 잦다.

10. 관련 문서[편집]

• 네트워크 흐름 · 최대유량 최소절단 정리 · 중국 우편배달부 문제
• 존슨 알고리즘 · 다익스트라 알고리즘 · 벨만-포드 알고리즘 · 차분 제약 시스템
• 헝가리안 알고리즘 · 이분 매칭 · 수송 문제 · 할당 문제
• 선형계획법 · 심플렉스법 · 쌍대성 · 전체 단모듈성 · 정수계획법
• 최적수송 · 볼록 최적화 · 조합 최적화
• 혼잡 게임 · 군중 시뮬레이션 · 최적설계

11. Footnotes[편집]

1. 카프의 최소평균 순환 알고리즘은 “간선을 정확히 $k$ 개 쓴 최단거리” $d_k(v)$ 를 $k=0..V$ 로 전부 채운 뒤 $\max_k (d_V(v)-d_k(v))/(V-k)$ 의 최솟값을 보는, 뒤통수 맞는 기분이 드는 공식으로 답을 낸다. 처음 보면 왜 저게 평균인지 안 보이고, 두 번 봐도 잘 안 보인다. ↩

2. Chen, Kyng, Liu, Peng, Probst Gutenberg, Sachdeva (2022). 초록의 “almost-linear time” 앞에 붙은 $o(1)$ 지수가 실제로 얼마인지는 논문에서도 명시적으로 안 세는 편인데, 대략 $\exp(O(\log^{c} m))$ 꼴이라 현실 규모에서 상수가 천문학적이다. 이론적 돌파와 실무 코드 사이의 거리를 보여 주는 최근 사례. ↩

3. 트리 간선 중 흐름이 0 이거나 용량에 딱 붙은 것이 하나라도 있으면 그 기저해는 퇴화다. 그런데 수급량이 정수인 네트워크에서는 그런 간선이 안 생기는 쪽이 오히려 이상하다. 그래서 “퇴화는 이론적 예외”라고 배운 사람이 네트워크 심플렉스를 처음 짜면 첫 실행에서 무한 루프를 만난다. 반순환(anti-cycling) 규칙은 장식이 아니다. ↩