비용과 병목을 함께 다루는 Min-Cost Max-Flow와 Push-Relabel
Min-Cost Max-Flow와 Push-Relabel의 동작 원리, 잠재치·잔여 그래프 불변식, 물류·트래픽·스케줄링 활용 방식을 정리한다.
2026-08-14 · 최초 발행 2024-04-29
비용 모델과 병목 문제에서 갈리는 유량 알고리즘
흐름 네트워크는 용량 제약 안에서 소스에서 싱크까지 보낼 수 있는 흐름을 찾는 최적화 문제군의 기반이다. 여기에 간선별 비용까지 더하면 단순히 많이 보내는 것만으로는 충분하지 않다. 물류, 통신, 스케줄링처럼 제약과 비용이 한 모델에 겹치는 문제에서는 Min-Cost Max-Flow와 Push-Relabel이 서로 다른 역할을 맡는다.
유향 그래프 (G(V, E))에서 간선 (e=(u, v))는 용량 (cap(e) \ge 0), 비용 (cost(e) \in \mathbb{Z}/\mathbb{R})를 가진다. 유량 (f)는 (0 \le f(e) \le cap(e))와 소스·싱크를 제외한 유량 보존을 만족해야 하며, 조정은 잔여 그래프에서 이뤄진다.
Min-Cost Max-Flow(MCMF)는 최대 유량을 달성하면서 총 비용 (\Sigma_e f(e)\cdot cost(e))를 최소화한다. 대표적인 구현은 Successive Shortest Path(SSP)에 Johnson’s potentials를 결합하는 방식이다. 잠재치로 음수 간선 비용을 제거해 감소 비용을 비음수화한 뒤 Dijkstra를 반복한다.
Push-Relabel(Preflow-Push)은 증가 경로를 직접 찾지 않는다. 국소적인 푸시와 재표기(relabel)로 최대 유량을 계산하며, 프리플로와 높이 함수, 용량 제약을 불변식으로 유지한다. 글로벌 재표기와 갭 히ュー리스틱은 이 과정을 가속하는 데 쓰인다.
잠재치로 최단 경로를 갱신하는 MCMF
처리는 네트워크, 용량, 비용, 소스와 싱크를 입력으로 받아 잠재치 기반 최단 경로 탐색과 잔여 그래프 갱신을 반복하는 방식이다. 결과는 최대 유량과 최소 비용의 쌍으로 얻는다.
음수 사이클이 존재하면 비용이 무한히 감소할 수 있다. 이 경우 제약을 수정하거나 사이클 취소 알고리즘이 필요하다. 비용과 용량의 스케일이 큰 모델에서는 정수 오버플로를 막기 위해 64-bit 처리가 필요하다.
프리플로를 밀어내는 Push-Relabel의 동작
초기에는 소스 높이를 (h(s)=|V|), 나머지 노드의 높이를 (h=0)으로 두고, 소스의 인접 간선으로 가능한 만큼 푸시해 프리플로를 만든다.
이후 넘침 노드에서는 (h(u)=h(v)+1)을 만족하는 간선으로 유량을 푸시한다. 조건을 만족하는 간선이 없으면 해당 노드의 높이를 증가시키는 relabel을 수행한다. 넘침 노드가 모두 사라지면 최대 유량에 도달한다.
글로벌 재표기는 BFS로 거리를 다시 계산하는 방식이며, 갭 히ュー리스틱은 특정 높이 레벨이 비었을 때 그보다 높은 레벨을 무효화한다. 대규모 병목 구간에서는 이런 히ュー리스틱의 적용 여부가 실전 성능에 영향을 준다.
불변식과 자료구조가 구현 품질을 좌우한다
감소 비용과 잠재치는 Johnson 변환으로 잔여 간선의 감소 비용을 비음수화해 Dijkstra를 사용할 수 있게 한다. 잠재치는 (\phi \leftarrow \phi + dist)로 갱신하며 최단 경로의 최적성을 유지한다.
Push-Relabel은 프리플로를 허용해 지역적인 갱신을 수행한다. 높이 함수의 단조 증가 불변식은 종료를 보장하고, 병목 구간 처리에도 강점이 있다.
구현에서는 잔여 그래프를 인접 리스트로 보관하고 역간선 인덱스를 유지한다. MCMF에서는 비용 없는 간선과 비용이 큰 간선이 섞일 때 capacity scaling, cost scaling을 적용할 수 있다. Push-Relabel에서는 Highest-Label, FIFO 큐 선택, 주기적인 글로벌 재표기가 사용된다.
용량과 유량의 비음수성, 잔여 용량의 일관성, 유량 보존은 계속 유지해야 한다. 비용과 용량이 정수라면 정수 해가 보장되며, 음수 사이클이 없다는 전제 아래 최적성 증명도 단순해진다.
| 알고리즘 | 시간복잡도(이론) | 성능(실전) | 확장성 | 일관성/안정성 | 운영 편의 |
|---|---|---|---|---|---|
| Edmonds-Karp | O(VE^2) | 소규모만 적합 | 낮음 | 단순·안정 | 구현 매우 쉬움 |
| Dinic | O(EV) ~ O(E√V) | 범용 우수 | 중간~높음 | 안정 | 구현 보통 |
| Push-Relabel (HLPP) | O(V^3) 이론, 실전 매우 빠름 | 대규모 병목에 강함 | 높음 | 히ュー리스틱 필요 | 구현 중간 |
| Min-Cost Max-Flow (SSP+Potentials) | O(F·E log V) | 비용 모델에서 강력 | 중간 | 음수 사이클 주의 | 구현 중간 |
F는 총 유량 규모 또는 증분 횟수다. 실제 성능은 그래프 구조, 스케일링, 히ュー리스틱 적용에 크게 좌우된다.
제약을 유량 그래프로 옮기는 방식
물류와 운송에서는 다품목 출발지-도착지 운송의 용량, 거리, 통관 비용을 간선 비용으로 모델링해 MCMF로 총 운송비를 최소화할 수 있다. 차선 제한과 허브 통과 제약은 용량 또는 노드 분할로 표현한다.
네트워크 트래픽 엔지니어링에서는 링크 용량에 지연과 패킷 드롭 비용을 반영해 경로를 분산한다. MCMF는 이때 비용을 최소화하는 경로 배분에 쓰이며, 링크 장애가 생기면 잔여 그래프를 다시 계산해 재루팅을 처리할 수 있다.
라이드셰어와 배송의 배차·매칭은 라이더와 주문을 이분 그래프 유량으로 놓고 거리, 시간, 페널티를 비용으로 둔다. MCMF는 이 비용 모델에서 최적 매칭을 구하며, 실시간 증분 업데이트는 롤링 호라이즌 운영에 연결된다.
데이터센터와 클러스터에서는 작업과 서버의 할당을 용량, 에너지, 데이터 이동 비용으로 나타낼 수 있다. MCMF는 TCO를 낮추는 배치에 쓰이고, Push-Relabel 기반 최대 유량으로 선행 배치를 수행한 뒤 비용 미세조정을 결합할 수 있다.
금융 결제 네팅에서는 상호 채무를 유량 네트워크로 표현해 최대 상계와 비용 최소화를 통해 유동성 사용을 최소화한다. 규제 제약은 용량과 필수 경로로 강제한다.
모델에 포함된 기대 효과
경로 분산과 허브 활용을 최적화하는 기준에서 운송·네트워크 비용은 1030% 절감을 기대할 수 있다. Push-Relabel은 대규모 그래프에서 최대 유량 계산 시간을 210배 단축한 사례가 다수다.
잠재치 기반 SSP는 최단 경로의 수치 안정성을 개선하고 경로 진동을 줄인다. 실시간성이 필요한 환경에서는 증분 재계산으로 SLA 준수율을 높이는 방식도 가능하다.
구현 예시: Min-Cost Max-Flow (C++17, SSP+Potentials)
비용과 용량은 비음수이고 음수 사이클이 없다는 전제의 예시다. 필요하면 초기 Bellman-Ford로 잠재치를 설정한다. 환경은 g++ -std=c++17 -O2이며, 64-bit 정수(long long) 사용을 권장한다.
#include <bits/stdc++.h>
using namespace std;
struct MCMF {
struct Edge { int v, rev; long long cap, cost; };
int n, s, t;
vector<vector<Edge>> g;
vector<long long> pot, dist;
vector<int> pv_v, pv_e;
MCMF(int n): n(n), g(n), pot(n), dist(n), pv_v(n), pv_e(n) {}
void add_edge(int u, int v, long long cap, long long cost){
Edge a{v, (int)g[v].size(), cap, cost};
Edge b{u, (int)g[u].size(), 0, -cost};
g[u].push_back(a); g[v].push_back(b);
}
pair<long long,long long> min_cost_max_flow(int S, int T){
s=S; t=T; long long flow=0, cost=0;
fill(pot.begin(), pot.end(), 0); // 필요시 Bellman-Ford로 초기화
while (true) {
// Dijkstra on reduced costs
fill(dist.begin(), dist.end(), LLONG_MAX/4);
dist[s]=0;
priority_queue<pair<long long,int>, vector<pair<long long,int>>, greater<>> pq;
pq.push({0,s});
while(!pq.empty()){
auto [d,u]=pq.top(); pq.pop();
if(d!=dist[u]) continue;
for(int i=0;i<(int)g[u].size();++i){
auto &e=g[u][i];
if(e.cap<=0) continue;
long long rcost = e.cost + pot[u] - pot[e.v];
if(dist[e.v] > d + rcost){
dist[e.v] = d + rcost;
pv_v[e.v]=u; pv_e[e.v]=i;
pq.push({dist[e.v], e.v});
}
}
}
if(dist[t]==LLONG_MAX/4) break; // 더 이상 경로 없음
for(int v=0; v<n; ++v) if(dist[v]<LLONG_MAX/4) pot[v]+=dist[v];
// augment
long long aug=LLONG_MAX;
for(int v=t; v!=s; v=pv_v[v]){
auto &e = g[pv_v[v]][pv_e[v]];
aug = min(aug, e.cap);
}
for(int v=t; v!=s; v=pv_v[v]){
auto &e = g[pv_v[v]][pv_e[v]];
auto &re = g[e.v][e.rev];
e.cap -= aug; re.cap += aug;
cost += aug * e.cost;
}
flow += aug;
}
return {flow, cost};
}
};
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N=4; // 예: s=0, t=3
MCMF mf(N);
mf.add_edge(0,1,5,2);
mf.add_edge(0,2,3,1);
mf.add_edge(1,2,2,0);
mf.add_edge(1,3,3,3);
mf.add_edge(2,3,5,1);
auto [f, c] = mf.min_cost_max_flow(0,3);
cout << f << " " << c << "\n";
return 0;
}매우 큰 비용 스케일에는 정규화나 스케일링을 고려한다. 유량 상한이 작고 비용 구조가 복잡할 때는 SSP가 효과적이며, 유량이 매우 크면 capacity scaling을 결합할 수 있다.