---
tocdepth: 3
---

# p9 | Multi-Commodity Network Design (MCND)

```{seealso}
This problem is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- We add implicit assumptions that $c_a, f_a, u_a \ge 0$ and $d_k > 0$.
- $d_k > 0$ is necessary to eliminate degenerate cases and argue at least once entering arc to $D_k$ should be active.
- EvoCut arXiv submissions `v1` proposes one inequality used to generate formulation `p9.b`.
- EvoCut arXiv submissions `v2` proposes two inequalities used to generate formulations `p9.c` and `p9.d`.
```


## Description

The Multi-Commodity Network Design (MCND) problem involves selecting a set of network links and assigning multiple flow demands (commodities) at minimal cost. Each commodity must be routed from its source to destination without exceeding link capacities, and activating a link incurs a fixed cost.

## Formulations
### Formulation `a` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850).
```

```{note}
- This is the MILP formulation given in Section F.2 of EvoCut arXiv submissions `v1`. We make one notational change: EvoCut indexes arcs as pairs $(i,j) \in A$; we instead index arcs by a single index $a$ with separate `tail` and `head` arrays, to fit the FormulationBench JSON format.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of network nodes | integer | *scalar* |
| `m` | Number of candidate directed arcs | integer | *scalar* |
| `K` | Number of commodities | integer | *scalar* |
| `tail` | Source node index of each arc | integer | `[m]` |
| `head` | Destination node index of each arc | integer | `[m]` |
| `c` | Unit transportation cost on each arc | continuous | `[m]` |
| `f` | Fixed cost to activate each arc | continuous | `[m]` |
| `u` | Capacity of each arc | continuous | `[m]` |
| `O` | Origin node of each commodity | integer | `[K]` |
| `D` | Destination node of each commodity | integer | `[K]` |
| `d` | Demand of each commodity | continuous | `[K]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `out` | Adjacency list of outgoing arcs for each node | $\delta^+(i) = \{a \in A : \text{tail}(a) = i\} \quad \forall i \in N$ |
| `inc` | Adjacency list of incoming arcs for each node | $\delta^-(i) = \{a \in A : \text{head}(a) = i\} \quad \forall i \in N$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | Flow of commodity k on arc a | continuous | `[m, K]` |
| `y` | 1 if arc a is activated, 0 otherwise | integer | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Unit transportation costs are non-negative. | $c_a \geq 0 \quad \forall a \in A$ | yes |
| Fixed arc activation costs are non-negative. | $f_a \geq 0 \quad \forall a \in A$ | yes |
| Commodity demands are strictly positive. | $d_k > 0 \quad \forall k \in K$ | yes |
| Arc capacities are non-negative. | $u_a \geq 0 \quad \forall a \in A$ | yes |


#### Constraints

- Commodity source outflow equals demand.

  $$ \sum_{a \in \delta^+(O_k)} x_{ak} = d_k \quad \forall k \in K $$

- Commodity sink inflow equals demand.

  $$ \sum_{a \in \delta^-(D_k)} x_{ak} = d_k \quad \forall k \in K $$

- Flow conservation at intermediate nodes: inflow equals outflow for every commodity at every non-source, non-sink node.

  $$ \sum_{a \in \delta^+(i)} x_{ak} - \sum_{a \in \delta^-(i)} x_{ak} = 0 \quad \forall k \in K,\; \forall i \in N \setminus \{O_k, D_k\} $$

- Arc capacity: total flow across all commodities on an arc cannot exceed its capacity times whether it is activated.

  $$ \sum_{k \in K} x_{ak} \leq u_a \, y_a \quad \forall a \in A $$

- Flow variables are non-negative.

  $$ x_{ak} \geq 0 \quad \forall a \in A,\; \forall k \in K $$

- Arc activation variables are binary.

  $$ y_a \in \{0, 1\} \quad \forall a \in A $$

- No outflow from any commodity's destination: commodity k has zero outflow from node D_k. _(implicit)_

  $$ \sum_{a \in \delta^+(D_k)} x_{ak} = 0 \quad \forall k \in K $$

#### Objective

Minimize total flow cost plus fixed arc activation cost.

$$ \min \sum_{a \in A} \sum_{k \in K} c_a \, x_{ak} + \sum_{a \in A} f_a \, y_a $$

### Formulation `b` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 1, name: EC1).
```

