Multi-Commodity Flow: Problem Definition

Introduces the multi-commodity flow (MCF) problem: a network with shared edge capacities through which several commodities, each with its own source, sink, and demand, must be routed simultaneously. Defines bundle (joint capacity) constraints and per-commodity flow conservation, and uses these to verify feasibility of a proposed multi-commodity flow.

Step 1 of 157%

Tutorial

Introduction

In the single-commodity setting, we route one good through a network. The multi-commodity flow (MCF) problem extends this to settings in which several distinct goods, called commodities, must be routed simultaneously through the same network, sharing edge capacities.

An MCF instance is specified by:

A directed graph $G = (V, E)$ .
A capacity $c(e) \geq 0$ for each edge $e \in E$ .
A list of $k$ $k$ commodities. Each commodity $i \in \{1, 2, \ldots, k\}$ $i \in {1, 2, \dots, k}$ is specified by:
- a source $s_i \in V$ ,
- a sink $t_i \in V$ , and
- a demand $d_i \geq 0$ (the amount of commodity $i$ that must be shipped from $s_i$ to $t_i$ ).

A multi-commodity flow is a tuple $(f_1, f_2, \ldots, f_k),$ where each $f_i \colon E \to \mathbb{R}_{\geq 0}$ is a non-negative flow assignment for commodity $i.$ The intent of $f_i$ is to ship $d_i$ units of commodity $i$ from $s_i$ to $t_i.$

For instance, a telecom backbone routing voice traffic between three distinct city pairs has $k = 3$ commodities, where each commodity corresponds to one source-destination pair and its requested bandwidth.