Mathematical formulation

Consider a directed graph G with n nodes and m arcs, defined as G=(V,A), where V={1,...,n} denotes the set of n nodes and A={(i₁,j₁),(i₂,j₂),...,(i_m,j_m)} is the set of arcs. The cost of every unit of capacity (MB/s) installed at each arc (i,j) ∈ A is denoted by a_ij, and, for each pair of nodes (h,k) the (unknown) traffic demand from h to k is given by d_hk. Let us introduce a binary flow variable f_ij^hk: this variable is one if demand (h,k) is routed through arc (i,j), zero otherwise, and serves to model the flow of data between each source/destination pair. We also need to introduce the integer variable x_ij, which represents the number of channels of capacity C to be installed in the network. This problem is a particular case of a multi-commodity network flow problems, with the important addition of the uncertain in the traffic demands.

Let us first model the uncertainty set: every uncertain demand d_hk is nonnegative and the total demand leaving or entering a node i is bounded from above by a given parameter:

∀ h ∈ V, ∑_{k∈V: k≠h} d_hk ≤ s_h⁺.

Let us consider now the two main classes of constraints for the problem: conservation of flow for the variables f and the capacity constraints. The former reads as follows: for each node i and each demand (h,k), if i is an intermediate node for this demand, i.e., it is neither h nor k, then the incoming flow must be equal to the outgoing flow, therefore

If i=h, the total balance of flow must be one, hence

∀ i,h,k ∈ V: i=h, ∑_{j: (i,j)∈A}f_ij^hk - ∑_{j: (j,i)∈A}f_ji^hk = 1.

The case for i=k is redundant and its corresponding constraint can be omitted. We can now write the capacity constraint: the total traffic on arc (i,j), weighted by the (unknown) traffic demands, must be less than or equal to the total capacity installed on that arc:

∀ (i,j) ∈ A, ∑_{h ∈ V} ∑_{k ∈ V:k≠h} d_hk f_ij^hk≤ C x_ij.

Finally, the objective function, to be minimized, is

∑_{(i,j)∈ A} a_ijx_ij.