```{note}
- For each commodity $k$, the incoming arcs to its destination $D_k$ must together provide enough capacity to deliver demand $d_k$. The inequality is a lifted cover inequality on the activation variables of those incoming arcs.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of network nodes | integer | *scalar* |
| `m` | Number of candidate directed arcs | integer | *scalar* |
| `K` | Number of commodities | integer | *scalar* |
| `tail` | Source node index of each arc | integer | `[m]` |
| `head` | Destination node index of each arc | integer | `[m]` |
| `c` | Unit transportation cost on each arc | continuous | `[m]` |
| `f` | Fixed cost to activate each arc | continuous | `[m]` |
| `u` | Capacity of each arc | continuous | `[m]` |
| `O` | Origin node of each commodity | integer | `[K]` |
| `D` | Destination node of each commodity | integer | `[K]` |
| `d` | Demand of each commodity | continuous | `[K]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `out` | Adjacency list of outgoing arcs for each node | $\delta^+(i) = \{a \in A : \text{tail}(a) = i\} \quad \forall i \in N$ |
| `inc` | Adjacency list of incoming arcs for each node | $\delta^-(i) = \{a \in A : \text{head}(a) = i\} \quad \forall i \in N$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | Flow of commodity k on arc a | continuous | `[m, K]` |
| `y` | 1 if arc a is activated, 0 otherwise | integer | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Unit transportation costs are non-negative. | $c_a \geq 0 \quad \forall a \in A$ | yes |
| Fixed arc activation costs are non-negative. | $f_a \geq 0 \quad \forall a \in A$ | yes |
| Commodity demands are strictly positive. | $d_k > 0 \quad \forall k \in K$ | yes |
| Arc capacities are non-negative. | $u_a \geq 0 \quad \forall a \in A$ | yes |


#### Constraints

- Commodity source outflow equals demand.

  $$ \sum_{a \in \delta^+(O_k)} x_{ak} = d_k \quad \forall k \in K $$

- Commodity sink inflow equals demand.

  $$ \sum_{a \in \delta^-(D_k)} x_{ak} = d_k \quad \forall k \in K $$

- Flow conservation at intermediate nodes: inflow equals outflow for every commodity at every non-source, non-sink node.

  $$ \sum_{a \in \delta^+(i)} x_{ak} - \sum_{a \in \delta^-(i)} x_{ak} = 0 \quad \forall k \in K,\; \forall i \in N \setminus \{O_k, D_k\} $$

- Arc capacity: total flow across all commodities on an arc cannot exceed its capacity times whether it is activated.

  $$ \sum_{k \in K} x_{ak} \leq u_a \, y_a \quad \forall a \in A $$

- Flow variables are non-negative.

  $$ x_{ak} \geq 0 \quad \forall a \in A,\; \forall k \in K $$

- Arc activation variables are binary.

  $$ y_a \in \{0, 1\} \quad \forall a \in A $$

- No outflow from any commodity's destination: commodity k has zero outflow from node D_k. _(implicit)_

  $$ \sum_{a \in \delta^+(D_k)} x_{ak} = 0 \quad \forall k \in K $$

- Destination In-Cut Bound (V1 EC1): for each commodity k, the incoming arcs to its destination, weighted by capacity plus the maximum incoming capacity, must jointly cover the demand plus that maximum.

  $$ \sum_{a \in \delta^-(D_k)} \bigl(u_a + u^{\max}_k\bigr)\,y_a \;\ge\; d_k + u^{\max}_k \qquad \forall k \in K $$

#### Objective

Minimize total flow cost plus fixed arc activation cost.

$$ \min \sum_{a \in A} \sum_{k \in K} c_a \, x_{ak} + \sum_{a \in A} f_a \, y_a $$

