p9 | Multi-Commodity Network Design (MCND)

See also

This problem is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut.

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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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)

See also

This formulation is sourced from EvoCut (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 \]