p9 | Multi-Commodity Network Design (MCND)

See also

This problem is sourced from EvoCut [2].

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.

NP-hard: yes

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)

See also

This formulation is sourced from EvoCut [2].

Note

• This is the MCND formulation from v1 of Yazdani et al. [2]. To fit the FormulationBench JSON format, we index arcs by \(a\) with separate tail and head arrays rather than pairs \((i,j) \in A\).

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
There is at least one node.	\(n \geq 1\)	yes
There is at least one arc.	\(m \geq 1\)	yes
There is at least one commodity.	\(K \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 1, name: EC1).

Note

• This is the MCND formulation from v1 of Yazdani et al. [2] augmented with acceleration cut EC1.

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
There is at least one node.	\(n \geq 1\)	yes
There is at least one arc.	\(m \geq 1\)	yes
There is at least one commodity.	\(K \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC1).

Note

• This is the MCND formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC1.

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
There is at least one node.	\(n \geq 1\)	yes
There is at least one arc.	\(m \geq 1\)	yes
There is at least one commodity.	\(K \geq 1\)	yes
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)

See also

This formulation is sourced from EvoCut [2] (version: 2, name: EC2).

Note

• This is the MCND formulation from v2 of Yazdani et al. [2] augmented with acceleration cut EC2.

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
There is at least one node.	\(n \geq 1\)	yes
There is at least one arc.	\(m \geq 1\)	yes
There is at least one commodity.	\(K \geq 1\)	yes
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 \]

Reformulations

Each entry below pairs two formulations of this problem, records whether the second is a reformulation of the first, and gives the parameter map carrying the first formulation’s parameters to the second’s.

a → b (valid)

Note

• Formulation b has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
K	\(K = K\)
tail	\(\text{tail}_{i} = \text{tail}_{i}\)
head	\(\text{head}_{i} = \text{head}_{i}\)
c	\(c_{i} = c_{i}\)
f	\(f_{i} = f_{i}\)
u	\(u_{i} = u_{i}\)
O	\(O_{i} = O_{i}\)
D	\(D_{i} = D_{i}\)
d	\(d_{i} = d_{i}\)

a → c (valid)

Note

• Formulation c has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
K	\(K = K\)
tail	\(\text{tail}_{i} = \text{tail}_{i}\)
head	\(\text{head}_{i} = \text{head}_{i}\)
c	\(c_{i} = c_{i}\)
f	\(f_{i} = f_{i}\)
u	\(u_{i} = u_{i}\)
O	\(O_{i} = O_{i}\)
D	\(D_{i} = D_{i}\)
d	\(d_{i} = d_{i}\)

a → d (valid)

Note

• Formulation d has the same parameters as formulation a; the map is the identity.

Parameter map

Name	Definition in terms of a
n	\(n = n\)
m	\(m = m\)
K	\(K = K\)
tail	\(\text{tail}_{i} = \text{tail}_{i}\)
head	\(\text{head}_{i} = \text{head}_{i}\)
c	\(c_{i} = c_{i}\)
f	\(f_{i} = f_{i}\)
u	\(u_{i} = u_{i}\)
O	\(O_{i} = O_{i}\)
D	\(D_{i} = D_{i}\)
d	\(d_{i} = d_{i}\)