### Formulation `c` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC1).
```

```{note}
- For every non-trivial node subset $S$, the activated arcs leaving $S$ must provide enough capacity to carry the total demand $D_B$ of all commodities whose source lies in $S$ and destination outside (each arc's capacity is capped at $D_B$ to lift the inequality).
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of network nodes | integer | *scalar* |
| `m` | Number of candidate directed arcs | integer | *scalar* |
| `K` | Number of commodities | integer | *scalar* |
| `tail` | Source node index of each arc | integer | `[m]` |
| `head` | Destination node index of each arc | integer | `[m]` |
| `c` | Unit transportation cost on each arc | continuous | `[m]` |
| `f` | Fixed cost to activate each arc | continuous | `[m]` |
| `u` | Capacity of each arc | continuous | `[m]` |
| `O` | Origin node of each commodity | integer | `[K]` |
| `D` | Destination node of each commodity | integer | `[K]` |
| `d` | Demand of each commodity | continuous | `[K]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `out` | Adjacency list of outgoing arcs for each node | $\delta^+(i) = \{a \in A : \text{tail}(a) = i\} \quad \forall i \in N$ |
| `inc` | Adjacency list of incoming arcs for each node | $\delta^-(i) = \{a \in A : \text{head}(a) = i\} \quad \forall i \in N$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | Flow of commodity k on arc a | continuous | `[m, K]` |
| `y` | 1 if arc a is activated, 0 otherwise | integer | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Unit transportation costs are non-negative. | $c_a \geq 0 \quad \forall a \in A$ | yes |
| Fixed arc activation costs are non-negative. | $f_a \geq 0 \quad \forall a \in A$ | yes |
| Commodity demands are strictly positive. | $d_k > 0 \quad \forall k \in K$ | yes |
| Arc capacities are non-negative. | $u_a \geq 0 \quad \forall a \in A$ | yes |


#### Constraints

- Commodity source outflow equals demand.

  $$ \sum_{a \in \delta^+(O_k)} x_{ak} = d_k \quad \forall k \in K $$

- Commodity sink inflow equals demand.

  $$ \sum_{a \in \delta^-(D_k)} x_{ak} = d_k \quad \forall k \in K $$

- Flow conservation at intermediate nodes: inflow equals outflow for every commodity at every non-source, non-sink node.

  $$ \sum_{a \in \delta^+(i)} x_{ak} - \sum_{a \in \delta^-(i)} x_{ak} = 0 \quad \forall k \in K,\; \forall i \in N \setminus \{O_k, D_k\} $$

- Arc capacity: total flow across all commodities on an arc cannot exceed its capacity times whether it is activated.

  $$ \sum_{k \in K} x_{ak} \leq u_a \, y_a \quad \forall a \in A $$

- Flow variables are non-negative.

  $$ x_{ak} \geq 0 \quad \forall a \in A,\; \forall k \in K $$

- Arc activation variables are binary.

  $$ y_a \in \{0, 1\} \quad \forall a \in A $$

- No outflow from any commodity's destination: commodity k has zero outflow from node D_k. _(implicit)_

  $$ \sum_{a \in \delta^+(D_k)} x_{ak} = 0 \quad \forall k \in K $$

- Knapsack-Cover Capacity Cut (V2 EC1): for each non-trivial node subset S, the sum of min(u_a, D_B) over arcs leaving S must be at least D_B, where B = K(S) is all commodities crossing S and D_B is their total demand.

  $$ \sum_{a \in \delta^+(S)} \min\{u_a,\,D_B\}\,y_a \;\ge\; D_B \qquad \forall S \subsetneq N,\; S \neq \emptyset,\; B = K(S) $$

#### Objective

Minimize total flow cost plus fixed arc activation cost.

$$ \min \sum_{a \in A} \sum_{k \in K} c_a \, x_{ak} + \sum_{a \in A} f_a \, y_a $$

### Formulation `d` (valid)

```{seealso}
This formulation is sourced from [EvoCut](https://arxiv.org/abs/2508.11850) (version: 2, name: EC2).
```

```{note}
- For every non-trivial node subset $S$, the number of activated arcs leaving $S$ must be at least the minimum count of arcs (chosen greedily by largest capacity) needed to cover the total demand $D_B$ crossing $S$.
```


#### Parameters

| Name | Description | Type | Shape |
|---|---|---|---|
| `n` | Number of network nodes | integer | *scalar* |
| `m` | Number of candidate directed arcs | integer | *scalar* |
| `K` | Number of commodities | integer | *scalar* |
| `tail` | Source node index of each arc | integer | `[m]` |
| `head` | Destination node index of each arc | integer | `[m]` |
| `c` | Unit transportation cost on each arc | continuous | `[m]` |
| `f` | Fixed cost to activate each arc | continuous | `[m]` |
| `u` | Capacity of each arc | continuous | `[m]` |
| `O` | Origin node of each commodity | integer | `[K]` |
| `D` | Destination node of each commodity | integer | `[K]` |
| `d` | Demand of each commodity | continuous | `[K]` |


#### Definitions

| Name | Description | Formulation |
|---|---|---|
| `out` | Adjacency list of outgoing arcs for each node | $\delta^+(i) = \{a \in A : \text{tail}(a) = i\} \quad \forall i \in N$ |
| `inc` | Adjacency list of incoming arcs for each node | $\delta^-(i) = \{a \in A : \text{head}(a) = i\} \quad \forall i \in N$ |


#### Variables

| Name | Description | Type | Shape / Indices |
|---|---|---|---|
| `x` | Flow of commodity k on arc a | continuous | `[m, K]` |
| `y` | 1 if arc a is activated, 0 otherwise | integer | `[m]` |


#### Assumptions

| Description | Formulation | Implicit |
|---|---|---|
| Unit transportation costs are non-negative. | $c_a \geq 0 \quad \forall a \in A$ | yes |
| Fixed arc activation costs are non-negative. | $f_a \geq 0 \quad \forall a \in A$ | yes |
| Commodity demands are strictly positive. | $d_k > 0 \quad \forall k \in K$ | yes |
| Arc capacities are non-negative. | $u_a \geq 0 \quad \forall a \in A$ | yes |


#### Constraints

- Commodity source outflow equals demand.

  $$ \sum_{a \in \delta^+(O_k)} x_{ak} = d_k \quad \forall k \in K $$

- Commodity sink inflow equals demand.

  $$ \sum_{a \in \delta^-(D_k)} x_{ak} = d_k \quad \forall k \in K $$

- Flow conservation at intermediate nodes: inflow equals outflow for every commodity at every non-source, non-sink node.

  $$ \sum_{a \in \delta^+(i)} x_{ak} - \sum_{a \in \delta^-(i)} x_{ak} = 0 \quad \forall k \in K,\; \forall i \in N \setminus \{O_k, D_k\} $$

- Arc capacity: total flow across all commodities on an arc cannot exceed its capacity times whether it is activated.

  $$ \sum_{k \in K} x_{ak} \leq u_a \, y_a \quad \forall a \in A $$

- Flow variables are non-negative.

  $$ x_{ak} \geq 0 \quad \forall a \in A,\; \forall k \in K $$

- Arc activation variables are binary.

  $$ y_a \in \{0, 1\} \quad \forall a \in A $$

- No outflow from any commodity's destination: commodity k has zero outflow from node D_k. _(implicit)_

  $$ \sum_{a \in \delta^+(D_k)} x_{ak} = 0 \quad \forall k \in K $$

- Cardinality Cut (V2 EC2): for each non-trivial node subset S, at least q_{S,B} arcs leaving S must be activated, where q_{S,B} is the fewest arcs (taken by largest capacity first) needed to cover total commodity demand D_B crossing S.

  $$ \sum_{a \in \delta^+(S)} y_a \;\ge\; q_{S,B} \qquad \forall S \subsetneq N,\; S \neq \emptyset,\; B = K(S) $$

#### Objective

Minimize total flow cost plus fixed arc activation cost.

$$ \min \sum_{a \in A} \sum_{k \in K} c_a \, x_{ak} + \sum_{a \in A} f_a \, y_a $$