However, when pricing involves the integer variables, the branching rule may compromise the tractability of the pricing process which is otherwise easy when the main LP relaxation is considered. To illustrate this important issue, consider the following nonbifurcated version of the noncompact L-P formulation (18.16):

$\min z$

(18.41a)

$\begin{array}{ll}{\displaystyle \sum _{p\in P_d}{u}_{dp}=1}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.41b)

${\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d}{h}_d{u}_{dp}\le }}\begin{array}{ll}{c}_e+z\hfill & e\in ℰ\hfill \end{array}$

(18.41c)

$\begin{array}{ll}{u}_{dp}\in \left\{0,1\right\}\hfill & d\in \mathcal{D},p\hfill \end{array}\in P_d.$

(18.41d)

with a hop-limit imposed on the paths in $\mathcal{P}$. Note that this time (18.41) has its compact N-L counterpart (see the remark after formulation (18.8) in Subsection 18.2.2). Still, the N-L formulation provides a worse lower bound than the LP relaxation of (18.41), since the former actually admits paths longer than the hoplimit (think why).

As discussed in [53], path generation in the BB nodes generated for this problem imposes a difficulty. If we were to use BB directly for the L-P formulation (18.41), i.e., if we were to branch on variables u_dp, then setting a particular path flow u_dp to 0 would require that path p ∈ $\mathcal{P}$_d is not used in the current BB solution. Still, this path can appear to be the shortest path generated as the result of solving the pricing problem. In such a case we would have to generate the second shortest path. Now, imagine that there are many u_dp for a demand d set to 0, say there are L such paths. Then we could in general have to generate L +1 shortest paths for this demand to obtain a new path to be added to the current path-list $\mathcal{P}$_d. Since generation of L shortest paths is $\mathcal{N}$$\mathcal{P}$-hard (with increasing L), path generation may become excessively time consuming.

Instead of branching on variables u_dp we could branch on binary variables x_ed, i.e., on link flows, where

$\begin{array}{ll}{x}_{ed}={\displaystyle \sum _{p\in P_{ed}}{u}_{dp},}\hfill & e\in ℰ,d\hfill \end{array}\in \mathcal{D}$

(18.42)

after adding equations (18.42) to the MIP formulation. Now, fixing x_ed to 0 makes no problem – we just forbid to use link e when we look for a shortest paths of demand d. Still, setting x_ed to 1 for a subset of links creates a difficulty because it is $\mathcal{N}$$\mathcal{P}$-hard to find a shortest path that must traverse a given set of links.

To resolve this issue, we use a specialized branching scheme due to [53]. We add equations (18.42) to formulation (18.41) and define the branching rule as follows. If the vector (x_ed, e ∈ ℰ, d ∈ $\mathcal{D}$) in the current BB node is not integral, we select a demand d ∈ $\mathcal{D}$ and a node v ∈ $\mathcal{V}$ with two fractional flows $x_{e_1}{}_d$ and $x_{e_2}{}_d$ for some links e₁,e₂ ∈ δ⁺(v) outgoing from node v (observe that such pair (d, v) exists). Then we divide the set δ⁺(v) into two subsets $\mathcal{A}$₁(v) and $\mathcal{A}$₂(v) so that e₁ ∈ $\mathcal{A}$₁(v) and e₂ ∈ $\mathcal{A}$₂(v), and branch by creating two new BB nodes, one with additional constraint ${\displaystyle {\sum }_{e\in {\mathcal{A}}_1\left(v\right)}{x}_{ed}=0}$, and the other with additional constraint ${\displaystyle {\sum }_{e\in {\mathcal{A}}_2\left(v\right)}{x}_{ed}=0}$, added to the LP subproblem of the current BB node. In this way we eliminate the bifurcation of the flow of demand d on links e₁ and e₂ in the BB subtree below the current BB node. Note that in any feasible (i.e., binary) solution of the single-path allocation problem, the path selected for demand d either traverses node v ∈ $\mathcal{V}$ or does not. If it does, it must also traverse one of the links outgoing from v (except for the end node t(d)). Obviously, this link will belong to exactly one of the sets $\mathcal{A}$₁(v), $\mathcal{A}$₂(v), say to set $\mathcal{A}$₁(v). Then, all link-flow variables assigned to the links belonging to the other set must be equal to 0: ${\displaystyle {\sum }_{e\in {\mathcal{A}}_2\left(v\right)}{x}_{ed}=0}$. This simple observation justifies the branching procedure. Namely, we require that at each BB node only variables x_ed associated with one of the two sets can obtain non-zero values.

For this particular branching rule, the pricing problem is easy since we do not force using particular subsets of links by the demand paths, we only force subsets of links not be used. When looking for a shortest path with respect to dual variables π* corresponding to constraints (18.41c), we can use the standard Dijkstra algorithm. Since we know which links outgoing from the nodes cannot be used for selecting the shortest paths for a demand, we simply delete these links from the graph while searching for a shortest path. Certainly, after the LP subproblem of a BB node is solved by PG, the new paths found during the process are added to the path lists $\mathcal{P}$_d, d ∈ $\mathcal{D}$ of the LP subproblem of the node (and new variables u_dp are added to constraints (18.41b)–(18.41d) and (18.42)).

Certainly, BP and BC can be combined in one scheme called branch-and-price-and-cut (BPC). This approach was for example applied in [53] using the lifted-cover knapsack inequalities [54].

18.3.3    Heuristic Approaches

The role of heuristics in network design is two-fold. In the context of the exact methods discussed above, heuristic methods can help to find good upper bound (sometimes even near-optimal) solutions of the MIP in hand. Besides, the heuristics can serve just as a means of finding a reasonable engineering solution in a short time and, what can be important, using simple to understand and implement algorithms. Looking at the literature of NDP, we may notice that most of the heuristic approaches applied to particular problems are either derived from some general approaches to combinatorial optimization called meta-heuristics or some ad-hoc problem-dependent (specialized) heuristic algorithms.

Stochastic Meta-heuristics

Consider a combinatorial optimization problem

$\underset{x\in X}{\min }F\left(x\right)$

(18.43)

where X is a finite set and F : X ↦ ℝ₊. Roughly speaking, stochastic metaheuristics can be viewed as local search methods for (18.43), extended with a mechanism for leaving the local minima at the expense of temporary increase of the cost function. There are several such methods used, including simulated annealing (SAN), evolutionary algorithm (EA), simulated allocation (SAL) or tabu search (TS). These methods are quite popular and are summarized in many handbooks, in the context of NDP for example in [2, 3].

Probably the oldest (at least among the commonly known methods) general stochastic heuristic method is called simulated annealing [55, 56, 57]. In SAN, having the current solution x ∈ X, we pick up a solution y ∈ X in its neighborhood at random and proceed to y (x := y) when F (y) ≤ F (x). However, when F (y) > F (x), we accept the move to y (x := y) with probability equal to $e\frac{-\Delta F}{T}$ (where ΔF = F(y) − F (x) – this is the so-called Metropolis test). Once L steps of this kind are performed, the “temperature” parameter T is decreased and the search of the best solution in the optimization space X continued. A typical temperature reduction is T := τT, for some parameter τ from interval (0,1), e.g., τ = 0.99. Note that for a fixed ΔF, the acceptance probability, decreases with T, so in the consecutive execution of the inner loop the uphill moves are more and more rare. The stopping criterion can be, for instance, the lack of significant improvement of the objective function.

An application of SAN requires first of all a proper specification of the neighborhood N(x). To illustrate this point consider for example the nonbifurcated flow allocation problem:

$FAP/SP\left(L-P\right):\min z$

(18.44a)

$\begin{array}{ll}{\displaystyle \sum _{p\in P_d}{u}_{dp}=1}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.44b)

${\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d}{h}_d{u}_{dp}\le c_e+z}}\begin{array}{ll}\hfill & e\in ℰ\hfill \end{array}$

(18.44c)

$\begin{array}{ll}{u}_{dp}\in \left\{0,1\right\}\hfill & d\in \mathcal{D},p\in P_d.\hfill \end{array}$

(18.44d)

The set X is the set of all feasible routing vectors u and F(u) = z. The neighborhood of flow pattern u ∈ X would be the set $\mathcal{N}$(u) of flow patterns u′ differing from u for exactly one demand:

$u^{\prime }\in \mathcal{N}\left(u\right)\iff \exists d^{\prime }\in \mathcal{D},{u^{\prime }}_{dp}=u_{dp},d\in \mathcal{D}\left\{d^{\prime }\right\},p\in P_d.$

(18.45)

Another popular algorithms are evolutionary algorithm (see [58, 59, 60]), tabu search (see [3, 61, 62]), and simulated allocation (see [2, 63, 64]).

Feasibility Pump and Randomized Rounding

A straightforward general heuristic, different from the stochastic meta-heuristics described above is called “feasibility pump” (FP). FP is intended for finding feasible solutions of MIPs and was proposed by Fischetti et al. in [65]. The idea of FP is explained below for pure binary programs (an extension to mixed-binary programs is straightforward).

Let X^BP ⊆ {0,1}ⁿ denote the set of feasible solutions of a BP problem, i.e., an IP problem (18.23) with binary x, and let P^LP be the solution polyhedron of the LP relaxation of the BP. Suppose we are interested in finding any feasible solution x ∈ X^BP. To do this, we first find a solution x* ∈ P^LP of the LP relaxation, and then round off variables x*₁, x₂,…,x*_n to binary values. Denote such a rounded-off vector x* by [x*] = ([x*]₁, [x*]₂,…, [x*]_n). If [x*] ∈ X^BP then we are done. Otherwise we solve the following LP:

$\min {\displaystyle \sum _{i\in I_0}{x}_i}+{\displaystyle \sum _{i\in I_1}\left(1-x_i\right)}$

(18.46a)

$Ax\le b$

(18.46b)

$0\le x_i\le 1,i=1,2,\dots ,n$

(18.46c)

where I₀ = {i : 1 ≤ i ≤ n, [x*]_i = 0} and I₁ = {i : 1 ≤ i ≤ n, [x*]_i = 1}. Note that in effect we are finding a point x ∈ P^LP that minimizes the distance form the current point [x*] ∈ {0,1}ⁿ. Now we denote the solution of problem (18.46) by x^* and repeat the above procedure. Certainly, we should try to apply a smart rounding-off (e.g., involving randomness) in order to avoid cycling. Still, in general, we are not guaranteed that the procedure will converge to a [x*] ∈ X^BP.

In NDP, the feasibility pump approach is potentially well suited to problems like the pure flow allocation problem FAP/SP (see (18.7) or (18.8)) since in this problem we may skip the objective function when a feasible solution [x*] ∈ X^BP is just what we are looking for. Finally, let us note that if the considered problem does have an objective function f (x) (like (18.7)) we may add constraint f (x) ≤ f * to the LP problem (18.46), where f * is related to the lower bound of (18.7) (e.g., reasonably bigger than the lower bound), and in this way try to obtain a suboptimal feasible solution.

In branch-and-bound it is important to systematically compute good upper bounds for the optimal solutions in the nodes of the BB tree. One such approach is called “randomized rounding” and was proposed by P. Raghavan and C. Thompson in [66]. Randomized rounding is a probabilistic method in the sense that the procedure yields random approximate solutions of a 0-1 integer problem.

Randomized rounding applied to linear relaxations of the link-path formulation (18.7) of the single-path allocation problems goes like this. For each demand d ∈ $\mathcal{D}$ the current demand volume distribution (x_dp, p = 1, 2,…, $\mathcal{P}$_d) is treated as a probability distribution (as ${\displaystyle {\sum }_{p\in {\mathcal{P}}_d}{x}_{dp}}=1,x_{dp}\ge 0$), and this distribution is used to draw exactly one path to be used to carry the whole demand volume h_d: Prob{x_dp′ = 1; x_dp = 0,p = 1, 2,…, $\mathcal{P}$_d, p ≠ p′} = x_dp′ p′ = 1, 2,…, $\mathcal{P}$_d. For any of the formulations with soft capacity constraints (i.e., for formulations like (18.16)) any such drawing will yield a feasible solution. As explained in [66], if for each BB node the drawing is repeated sufficiently many times, we may get good upper bounds.

18.4    Optimization Models for Multistate Networks

This section is devoted to optimization models of multistate networks. The presentation is concentrated on network design problems taking into consideration network survivability, i.e., robustness to failures. In particular, we consider problems related to protection and restoration mechanisms that can be used in survivable networks. On top of survivability, in the last part of this section, we briefly discuss models reflecting nonsimultaneous traffic matrices scenarios. Below we assume that, if not stated explicitly otherwise, all elementary paths are admissible for traffic demands.

18.4.1    Protection Models

Conceptually, the simplest way of protecting traffic against failing network components is by over-provisioning. The corresponding protection mechanisms are passive (static), and protect demands by realizing redundant (with respect to normal demand h_d , d ∈ $\mathcal{D}$) flows, out of which a sufficient subset survives any of the assumed failure states. Consider a network $\mathcal{N}$ ($\mathcal{G}$, $\mathcal{D}$) and a failure scenario $\mathcal{S}$ (see Subsection 18.2.1).

Path Diversity

The protection concept based on path diversity (PD) follows the idea of overprovisioning by routing more demand volume than the specified values h_d, d ∈ $\mathcal{D}$ in the normal failure-less state s = ∅, and assuring that at least a specified fraction of the normal flow survives each failure situation s in the considered failure scenario $\mathcal{S}$. We note that several path diversity protection concepts similar to the one discussed below can be found in the literature, for example diversification [38] and its generalization demand-wise shared protection (DSP) [67, 68, 69].

The PD network design problem is given by the following noncompact linear programming formulation.

$PD\left(L-P\right):\min F\left(y\right){\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.47a)

$\begin{array}{ll}\left[{\text{λ}}_d^s\right]{\displaystyle \sum _{p\in P_d^s}{x}_{dp}\ge h_d^s}\hfill & d\in \mathcal{D},s\in \mathcal{S}\hfill \end{array}$

(18.47b)

$\begin{array}{ll}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{x}_{dp}\le y_e}}\hfill & e\in ℰ\hfill \end{array}$

(18.47c)

$\begin{array}{ll}{x}_{dp}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\in P_d\hfill \end{array}$

(18.47d)

$\begin{array}{ll}{y}_e\in ℝ\hfill & e\in ℰ.\hfill \end{array}$

(18.47e)

In essence, the formulation simply states that for each demand a sufficient portion of flow must survive in every network state (recall that ${\mathcal{P}}_d^s$ is the set of admissible paths of demand d ∈ $\mathcal{D}$ that survive in state s ∈ $\mathcal{S}$). If any of the end-nodes of some demand d ∈ D fails in state s ∈ S we assume $h_d^s=0$ because otherwise the problem becomes infeasible due to ${\mathcal{P}}_d^s=\varnothing$. The symbol ${\text{λ}}_d^s$ in brackets to the left of constraint (18.47b) denotes the corresponding dual variable which will be used in the problem dual to PD(L-P). Notice that with continuous capacity variables y_e , as assumed in (18.47), each inequality in (18.47c) could be turned into an equation, and then the problem would decompose into a set of separate subproblems for each demand d ∈ $\mathcal{D}$:

$\min F\left(x\right)={\displaystyle \sum _{p\in P_d}\left({\displaystyle \sum _{e\in p}{\xi }_e}\right)}{x}_p$

(18.48a)

$\begin{array}{ll}\left[{\text{λ}}^s\right]{\displaystyle \sum _{p\in P_d^s}{x}_p\ge h_d^s}\hfill & s\in \mathcal{S}\hfill \end{array}$

(18.48b)

$x_p\in {ℝ}_{+}p\in P_d.$

(18.48c)

Nevertheless, we keep the problem in form (18.47) because the decomposition does not apply to other protection/restoration mechanisms discussed in this section, or when extensions, as for example modular link capacity, are considered.

In fact, as shown by the following N-L formulation, problem (18.47) is polynomial for the single link failure scenario, and $\mathcal{N}$$\mathcal{P}$-hard for multiple link failure scenarios (the last statement is proven in [70]).

$PD\left(N-L\right):\min F\left(x\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.49a)

${\displaystyle \sum _{e\in {\delta }^{+}\left(s-d\right)}{x}_{ed}-}{\displaystyle \sum _{e\in {\delta }^{-}\left(s\left(d\right)\right)}{x}_{ed}=X_d}d\in \mathcal{D}$

(18.49b)

${\displaystyle \sum _{e\in {\delta }^{+}\left(v\right)}{x}_{ed}-}{\displaystyle \sum _{e\in {\delta }^{-}\left(v\right)}{x}_{ed}=0}d\in \mathcal{D},v\in \mathcal{V}\left\{s\left(d\right),t\left(d\right)\right\}$

(18.49c)

${\displaystyle \sum _{d\in \mathcal{D}}{x}_{ed}}\le y_{e}e\in ℰ$

(18.49d)

$X_d-x_{ed}\ge h_d^{s}d\in \mathcal{D},\left\{e\right\}\in \mathcal{S}$

(18.49e)

$x_{ed}\in {ℝ}_{+}e\in ℰ,d\in \mathcal{D}$

(18.49f)

$x_d\in ℝd\in \mathcal{D}.$

(18.49g)

Following [71] we now derive the pricing problem for PD(L-P). To do that, we will first derive the dual to (18.47). Certainly, for this we could apply standard formulas for the LP dual that can be found in any handbook on linear programming (see Section 15.1.4 in Chapter 15, and for example [15, 18, 19]). However, in this particular case we will derive the dual from scratch to illustrate the technique for the readers who are not familiar with dualization. In our derivation, analogously to (18.48), we get rid of constraint (18.47c) by substituting ${\displaystyle {\sum }_{d\in \mathcal{D}}{\displaystyle {\sum }_{p\in {\mathcal{P}}_{ed}}{x}_{dp}}}$ for y_e in the objective function (18.47a). Then we form the Lagrangean function L(x; λ) by dualizing constraints (18.47c) using dual variables $\text{λ}=\left({\text{λ}}_d^s\ge 0:d\in \mathcal{D},s\in \mathcal{S}\right)$:

$ℒ\left(x;\text{λ}\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e\left({\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{x}_{dp}}}\right)}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{\text{λ}}_d^s}\left(h_d^s-{\displaystyle \sum _{p\in P_d^s}{x}_{dp}}\right)}.$

(18.50)

The dual function W(λ) is defined as

$W\left(\text{λ}\right)=\underset{x\ge 0}{\min }ℒ\left(x;\text{λ}\right)$

(18.51)

and to express this function for a given λ ≥ 0 we transform 18.50 into a suitable form with the primal variables separated as follows:

$ℒ\left(x;\text{λ}\right)={\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{h}_d^s{\text{λ}}_d^s}}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d}\left({\displaystyle \sum _{e\in P}{\xi }_e}-{\displaystyle \sum _{s\in {\mathcal{S}}_p}{\text{λ}}_d^s}\right)}}{x}_{dp}.$

(18.52)

Then we easily see that

$W\left(\text{λ}\right)={\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{h}_d^s{\text{λ}}_d^s}}$

when

${\displaystyle \sum _{s\in {\mathcal{S}}_p}{\text{λ}}_d^s}\le {\displaystyle \sum _{s\in p}{\xi }_e}$

for all d ∈ $\mathcal{D}$ and p ∈ $\mathcal{P}$_d, and W(λ) = −∞ otherwise. Hence the dual problem is given by

$\max \left\{{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{h}_d^s{\text{λ}}_d^s:\text{λ}}}\ge {\displaystyle \sum _{s\in {\mathcal{S}}_p}{\text{λ}}_d^s\le }{\displaystyle \sum _{e\in p}{\xi }_e,d\in \mathcal{D},p\in P_d}\right\}.$

(18.53)

Note that problem (18.53) is always feasible (λ = 0 is a feasible solution). Introducing auxiliary dual variables Λ_d, d ∈ $\mathcal{D}$ we obtain a more handy form of the dual:

$PD\left(L-P\right)-D:\max W\left(\text{λ}\right)={\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{h}_d^s}{\text{λ}}_d^s}$

(18.54a)

$\begin{array}{ll}{\text{Λ}}_d={\displaystyle \sum _{s\in \mathcal{S}}{\text{λ}}_d^s}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.54b)

$\begin{array}{ll}{\text{Λ}}_d\le {\displaystyle \sum _{e\in p}{\xi }_e+}{\displaystyle \sum _{s\in {\mathcal{S}}_p}{\text{λ}}_d^s}\hfill & d\in \mathcal{D}\hfill \end{array},p\in P_d$

(18.54c)

$\begin{array}{ll}{\text{λ}}_d^s\in {ℝ}_{+}\hfill & d\in \mathcal{D}\hfill \end{array},s\in \mathcal{S}.$

(18.54d)

Given an optimal dual solution λ* with respect to the current set of admissible paths, the goal of the pricing problem for demand d ∈ $\mathcal{D}$ is to find a new path p(d) outside the current list of admissible paths $\mathcal{P}$_d which violates the dual constraint (18.54c), i.e., which satisfies

${\displaystyle \sum _{e\in p}{\xi }_e+}{\displaystyle \sum _{e\in {\overline{\mathcal{S}}}_p}{\text{λ}}_d^{s*}<{\text{Λ}}_d^{*}.}$

(18.55)

As explained in Subsection 18.3.1, if added to the list of admissible paths of the current formulation of PD(L-P), such a path p(d) may improve the primal objective function. Hence, using the pricing problem (18.55) in Step 2, we can solve problem (18.47) using Algorithm PG given in Subsection 18.3.1.

Under a single link failure scenario $\mathcal{S}$ ⊆ {{e} : e ∈ ℰ}∪{∅}, the pricing problem for PD(L-P) can be solved in polynomial time, as observed in [12, 68]. To see this, note that with single link failures only, condition (18.55) can be rewritten as follows:

${\displaystyle \sum _{e\in p}\left({\xi }_e+{\text{λ}}_d^{e*}\right)}<{\text{Λ}}_d^{*}$

(18.56)

where ${\text{λ}}_d^{e*}=0$ if {e} ∉ $\mathcal{S}$. The right-hand side of (18.56) depends only on the demand, and the link weights on the left-hand side are non-negative. Hence, for each demand d ∈ $\mathcal{D}$, violation of the dual constraint (18.54c) can be tested by searching for a shortest path p(d) between the end-nodes of d with respect to the demand-dependent non-negative link weights ${\gamma }_e\left(d\right)={\xi }_e+{\text{λ}}_d^{e*}$ using for example the Dijkstra algorithm, and comparing its length to the value of Λ*_d. If the shortest path p(d) fulfills condition (18.56), then adding path p(d) to $\mathcal{P}$_d (and thus the corresponding constraint ${\text{Λ}}_d\le {\displaystyle {\sum }_{e\in p\left(d\right)}\left({\xi }_e+{\text{λ}}_d^{\left\{e\right\}}\right)}$ to the dual formulation (18.54) can potentially improve the primal objective value. Otherwise, no path for this demand violates the dual constraints for the current set of optimal dual variables.

As already mentioned, PD is $\mathcal{N}$$\mathcal{P}$-hard for multiple link failure scenarios (recall a set s of links failing together is called the shared risk link group, SRLG, see [72]). This in particular means that then the pricing problem must also be $\mathcal{N}$$\mathcal{P}$-hard (see Subsection 18.3.2 and [27]). In this case the pricing problem for a directed graph can be written as the following MIP:

$\min {\displaystyle \sum _{e\in ℰ}{\xi }_e{\displaystyle \sum _{s\in \mathcal{S}}{\text{λ}}_d^{s*}{Y}^s}}$

(18.57a)

${\displaystyle \sum _{e\in {\delta }^{+}\left(v\right)}{x}_e-}{\displaystyle \sum _{e\in {\delta }^{-}\left(v\right)}{x}_e=}\{\begin{array}{ll}\hfill 0,& v\in \mathcal{V}\left\{s\left(d\right),t\left(d\right)\right\}\hfill \\ \hfill 1,& v=s\left(d\right)\hfill \\ \hfill -1,& v=t\left(d\right)\hfill \end{array}$

(18.57b)

$\begin{array}{ll}{x}_e\le Y^s\le 1\hfill & s\in \mathcal{S},e\in s\hfill \end{array}$

(18.57c)

$\begin{array}{ll}{x}_e\in \left\{0,1\right\}\hfill & e\in ℰ.\hfill \end{array}$

(18.57d)

An analogous formulation can be written for the undirected case by modifying formulation (18.57) according to (18.3) (see [71]).

Let (x*,Y*) be an optimal solution of (18.57). Then constraints (18.57b) together with the binary requirement (18.57d) will ensure that the flows x*_e equal to 1 specify a directed single-path flow of value 1 from s(d) to t(d). Finally, variables Y^s* (identifying the failure states in which the so-specified flow fails) will also be binary when this matters (i.e., when ${\text{λ}}_d^{s*}>0$) because they are minimized and restricted from below by the binary values.

More on path generation for problem PD(N-L) can be found in [71].

Hot-Standby

Perhaps the most common protection mechanism used in communication networks is hot-standby (HS), known also as 1+1 protection. In HS, the entire volume of every demand d ∈ $\mathcal{D}$ is realized on a single path and protected also by a single, dedicated failure disjoint path. HS assures 100% protection of the demands for the single-link failure scenarios. The related optimization problem is as follows.

$HS\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.58a)

$\begin{array}{ll}{\displaystyle \sum _{r\in {ℛ}_d}{u}_{dr}}=1\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.58b)

$\begin{array}{ll}{\displaystyle \sum _{d\in \mathcal{D}}\left({\displaystyle \sum _{r\in {ℛ}_{ed}^1}{u}_{dr}+}{\displaystyle \sum _{r\in {ℛ}_{ed}^2}{u}_{dr}}\right)}{h}_d\le y_e\hfill & e\in ℰ\hfill \end{array}$

(18.58c)

$\begin{array}{ll}{u}_{dr}\in \left\{0,1\right\}\hfill & d\in \mathcal{D},r\in \hfill \end{array}{ℛ}_d$

(18.58d)

$\begin{array}{ll}{y}_e\in ℝ\hfill & e\in ℰ.\hfill \end{array}$

(18.58e)

Note that reliable links can appear in both the primary and the backup path used for a demand; in such a case the link is loaded twice by the demand’s volume.

The above problem is in fact very similar to the simple design problem SDP(LP) (18.10) discussed in Section 18.2.3. As in SDP(L-P), the continuous link capacities are split among the demands and the resulting parts are dedicated to individual demands. Therefore, the problem can be split and solved separately for each demand. As for SDP(L-P), each of such separate formulations is totally unimodular (see Subsection 18.57) and will yield a binary optimal vertex solution even if the integrality condition (18.58d) is relaxed to 0 ≤ u_dr ≤ 1. For a fixed d ∈ $\mathcal{D}$, such an optimal vertex solution will assign u_dr = 1 to a ξ-shortest pair r ∈ $\mathcal{R}$_d, i.e., to a pair r = (p, q) with the minimum cost

$\langle r\rangle ={\displaystyle \sum _{e\in p}{\xi }_e}+{\displaystyle \sum _{e\in q}{\xi }_e}.$

(18.59)

Note that by substituting the right-hand side of (18.58c) for y_e in objective (18.58a) we can get rid of constraint (18.58c) and then deriving the problem dual to the relaxation of HS(L-P) becomes straightforward. Using the dual, it can be easily shown that column generation consists in finding, for each demand d ∈ $\mathcal{D}$, a pair of failure-disjoint paths r = (p, q) minimizing its cost (18.59).

Hence, in this particular case, the primal problem (18.58) and its pricing problem (18.59) are equivalent. With single link failures, a pair of failure-disjoint paths minimizing (18.59) can be found in polynomial time using the Suurballe algorithm [73] or its modification described in [74]. For the general case of multiple-link failures, finding a minimum-cost disjoint pair of paths is $\mathcal{N}$$\mathcal{P}$-hard [75].

We end the discussion of HS by a remark on application of Benders decomposition. We simply notice that BD remains essentially the same as in the case described in Subsection 18.3.1, with the only difference that inequality (18.20b) in the feasibility test of Step 2 of Algorithm BD becomes

$\begin{array}{ll}{\text{λ}}_d\le {\displaystyle \sum _{e\in p}{\pi }_e}+{\displaystyle \sum _{e\in q}{\pi }_e}\hfill & d\in \mathcal{D},r=\left(p,q\right)\in {ℛ}_d.\hfill \end{array}$

(18.60)

Certainly, modular capacities can be considered in the BD master problem as well.

18.4.2    Restoration Models

Restoration mechanisms are dynamic in the sense that in case of a failure they are capable of restoring the failed flows on nonaffected routing paths, that is, to reconfigure the flow pattern in real-time.

Unrestricted Reconfiguration

We start our presentation with conceptually the simplest restoration mechanism referred to as unrestricted reconfiguration (UR). When a failure occurs, the UR mechanism disconnects all the flows and realizes from scratch a new, failure situation-dependent flow pattern within the surviving link capacity. The corresponding optimization problem reads:

$UR\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.61a)

$\begin{array}{ll}\left[{\text{λ}}_d^s\right]{\displaystyle \sum _{p\in P_d^s}{x}_{dp}^s=h_d^s}\hfill & d\in \mathcal{D},s\in \mathcal{S}\hfill \end{array}$

(18.61b)

$\begin{array}{ll}\left[{\pi }_e^s\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}^s}{x}_{dp}^s\le y_e}}\hfill & e\in ℰ,s\in {\mathcal{S}}_e\hfill \end{array}$

(18.61c)

$\begin{array}{ll}{x}_{dp}^s\in {ℝ}_{+}\hfill & d\in \mathcal{D},s\in \mathcal{S},p\in P_d^s\hfill \end{array}$

(18.61d)

$\begin{array}{ll}{y}_e\in ℝ\hfill & e\in ℰ\hfill \end{array}.$

(18.61e)

The problem dual to UR(L-P) can be written as follows:

$\max W\left(\text{λ},\pi \right)={\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{s\in \mathcal{S}}{h}_d^s{\text{λ}}_d^s}}$

(18.62a)

$\begin{array}{ll}{\text{λ}}_d^s\le {\displaystyle \sum _{e\in p}{\pi }_e^s}\hfill & d\in \mathcal{D},s\hfill \end{array}\in \mathcal{S},p\in P_d^s$

(18.62b)

$\begin{array}{ll}{\displaystyle \sum _{s\in {\mathcal{S}}_e}{\pi }_e^s}={\xi }_e\hfill & e\in ℰ\hfill \end{array}$

(18.62c)

$\begin{array}{ll}{\text{λ}}_d^s\in ℝ\hfill & e\in \mathcal{D},s\in \mathcal{S}\hfill \end{array}$

(18.62d)

${\pi }_e^s\in {ℝ}_{+}e\in ℰ,s\in \mathcal{S}.$

(18.62e)

In any optimal solution λ*, π* of the dual, the value ${\text{λ}}_d^{s*}$ is the length of the shortest path $p\in {\mathcal{P}}_d^s$ with respect to link metrics ${\pi }^{s*}=\left({\pi }_e^{s*},e\in {\epsilon }_s\right)$. Hence, for any failure scenario (both single and multiple link failure), the pricing problem reduces, for each network state s ∈ S, to the separate shortest path problem for every demand d ∈ $\mathcal{D}$ for the link metrics π^s*. The pricing problem is thus solvable in polynomial time in the number of nodes, links, and network states. This means that UR is polynomial also when all elementary paths are admissible. Hence, it is not surprising that it can be expressed in a compact form using node-link formulation for any, even multiple, link failure scenario $\mathcal{S}$.

Also Benders decomposition (examined in detail in [76], see also [2]) for UR is quite simple, still instructive to perform (Exercise 18.6.11). In Step 2 of Algorithm BD we perform feasibility tests separately for each state s ∈ $\mathcal{S}$. Each such test is essentially the same as (18.20); for a fixed s ∈ $\mathcal{S}$ looks as follows:

$\max W\left(\text{λ},\text{π}\right)={\displaystyle \sum _{d\in \mathcal{D}}{h}_d^s{\text{λ}}_d}-{\displaystyle \sum _{d\in {ℰ}_s}{y}_e^{*}{\pi }_e}$

(18.63a)

${\text{λ}}_d\le \begin{array}{ll}{\displaystyle \sum _{e\in p}{\pi }_e}\hfill & d\in \mathcal{D},p\in P_d^s\hfill \end{array}$

(18.63b)

${\displaystyle \sum _{e\in {ℰ}_s}{\pi }_e=1}$

(18.63c)

$\begin{array}{ll}{\pi }_e\ge 0\hfill & e\in {ℰ}_s.\hfill \end{array}$

(18.63d)

For UR (and also for the problem RR consider below), Benders inequalities can be used to deduce strong valid inequalities for the incremental modular link capacity model [12, 38] (the incremental modular link capacity model is described in Subsection 18.2.3).

Certainly, UR would be highly impractical to control by a central unit, as for example in transmission networks. However, in the higher network layers (called the traffic layers) the routing protocols can sometimes realize UR in a distributed, automatic way, although with a considerable rerouting time. This is the case for example when dynamic call routing is used in an IDN (contemporary telephone network) or in an autonomous system using the OSPF protocol [2]. In any case, the optimization problem related to UR is important because it sets a lower bound on the cost of the protected network since UR is the least constrained survivable network design problem we can think of.

Restricted Reconfiguration

A more realistic reconfiguration mechanism is referred to as restricted reconfiguration (RR). With RR, the flows that are not affected by a failure are not disconnected, i.e., nonfailing flows are preserved and only the affected flows are restored. In the balance of this paragraph, we assume that for every d ∈ $\mathcal{D}$, $h_d^s=h_d$ for all s ∈ $\mathcal{S}$. Although we could perform all the following derivations without this 100% restoration assumption, we adopt it not in order to keep the presentation simple. We will distinguish two cases of RR: with, and without stub-release. With stub-release, the capacity on the surviving parts (stubs) of a failing routing path can be reused for backup flows; without stub-release, this capacity cannot be reused for restoration as it is reserved for the normal network state flows.

In the following problem RR/SR, we consider situation-dependent restoration of failed flows utilizing stub-release, i.e., the case when the capacity released on the surviving stubs of failing paths can be reused for backup flows.

$RR/SR\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.64a)

$\begin{array}{ll}\left[{\text{λ}}_d^{\varnothing }\right]{\displaystyle \sum _{p\in P_d}{x}_{dp}=h_d}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.64b)

$\begin{array}{ll}\left[{\text{λ}}_d^s\right]{\displaystyle \sum _{p\in P_d^s}{x}_{dq}^s={\displaystyle \sum _{p\in P_d^s}{x}_{dp}}}\hfill & d\in \mathcal{D},s\in \mathcal{S}\{\varnothing \}\hfill \end{array}$

(18.64c)

$\begin{array}{ll}\left[{\pi }_e^{\varnothing }\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{\mathrm{ed}}^s}{x}_{dp}\le y_e}}\hfill & e\in ℰ\hfill \end{array}$

(18.64d)

$\begin{array}{ll}\left[{\pi }_e^s\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}^s}{x}_{dp}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}^s}{x}_{dq}^s\le y_e}}}}\hfill & e\in ℰ,s\in \hfill \end{array}{S}_e\{\varnothing \}$

(18.64e)

$\begin{array}{ll}{x}_{dp}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\hfill \end{array}\in P_d$

(18.64f)

$\begin{array}{ll}{x}_{dp}^s\in {ℝ}_{+}\hfill & d\in \mathcal{D},s\in \mathcal{S},p\hfill \end{array}\in P_d^s$

(18.64g)

$\begin{array}{ll}{y}_e\in ℝ\hfill & e\in ℰ.\hfill \end{array}$

(18.64h)

In RR/SR(L-P), for every d ∈ $\mathcal{D}$, x_dp denote the nominal flows realizing demand volume h_d (constraint (18.64b)), while $x_{dp}^s$ are the restoration flows that are used in a failure state s ∈ $\mathcal{S}$ {∅} to restore the failing nominal flows of d (constraint (18.64c)). Constraints (18.64d) and (18.64e), in turn, assure that the link capacity reservations are sufficient in the nominal state and in every failure state.

No compact LP formulation for problem RR/SR is known, even for the single link failure scenario, and the problem is most likely $\mathcal{N}$$\mathcal{P}$-hard already for single failures. Hence, not surprisingly, path generation for formulation (18.64) is $\mathcal{N}$$\mathcal{P}$-hard, as will be demonstrated now. The problem dual to RR/SR(L-P) reads:

$\max W\left(\text{λ}\right)={\displaystyle \sum _{d\in \mathcal{D}}{h}_d}{\text{λ}}_d^{\varnothing }$

(18.65a)

$\begin{array}{ll}{\text{λ}}_d^s\le {\displaystyle \sum _{e\in p}{\pi }_e^s}\hfill & d\in \mathcal{D},s\in \mathcal{S}\hfill \end{array}\{\varnothing \},p\in P_d^s$

(18.65b)

$\begin{array}{ll}{\text{λ}}_d^{\varnothing }\le {\displaystyle \sum _{e\in p}\left({\displaystyle \sum _{e\in {\mathcal{S}}_p}{\pi }_e^s}\right)+{\displaystyle \sum _{e\in {\overline{\mathcal{S}}}_p}{\text{λ}}_d^s}}\hfill & d\in \mathcal{D},\hfill \end{array}p\in P_d^s$

(18.65c)

$\begin{array}{ll}{\displaystyle \sum _{e\in {\mathcal{S}}_e}{\pi }_e^s={\xi }_e}\hfill & e\in ℰ\hfill \end{array}$

(18.65d)

$\begin{array}{ll}{\text{λ}}_d^s\in ℝ\hfill & d\in \mathcal{D},\hfill \end{array}s\in \mathcal{S}$

(18.65e)

$\begin{array}{ll}{\pi }_e^s\in {ℝ}_{+}\hfill & e\in ℰ,\hfill \end{array}s\in {\mathcal{S}}_e.$

(18.65f)

Denote the optimal dual variables solving (18.65) by λ*, π*. Similarly to the case of UR, it is easy to find an improving protection path q(d) for every demand d ∈ $\mathcal{D}$ in any failure situation s ∈ $\mathcal{S}$ {∅} by solving the shortest path problem between the end-nodes of d in the surviving network with respect to the link weights π^s*.

On the other hand, finding improving primary paths is $\mathcal{N}$$\mathcal{P}$-hard already in the case of single link failures, as suggested in [12, 77], and shown later in [78] and [79]. To solve the pricing problem for a fixed demand d ∈ $\mathcal{D}$ we have to find a path p(d) from s(d) to t(d) minimizing the quantity

$\langle p\rangle ={\displaystyle \sum _{e\in p}\left({\displaystyle \sum _{s\in {\mathcal{S}}_p}{\pi }_e^{s*}}\right)+}{\displaystyle \sum _{s\in {\overline{\mathcal{S}}}_p}{\text{λ}}_d^{s*}.}$

(18.66)

The difficulty in minimizing the sum on the right-hand side stems from the term ${\displaystyle {\sum }_{x\in p}{\displaystyle {\sum }_{s\in {\mathcal{S}}_p}{\pi }_e^{s*}}}$. Because of that, the length of a path in the pricing problem is not a sum of independent link weights like in usual shortest-path problems. Instead, the contribution ${\displaystyle {\sum }_{x\in {\mathcal{S}}_p}{\pi }_e^{s*}}$ of a link to the path length depends on the set of failure situations in which the path survives, and thus on the whole path. Under a full single link failure scenario, this path length reduces to

$\langle p\rangle ={\displaystyle \sum _{e\in p}\left({\displaystyle \sum _{f\notin p}{\pi }_e^{f*}}\right)+}{\displaystyle \sum _{s\in {\overline{\mathcal{S}}}_p}{\text{λ}}_d^{\left\{e\right\}*}.}$

(18.67)

It can be shown by reduction to the Hamilton path problem [79] or to the max-cut problem [78] that already minimizing ${\displaystyle {\sum }_{x\in \epsilon }\left({\displaystyle {\sum }_{f\notin p}{\pi }_e^{f*}}\right)}$ is $\mathcal{N}$$\mathcal{P}$-hard, which implies the $\mathcal{N}$$\mathcal{P}$-hardness of minimizing (18.67). Observe that pricing problem (18.66) can be formulated as a MIP problem in the N-L notation using binary variables analogously to (18.57).

Problem RR/SR can be treated by Benders decomposition. It this case, however, the master problem (see Algorithm BD in Subsection 18.3.1) has to include variables x = (x_dp, d ∈$\mathcal{D}$, p ∈ $\mathcal{P}$_d) on top of the link capacity reservation variables y since both sets of variables influence all state s ∈ $\mathcal{S}${∅}. For RR/SR, the master program becomes:

$\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.68a)

$\begin{array}{ll}{\displaystyle \sum _{p\in P_d}{x}_{dp}}=h_d\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.68b)

$\begin{array}{ll}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d}{x}_{dp}}}\le y_e\hfill & e\in ℰ\hfill \end{array}$

(18.68c)

$\left(x,y\right)\in \mathcal{Y}\left(\text{Ω}\right)$

(18.68d)

and the feasibility test for state s ∈ $\mathcal{S}$ {∅} follows from the (dual) problem:

$\max W\left(\text{λ},\pi \right)={\displaystyle \sum _{d\in \mathcal{D}}\left(h_d-{\displaystyle \sum _{p\in P_d^s}{x}_{dp}^{*}}\right)\text{λ}d-}{\displaystyle \sum _{d\in {ℰ}_s}\left(y_e^{*}-{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_d^s}{x}_{dp}^{*}}}\right){\pi }_e}$

(18.69a)

$\begin{array}{ll}{\text{λ}}_d\le {\displaystyle \sum _{e\in p}{\pi }_e}\hfill & d\in \mathcal{D},p\in P_d^s\hfill \end{array}$

(18.69b)

${\displaystyle \sum _{e\in {ℰ}_s}{\pi }_e}=1$

(18.69c)

${\pi }_e\ge 0e\in {ℰ}_s.$

(18.69d)

Note that $h_d-{\displaystyle {\sum }_{p\in {\mathcal{P}}_d^s}{x}_{dp}^{*}}$ is the actual demand volume of demand d that has to be restored in state s using the available link capacity $y_e^{*}-{\displaystyle {\sum }_{d\in \mathcal{D}}{\displaystyle {\sum }_{p\in {\mathcal{P}}_{ed}^s}{x}_{dp}^{*}},e\in {\epsilon }_s}$. In Step 3 of the BD algorithm, we add an inequality for each failure situation s with W(λ*,π*) > 0:

$\text{Ω:=Ω}\cup \left\{{\displaystyle \sum _{e\in ℰ}{\pi }_e^{*}\left(y_e-{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}^s}{x}_{dp}}}\right)\ge }{\displaystyle \sum _{d\in \mathcal{D}}{\text{λ}}_d^{*}\left(h_d-{\displaystyle \sum _{p\in P_d^s}{x}_{dp}}\right)}\right\}.$

The counterpart for RR/SR that does not utilize the stub-release is as follows.

$RR/NSR\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.70a)

$\left[{\text{λ}}_d^{\varnothing }\right]{\displaystyle \sum _{p\in P_d}{x}_{dp}}=hdd\in \mathcal{D}$

(18.70b)

$\left[{\text{λ}}_d^s\right]{\displaystyle \sum _{q\in P_d^s}{x}_{dq}^s}={\displaystyle \sum _{p\in {\overline{P}}_d^s}{x}_{dp}}d\in \mathcal{D},s\in \mathcal{S}\{\varnothing \}$

(18.70c)

$\left[{\text{λ}}_e^s\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{x}_{dp}}}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{q\in P_{ed}^s}{x}_{dq}^s\le y_e}}e\in ℰ,s\in {\mathcal{S}}_e\{\varnothing \}$

(18.70d)

$\begin{array}{ll}{x}_{dp}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\in P_d\hfill \end{array}$

(18.70e)

$\begin{array}{ll}{x}_{dp}^s\in {ℝ}_{+}\hfill & d\in \mathcal{D},s\in \mathcal{S},p\in P_d^s\hfill \end{array}$

(18.70f)

$\begin{array}{ll}{y}_e\in {ℝ}_{}\hfill & e\in ℰ.\hfill \end{array}$

(18.70g)

The main difference between RR/NSR and RR/SR is in constraints (18.70d) and (18.64e), respectively. According to (18.70d) (RR/NSR), the surviving link in state s is loaded by all nominal flows, whether or not they survive in s, while according to (18.70d) (RR/SR) the link is loaded only by surviving nominal flows.

Omitting the formulation of the dual (Exercise 18.6.12), we directly proceed to the pricing problems, assuming the optimal dual variables λ*,π*. For the backup paths, the pricing problem consists in finding, for each state s ∈ $\mathcal{S}$ {∅} and each demand d ∈ $\mathcal{D}$, a shortest path q(d, s) between s(d) and t(d) in the graph composed of the nonfailing links E_s , with respect to the weights π^s*. For each such pair (d, s), if the path q(d, s) is strictly shorter than ${\text{λ}}_d^s*$ then it is added to the current path list ${\mathcal{P}}_d^s$. For the primary paths, the pricing problem is to find, for each demand d ∈ $\mathcal{D}$, a shortest path p(d) with respect to the length defined by

$\langle p\rangle ={\displaystyle \sum _{e\in p}{\xi }_e+}{\displaystyle \sum _{s\in {\overline{\mathcal{S}}}_p}{\text{λ}}_d^{s*}.}$

(18.71)

The above problem is identical to the pricing problem (18.56) for PD so all the observations made for (18.56) apply. As PD, problem RR/NSR is $\mathcal{N}$$\mathcal{P}$-hard for multiple link failure scenarios [71].

The way of applying BD to RR/NSR is left to the reader as Exercise 18.6.13.

Situation-Independent Restoration

In restricted reconfiguration RR (and for that matter also in UR) the failed nominal flows are restored in a situation-dependent manner so in effect different backup paths can be used in different failure situations to restore the primary flow on path p. In situation-independent restoration, the failed flow on a primary path p is restored always using the same backup path q, no matter what particular failure situation affects the flow on path p. Certainly, for that we need to require that paths p and q are failure disjoint. For this type of restoration it is natural not to utilize stub-release, that is, the surviving but unused working link capacity is not reused for backup flows. Thus we concentrate on the case with no stub-release (the case with stub-release is presented in [71]). Using variables z_dpq to denote the flow on backup path q ∈ $\mathcal{Q}$_p of working path p ∈ $\mathcal{P}$_d, the corresponding design problem can be formulated as follows:

$SI/NSR\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e{y}_e}$

(18.72a)

$\begin{array}{ll}\left[{\text{λ}}_d\right]{\displaystyle \sum _{p\in P_d}{x}_{dp}=hd}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.72b)

$\begin{array}{ll}{\displaystyle \sum _{q\in Q_p}z{d}_{pq}=x_{dp}}\hfill & d\in \mathcal{D}\hfill \end{array},p\in P_d$

(18.72c)

$\left[{\pi }_e^s\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{x}_{dp}}}\begin{array}{ll}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in {\overline{P}}_d^s}{\displaystyle \sum _{q\in Q_{ep}}{z}_{dpq}\le }{y}_e}}\hfill & e\in ℰ\hfill \end{array},s\in {\mathcal{S}}_e\{\varnothing \}$

(18.72d)

$\begin{array}{ll}{x}_{dp}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\in P_d\hfill \end{array}$

(18.72e)

$\begin{array}{ll}{z}_{dpq}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\in P_d,q\in Q_{dp}\hfill \end{array}$

(18.72f)

$\begin{array}{ll}{y}_e\in ℝ\hfill & e\in ℰ.\hfill \end{array}$

(18.72g)

As far as PG for SI/NSR is concerned, note that dual variables corresponding to primal constraints (18.72c) are not required as we can get rid of constraint (18.72c) by substituting ${\displaystyle {\sum }_{q\in {\mathcal{Q}}_p}{z}_{dpq}}$ for x_dp in (18.72b) and (18.72d). Again, we omit formulating dual to SI/NSR(L-P) (the dual problem can be found in [71]) and proceed to the pricing problem. Assuming the optimal dual variables λ*,π*, the pricing problem consists of finding, for each demand d ∈ $\mathcal{D}$, a pair of failure disjoint paths r(d) = (p(d), q(d)) from s(d) to t(d) minimizing the expression

$\langle r\rangle ={\displaystyle \sum _{e\in p}{\xi }_e+{\displaystyle \sum _{e\in q}\left({\displaystyle \sum _{e\in {\overline{\mathcal{S}}}_p}{\pi }_e^{s*}}\right).}}$

(18.73)

For each demand d, if the value 〈r(d)〉 is strictly smaller than λ_d* then we modify the admissible sets: $\mathcal{P}$_d := $\mathcal{P}$_d ∪ {p(d)} and $\mathcal{Q}$_p(d) := $\mathcal{Q}$_p(d) ∪ {q(d)}. Note that $\mathcal{P}$_d may already contain p(d) or $\mathcal{Q}$_p(d) may already contain q(d).

The pricing problem (18.73) is $\mathcal{N}$$\mathcal{P}$-hard already for single-link failure scenarios as shown in [80]. In fact, it is demonstrated in [81] for directed graphs that problem SI/NSR itself is $\mathcal{N}$$\mathcal{P}$-hard (already for single link failure scenarios). This is done using a reduction from Two Diverse Paths problem [82] – a special case of the $\mathcal{N}$$\mathcal{P}$-hard Disjoint Connecting Paths problem [10] – consisting of finding two link-disjoint paths between two distinct pairs of nodes.

Application of Benders decomposition to SI/NSR uses the same master problem as in the BD algorithm presented in Section 18.3.1, and the feasibility test derived form the following version of FAP (see (18.16):

$\min z$

(18.74a)

$\begin{array}{ll}\left[{\text{λ}}_d\right]{\displaystyle \sum _{p\in P_d}{\displaystyle \sum _{q\in Q_p}{z}_{dpq}=h_d}}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.74b)

$\begin{array}{ll}\left[{\pi }_e^s\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{\displaystyle \sum _{q\in Q_p}{z}_{dpq}}+{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in {\overline{P}}_d^s}{\displaystyle \sum _{q\in Q_{ep}}{z}_{dpq}}\le y_e^{*}+ze\in ℰ,}}}}\hfill & s\in {\mathcal{S}}_e\{\varnothing \}\hfill \end{array}$

(18.74c)

$\begin{array}{ll}{z}_{dpq}\in {ℝ}_{+}\hfill & d\in \mathcal{D},p\in P_d,q\in \hfill \end{array}{Q}_{dp}$

(18.74d)

where y* is the solution of the BD master problem. Problem dual to (18.74) is as follows:

$\max W\left(\text{λ},\pi \right)={\displaystyle \sum _{d\in \mathcal{D}}{h}_d{\text{λ}}_d-{\displaystyle \sum _{e\in ℰ}\left({\displaystyle \sum _{s\in \mathcal{S}e\{\varnothing \}}{\pi }_e^s}\right)y_e^{*}}}$

(18.75a)

${\text{λ}}_d\le {\displaystyle \sum _{e\in p}\left({\displaystyle \sum _{s\in \mathcal{S}e\{\varnothing \}}{\pi }_e^s}\right)+{\displaystyle \sum _{e\in q}\left({\displaystyle \sum _{s\in {\overline{\mathcal{S}}}_p}{\pi }_e^s}\right)d\in \mathcal{D},p\in P_d,q\in Q_{dp}}}$

(18.75b)

${\displaystyle \sum _{e\in ℰ}{\displaystyle \sum _{s\in {\overline{\mathcal{S}}}_e\{\varnothing \}}{\pi }_e^s}}=1$

(18.75c)

${\pi }_e^s\ge 0e\in ℰ,s\in {\mathcal{S}}_e\{\varnothing \}.$

(18.75d)

Therefore, if for optimal solution λ*,π* of the above dual it turns out that W(λ*, π*) > 0 then the BD inequality

${\displaystyle \sum _{e\in ℰ}\left({\displaystyle \sum _{s\in {\mathcal{S}}_e\{\varnothing \}}{\pi }_e^{s*}}\right)}{y}_e\ge {\displaystyle \sum _{d\in \mathcal{D}}{h}_d{\text{λ}}_d^{*}.}$

(18.76)

is added to the set Ω in Step 3 of the BD algorithm.

Note that using BD for SI/NSR can be beneficial (especially when modular link capacities are considered) because of a large number of the flow variables z required in the primal formulation of the problem.

Situation-Independent Restoration with Nonbifurcated Flows

Let us now consider the nonbifurcated version of SI/NSR which assumes that the entire volume h_d of each demand d is realized on a single primary path p ∈ $\mathcal{P}$_d protected by a single failure-disjoint path q ∈ $\mathcal{Q}$_p. This version of SI/NSR is a backup capacity sharing counterpart of the problem (18.58) with the hot-standby 1+1 protection where backup capacity is dedicated to individual primary paths. The corresponding mixed-binary programming (MBP) problem reads:

$SI/NBR\left(L-P\right):\min F\left(y\right)={\displaystyle \sum _{e\in ℰ}{\xi }_e\left(y_e^1+y_e^2\right)}$

(18.77a)

$\begin{array}{ll}{\displaystyle \sum _{e\in {ℛ}_d}{u}_d{}_r=1}\hfill & d\in \mathcal{D}\hfill \end{array}$

(18.77b)

$\begin{array}{ll}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{r\in {ℛ}_{ed}^1}{h}_d{u}_d{}_r\le y_e^1}}\hfill & e\in ℰ\hfill \end{array}$

(18.77c)

$\begin{array}{ll}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{r=\left(p,q\right)\in {ℛ}_{ed}^2:s\in {\overline{\mathcal{S}}}_p}{h}_d{u}_d{}_r\le y_e^2}}\hfill & e\in ℰ\hfill \end{array},s\in {\mathcal{S}}_e\{\varnothing \}$

(18.77d)

$\begin{array}{ll}{u}_d{}_r\in \left\{0,1\right\}\hfill & d\in \mathcal{D}\hfill \end{array},r\in {ℛ}_d$

(18.77e)

$\begin{array}{ll}{y}_e^1,y_e^2\in ℝ\hfill & e\in ℰ\hfill \end{array}.$

(18.77f)

Above, $y_e^1$ and $y_e^2$ denote, respectively, the primary and the backup capacity reservation on link e ∈ ℰ. The primary capacity y¹ is reserved for the nominal (i.e., primary) flows, while the backup capacity y² is reserved for the backup flows. Certainly, contrary to HS (see (18.58)), backup capacity is now shared between backup flows in different failure situations s ∈$\mathcal{S}$ {∅}.

Although looking quite different at first glance, the LP relaxation of SI/NBR (18.77) is equivalent to problem SI/NSR (18.72). The reason is that several pairs r ∈ R_d can have the same primary path p ∈ $\mathcal{P}$_d and consequently all the corresponding paths q ∈$\mathcal{Q}$_p are used to protect path p in a bifurcated way. Also, the problem dual to the relaxation of (18.77) is identical to the dual of (18.72).

Finally, observe that we can write down a compact MIP node-link formulation of SI/NBR, although for the LP relaxation of the problem a compact formulation does not exist. This MIP formulation is as follows:

$\text{SI}/\text{NBR}\left(\text{N-L}\right):\min F\left(y\right)={\displaystyle \sum _{e\in \epsilon }{\text{ξ}}_e\left(y_e^1+y_e^2\right)}$

(18.78a)

${\displaystyle \sum _{e\in \delta +\left(\upsilon \right)}{x}_{ed}}-{\displaystyle \sum _{e\in \delta -\left(\upsilon \right)}{x}_{ed}}=\{\begin{array}{l}0,\upsilon \in \mathcal{V}\left\{s\left(d\right),t\left(d\right)\right\}\\ 1,\upsilon =s\left(d\right)\end{array}d\in \mathcal{D}$

(18.78b)

${\displaystyle \sum _{e\in {\delta }^{+}\left(\upsilon \right)}{z}_{ed}}-{\displaystyle \sum _{e\in \delta -\left(\upsilon \right)}{z}_{ed}}=\{\begin{array}{l}0,\upsilon \in \mathcal{V}\left\{s\left(d\right),t\left(d\right)\right\}\\ 1,\upsilon =s\left(d\right)\end{array}d\in \mathcal{D}$

(18.78c)

$x_{ed}+z_{ed}\le 1s\in \mathcal{S},e\in s,d\in \mathcal{D}$

(18.78d)

${\displaystyle \sum _{d\in \mathcal{D}}{h}_d}{x}_{ed}\le y_e^{1}e\in \epsilon$

(18.78e)

$x_{ed}\le W_{ds}\le {\displaystyle \sum _{e\in s}{x}_{ed}}s\in \mathcal{S}\left[\cancel{0}\right],e\in s,d\in \mathcal{D}$

(18.78f)

$Y_{eds}\ge z_{ed}-W_{ds}e\in \epsilon ,d\in \mathcal{D},s\in \mathcal{S}\left\{\cancel{0}\right\}$

(18.78g)

${\displaystyle \sum _{d\in \mathcal{D}}{g}_d{Y}_{eds}}\le y_e^{2}e\in \epsilon ,s\in \mathcal{S}\left\{\cancel{0}\right\}$

(18.78h)

$x_{ed},z_{ed}\in \left\{0,1\right\}e\in \epsilon ,d\in \mathcal{D}$

(18.78i)

$0\le Y_{eds}\le 1e\in \epsilon ,d\in \mathcal{D},s\in \mathcal{S}\left\{\cancel{0}\right\}.$

(18.78j)

In the above formulation, binary variables x_ed, e ∈ ℰ define the primary path p(d) = {e ∈ ℰ : x_ed = 1} for demand d ∈ $\mathcal{D}$, and binary variables z_ed, e v ℰ – its backup path q(d) = {e ∈ ℰ : z_ed = 1}. Note that due to (18.78d), paths p(d) and q(d) are failure disjoint. Variables W_ds, d ∈ $\mathcal{D}$, s ∈$\mathcal{S}$ {∅}, although formally continuous, can assume only binary values and indicate whether the primary path p(d) works in failure situation s (W_ds = 1) or it is failed (W_ds = 0). In turn, variables Y_eds, e ∈ ℰ, d ∈ $\mathcal{D}$, s ∈ $\mathcal{S}$ {∅} define the load h_dY_eds induced by backup path q(d) on link e in situation s. In particular, Y_eds = 1 indicates that h_d loads link e in situation s because e ∈ q(d) and p(d) fails in s – this is assured by constraints (18.78g) and (18.78j).

Link Protection

The last problem considered in this subsection is related to a restoration mechanism called link protection (LPR). LPR assumes a single link failure scenario, and contrary to the previous mechanisms, restores the failed capacity of link rather than end-to-end flows that use a failed link. This mechanism is applicable to facility networks like SDH/SONET [2]. The related NDP is as follows.

$\text{LPR}\left(\text{L-P}\right):\min F\left(y\right)={\displaystyle \sum _{e\in \epsilon }{\text{ξ}}_e}\left(y_e^1+y_e^2\right)$

(18.79a)

$\begin{array}{ccc}{\displaystyle \sum }_{p\in {\mathcal{P}}_d}{x}_{dp}=h_d& & d\in \mathcal{D}\end{array}$

(18.79b)

$\begin{array}{ccc}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in P_{ed}}{x}_{dp}}\le y_{\text{e}}^1}& & e\in \epsilon \end{array}$

(18.79c)

$\begin{array}{ccc}{\displaystyle \sum _{q\in {ℒ}_e}{u}_{eq}=1}& & e\in \epsilon \end{array}$

(18.79d)

${\displaystyle \sum _{q\in {ℒ}_{fe}}{y}_e^1{u}_{eq}}\le y_f^{2}e\in \epsilon ,f\in \epsilon ,e\ne f$

(18.79e)

$x_{dp}\in {ℝ}_{+}d\in \mathcal{D},p\in {\mathcal{P}}_d$

(18.79f)

$u_{eq}\in \left\{0,1\right\}e\in \epsilon ,q\in {ℒ}_d$

(18.79g)

$y_e^1,y_e^2\in ℝe\in \epsilon .$

(18.79h)

Above, $\mathcal{L}$_e denotes the set of paths between the end nodes of link e that are admissible for restoring the primary capacity $y_e^1$, and $\mathcal{L}$_fe denotes the set of paths from $\mathcal{L}$_e that contain link f. Primary capacity is restored in a nonbifurcated way on a single path from $\mathcal{L}$_e—this is assured by constraint (18.79d). The restoration flow of each (individually) failed link e uses the protection capacity $y_e^2$, f ∈ ℰ {e} of the other links. Note that the above formulation is bilinear (and hence not a MIP formulation) as it contains multiplication of variables in (18.79e). This bilinearity can be removed using standard methods (see [83]). In the LP relaxation, this bilinearity is not any issue, as we can use absolute continuous flows z_eq instead of binary flows u_eq, and substitute constraints (18.79d) and (18.79e) with

${\displaystyle \sum _{q\in {ℒ}_e}{z}_{eq}}=y_e^{1}e\in \epsilon$

(18.80a)

${\displaystyle \sum _{q\in {ℒ}_{fe}}{z}_{eq}}\le y_f^{2}e\in \epsilon ,f\in \epsilon ,e\ne f.$

(18.80b)

Path generation for the LP relaxation of LPR(L-P) is polynomial and hence LPR can be approached with BP (BPC). LPR can also be written in a compact N-L notation and approached with BB (CB, BC).

18.4.3    Multihour and Multiperiod Design

Multihour design refers to the situation when we are to dimension a network for many nonsimultaneous traffic matrices. This is for example relevant to modeling communication networks with noncoincident traffic busy hours or to the case of uncertain traffic when we have a large set of possible traffic matrices, but do not know which of them will actually be realized. Thus we assume a demand scenario, i. e., a set $\mathcal{T}$ of the traffic states τ ∈ $\mathcal{T}$. In this case, failures are not considered (in all states τ ∈ $\mathcal{T}$ all links are available) and the states differ only by their demand vectors h^τ, τ ∈ $\mathcal{T}$. In a demand scenario, we do not distinguish the normal state.

Consider the following multistate NDP:

$\text{MH}\left(\text{L-P}\right):minF\left(y\right)={\displaystyle \sum _{e\in \epsilon }{\text{ξ}}_e{y}_e}$

(18.81a)

$\left[{\text{λ}}_d^{\text{τ}}\right]{\displaystyle \sum _{p\in {\mathcal{P}}_d^{\text{τ}}}{x}_{dp}^{\text{τ}}}=h_d^{\text{τ}}d\in \mathcal{D},\text{τ}\in \mathcal{T}$

(18.81b)

${\text{π}}_e^{\text{τ}}{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{d\in {\mathcal{P}}_{ed}^{\text{τ}}}{x}_{dp}^{\text{τ}}}\le y_{e}e\in \epsilon ,\text{τ}\in \mathcal{T}}$

(18.81c)

$x_{dp}^{\text{τ}}\in {ℝ}_{+}d\in \mathcal{D},\text{τ}\in \mathcal{T},p\in {\mathcal{P}}_d^{\text{τ}}$

(18.81d)

$y_e\in ℝe\in \epsilon .$

(18.81e)

The problem assumes state-dependent routing and in fact has many similarities to problem UR (18.61) considered in Subsection 18.4.2. In particular, PG and BD (examined in detail in [84]) are very very similar to those of UR. Similarly, (18.81) can be easily written in the compact N-L notation (and, for that matter, also in the aggregated N-L notation).

Formulation (18.81) assumes state-dependent (dynamic) routing. Although it is a correct assumption for different traffic hours, it becomes not appropriate when we deal with traffic uncertainty. For the latter case, we should rather consider static state-independent routing (called also oblivious routing), i.e., a problem like this:

$\text{UT}\left(\text{L-P}\right):\min F\left(y\right)={\displaystyle \sum _{e\in \epsilon }{\text{ξ}}_e{y}_e}$

(18.82a)

$\left[{\text{λ}}_d\right]{\displaystyle \sum _{p\in {\mathcal{P}}_d}{x}_{dp}=1d\in \mathcal{D}}$

(18.82b)

$\left[{\text{π}}_e^{\tau }\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in {\mathcal{P}}_{ed}}{h}_d^{\text{τ}}{x}_{dp}}\le y_{e}e\in \epsilon ,\tau \in \mathcal{T}}$

(18.82c)

$x_{dp}\in {ℝ}_{+}d\in \mathcal{D},p\in {\mathcal{P}}_d$

(187.82d)

$y_e\in ℝe\in \epsilon .$

(18.82e)

The nature of UT is different than that of MH. In particular, the pricing problem in PG is different, and BD is not applicable to UT. Moreover, although UT possesses an N-L formulation, it does not possess an aggregated N-L formulation (Exercise 18.6.14).

To end the presentation of NDPs with nonsimultaneous traffic matrices we formulate, for completeness, the so-called multiperiod design problem. In this case the states τ ∈ T = {1, 2,…, $\mathcal{T}$} correspond to consecutive periods of network operation, say, to consecutive years. At the beginning of each period the capacity of the network is extended (see Chapter 11 in [2]).

$\text{MP}\left(\text{L-P}\right):\min F\left(y\right)={\displaystyle \sum _{\tau =1}{\displaystyle \sum _{e\in \epsilon }{\text{ξ}}_e^{\text{τ}}}{y}_e^{\text{τ}}}$

(18.83a)

$\left[{\text{λ}}_d^{\text{τ}}\right]{\displaystyle \sum _{p\in {\mathcal{P}}_d^{\text{τ}}}{x}_{dp}^{\text{τ}}}=h_d^{\text{τ}}d\in \mathcal{D},\tau \in \mathcal{T}$

(18.83b)

$\left[{\text{π}}_e^{\text{τ}}\right]{\displaystyle \sum _{d\in \mathcal{D}}{\displaystyle \sum _{p\in {\mathcal{P}}_{ed}^{\text{τ}}}{x}_{dp}^{\text{τ}}}}\le {\displaystyle \sum _{t=1}^{\tau }{y}_e^t}e\in \epsilon ,\tau \in \mathcal{T}$

(18.83c)

$x_{dp}^{\tau }\in {ℝ}_{+}d\in \mathcal{D},\tau \in \mathcal{T},p\in {\mathcal{P}}_d^{\tau }$

(18.83d)

$y_e^{\tau }\in ℝe\in \epsilon ,\tau \in \mathcal{T}.$

(18.83e)

This problem also possesses an N-L formulation and an aggregated N-L formulation. It can also be easily treated by PG and BD.

18.5    Concluding Remarks

In this chapter, we have discussed optimization models for communication networks design and planning. An optimization model is understood as an appropriate mathematical problem formulation expressed in the language of multicommodity flow networks and mixed-integer programming, together with a set of algorithms that can be applied for finding the problem’s optimal or near-optimal solutions. Section 18.2 is devoted to problem formulations. Consequently, it introduces the notation and discusses two basic types of network design problem (NDP) formulations: dimensioning problems (such as SDP) involving simultaneous optimization of link capacity reservations and flow patterns, and flow allocation problems (such as FAP) involving only flow patterns optimization. For both types of problems, we have used link-path notation leading to noncompact formulations, and node-link notation (and its variant – aggregated notation) leading to compact formulations. We have also discussed different variants of SDP and FAP including modular dimensioning and several routing requirements. Finally, we have discussed concave and convex link dimensioning models and their MIP/LP approximations.

In Section 18.3, we have surveyed basic optimization methods and algorithms for solving the considered multicommodity flow problem formulations, with an emphasis put on exact methods of mixed-integer programming. Here, such methods as path generation, Benders decomposition, cutting plane, branch-and-bound, and its variants have been discussed.

Section 18.4 presents a number of advanced optimization problems related to multistate design of communication networks, thus encompassing design of resilient networks, multihour design and multiperiod design. It is explained why the mixed-integer programming techniques presented in Section 18.3 are important for the presented problems. In particular, path generation is necessary for (intrinsically) noncompact LP models like PD, RR, and SI. Branch-and-cut is crucial for the modular dimensioning and for the single-path routing versions of the problems. In the latter case, branch-and-price and branch-and-price-and-cut are also important when noncompact formulations are considered. Finally, Benders decomposition may become a helpful means for improving the optimization efficiency, as it decreases the number of variables in the master problem by projecting out the flow variables.

The potential number of valid NDPs combining different capacity modularity, routing, protection/restotration, and multihour and multiperiod options is enormous. Certainly, in a chapter of this size, we have not been able to cover all aspects of NDPs and had to omit certain models. In particular, we have omitted the case of multilayer networks (a communication network is typically composed of several resource layers, as for example IDN-over-SONET-over-WDM networks or IP-over-WDM networks), radio networks (for example radio access networks such as wireless mesh networks or cellular networks), IP networks with shortest path routing (of the OSPF type), and others. These aspects extend the class of important and valid NDPs even more. We hope, however, that the material presented in this chapter forms a critical mass for understanding the basics of the MFN modeling and integer programming techniques, and will prepare the reader to cope with the omitted models as well. For more reading, we refer the reader to such handbooks on network optimization, design, and planning as [2, 3, 29], to the papers cited in the main body of this chapter, and, eventually, to numerous interesting and valuable papers on network design and multicommodity flow networks available in communications and operations research journals and conferences proceedings.

Finally, we should emphasize that the mixed-integer programming techniques can in many cases help to effectively solve the considered network design problems to optimality or near-optimality. However, most of the problems dealt with in network design are NP-hard, and because of that we cannot expect that the MIP approaches will always be effective, at least for large problem instances. As a practical guideline, we may roughly say that in general a MIP formulation with a weak LP relaxation and/or with only weak cutting planes available, may not be efficiently solvable even with the best MIP solvers. In fact, these are only the (compact) linear programming formulations that guarantee optimal solutions in a reasonable time. The reader is encouraged to check this observation on NP-hard problem instances (and their LP relaxations) formulated in Section 18.4, using a state-of-the-art MIP solver for network examples from the library of NDP examples described in [85].

18.6    Exercises

Exercise 18.6.1. Give an example of a simple network configuration with more than one path-flow pattern realizing a given link-flow pattern.

Exercise 18.6.2. Prove that the SPA rule leads to an optimal solution of SDP. Give an example when an optimal solution assigns non-zero flows to more than one path of a demand.

Exercise 18.6.3. Write down the incremental version of (18.12).

Exercise 18.6.4. Find a piecewise linear approximation of $f\left(z\right)=\sqrt{z}$ in [0, +∞) with K = 4 linear pieces and exact values for z = 0, 1, 4, 9, 16. Write down SDP/CV for this particular approximation.

Exercise 18.6.5. Find a piecewise linear approximation of f (z) = z² in [0, +∞) with K = 4 linear pieces and exact values for z = 0, 1, 2, 3, 4. Write down SDP/CX for this particular approximation.

Exercise 18.6.6. Consider a triangle symmetrical undirected network with 3 nodes ($\mathcal{V}$ = {v₁,v₂,v₃}), 3 links (ℰ = {e₁ = {v₁,v₂},e₂ = {v₁,v₃},e₃ = {v₂,v₃}}), and 3 demands ($\mathcal{D}$ = {d₁ = {v₁,v₂},d₂ = {v₁,v₃},d₃ = {v₂,v₃}}). Assume c₁ = 10, c₂ = 20, c₃ = 20 and h₁ = 20, h₂ = 10, h₃ = 10. Suppose that the initial lists of admissible paths for the demands contain just the direct paths $\left({\mathcal{P}}_{d_i}={\mathcal{P}}_i=\left\{p_i=\left\{e_i\right\}\right\},i=1,2,3\right)$. Apply the PG algorithm to this setting. Then consider objective (18.1a) instead of (18.16a) and see what metrics will then be used in PG. (Hint: Write down the dual problem for (18.1).)

Exercise 18.6.7. Consider a fully connected network with the set of nodes V = {v₁,v₂,…, v_V}. The set of demands corresponds to all pairs of nodes. Suppose that all but one demand values are equal to 1 and that one demand value (for, say, demand d₁ = {v₁, v₂}) is equal to 1 + ε. Suppose also that all capacity reservations c_e are equal to 1, except for the links {v₁, v₃}, {v₃,v₄},…, {v_V−1,v_V}, {v_V, v₂}} for which the capacity reservation is equal to 1 + ε. What is the optimal solution of (18.16)? Suppose we start the PG process with the single direct paths on the demand admissible path-lists and apply the PG algorithm. Will it take a long time to get the final optimal solution with z* =0 (think of large V = ∣$\mathcal{V}$∣)?

Exercise 18.6.8. Apply BD to the network from Example 1. What are the cuts corresponding to the generated inequalities. Write down the dual test (and the generated metric inequality) corresponding to (18.16) written in the N-L formulation.

Exercise 18.6.9. Write down the BB tree corresponding to the BB process executed for (18.31) and for (18.33). Compare the trees.

Exercise 18.6.10. Derive the problem dual to LP(Ω), a BB subproblem for (18.40), and in this way verify the PG rule.

Exercise 18.6.11. Execute the BD algorithm for UR on a network with two nodes, one demand between them, and two parallel links e₁,e₂ between the two nodes, with the unit costs ${\xi }_{e_1}=1,{\xi }_{e_2}=2$. The nominal demand volume is h = 3 while the demand volumes in the two considered single-link failure situations is equal to h^s = 1. What is the final set of inequalities Ω? What is the final solution in terms of y? Give graphical interpretation of the obtained feasible region defined by Benders inequalities.

Exercise 18.6.12. Derive the problem dual to RR/NSR (18.70) using the dual variables specified in formulation (18.70).

Exercise 18.6.13. Derive the BD feasibility tests and the resulting Benders inequalities for RR/NSR (18.70).

Exercise 18.6.14. Derive the pricing formulas for (18.81) and for (18.82) and see where they differ? Why BD makes no sense for UT? Why the aggregated N-L notation is not applicable to UT?

References

[1]   J. Vasseur, M. Pickavet, and P. Demeester, Network Recovery, Protection and Restoration. San Francisco: Morgan Kaufmann, 2004.

[2]   M. Pióro and D. Medhi, Routing, Flow, and Capacity Design in Communication and Computer Networks. San Francisco: Morgan Kaufmann, 2004.

[3]   W. D. Grover, Mesh-Based Survivable Networks: Options and Strategies for Optical, MPLS, SONET and ATM Networking. Upper Saddle River, NJ: Prentice Hall, 2003.

[4]   L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton, NJ: Princeton University Press, 1962.

[5]   L. Gouveia, P. Patricio, and A. Sousa, “Optimal survivable routing with a small number of hops,” in Telecommunications Modeling, Policy, and Technology, B. G. S. Raghvan and E. Wasil, Eds. Springer US, 2010.

[6]   M. Belaidouni and W. Ben-Ameur, “On the minimum cost multiple-source unsplittable flow problem,” RAIRO – Operations Research, vol. 41, no. 4, pp. 253–273, 2007.

[7]   Y. Dinitz, N. Garg, and M. Goemans, “On the single-source unsplittable flow problem,” in Proceedings 39th Annual Symposium on Foundations of Computer Science, 1998, pp. 290–299.

[8]   J. Kleinberg, “Approximation algorithms for disjoint path problems,” Ph.D. dissertation, 1996.

[9]   A. Schrijver, P. Seymour, and P. Winkler, “The ring loading problem,” SIAM Journal of Discrete Mathematics, vol. 11, no. 1, pp. 1–14, 1998.

[10]   M. R. Garey and D. R. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W. H. Freeman & Co., 1979.

[11]   M. Minoux, “Discrete cost multicommodity network optimization problems and exact solution methods,” in Annals of Operations Research, 2001, vol. 106, pp. 19–46.

[12]   R. Wessäly, “Dimensioning Survivable Capacitated NETworks,” Ph.D. dissertation, Technische Universität Berlin, April 2000.

[13]   M. Minoux, “Network synthesis and optimum network design problems: Models, solution methods and applications,” Networks, vol. 19, pp. 313–360, 1989.

[14]   B. Yaged, “Minimum cost routing for static network models,” Networks, vol. 1, pp. 139–172, 1971.

[15]   M. Minoux, Mathematical Programming: Theory and Algorithms. New York: John Wiley & Sons, 1986.

[16]   J. B. Rosen, “The gradient projection method for nonlinear programming: Part I, linear constraints,” SIAM Journal, vol. 8, pp. 181–217, 1960.

[17]  CPLEX, ILOG CPLEX 11.0 User’s Manual. ILOG, 2007.

[18]   L. Lasdon, Optimization Theory for Large Systems. New York: Macmillan, 1970.

[19]   A. Schrijver, Theory of Linear and Integer Programming. New York: John Wiley & Sons, 1986.

[20]   N. Garg and J. Könemman, “Faster and simpler algorithms for multicommodity flow and other fractional packing problems,” SIAM Journal on Computing, vol. 37, no. 2, pp. 630–652, 2007.

[21]   M. Bárász, Z. Fekete, A. Jüttner, M. Makai, and J. Szabó, “Qos aware and fair resource allocation scheme in transport networks,” in International Conference on Transport Optical Networks (ICTON), June 2006, pp. 239–242.

[22]   J. F. Benders, “Partitioning procedures for solving mixed variable programming problems,” Numerische Mathematik, vol. 4, pp. 238–252, 1962.

[23]   H. Okamura and P. Seymour, “Multicommodity flows in planar graphs,” Journal of Combinatorial Theory, vol. 31, no. 1, pp. 75–81, 1981.

[24]   M. Padberg, “Classical cuts for mixed-integer programming and branch-and-cut,” Annals of Operations Research, vol. 139, pp. 321–352, 2005.

[25]   M. Padberg, “Cutting plane methods for mixed-integer programming,” website tutorial.

[26]   L. A. Wolsey, Integer Programming. New York: John Wiley & Sons, 1998.

[27]   G. L. Nemhauser and L. A. Wolsey, Integer and Combinatorial Optimization. New York: John Wiley & Sons, 1988.

[28]   M. Grötschel, L. Lovász, and A. Schrijver, “The ellipsoid method and its consequences in combinatorial optimization,” Combinatorica, vol. 1, no. 2, pp. 169–197, 1981.

[29]   R. K. Ahuja, T. L. Magnanti, and J. B. Orlin, Network Flows: Theory, Algorithms, and Applications. Englewood Cliffs, NJ: Prentice Hall, 1993.

[30]   R. E. Gomory, An Algorithm for the Mixed Integer Problem, ser. Research Memoranda. RAND Corporation, 1960, no. RM-2597-PR.

[31]   R. E. Gomory, “An algorithm for integer solutions for integer programs,” in Recent Advances in Mathematical Programming, R. L. Graves and P. Wolfe, Eds., 1963, pp. 269–302.

[32]   A. Balakrishnan, “A dual-ascent oricedure for large-scale uncapacitated network design,” Operations Research, vol. 37, no. 5, pp. 716–740, 1989.

[33]   F. Cruz, G. Mateus, and J. M. Smith, “A branch-and-bound algorithm to slve a multi-level network optimization problem,” Journal of Mathematical Modelling and Algorithms 2, pp. 37–56, 2003.

[34]   A. D. Jongh, M. Gendreau, and M. Labbe, “Finding disjoint routes in telecommunications networks with two technologies,” Operations Research, no. 47, pp. 81–92, January 1999.

[35]   E. Gourdin, M. Labbe, and H. Yaman, “Telecommunication and location,” in Facility Location: Applications and Theory, Z. Drezner and H. Hamacher, Eds. Berlin, Heidelberg, New York: Springer-Verlag, 2002, pp. 275–305.

[36]   A. Jüttner, B. Szviatovszki, I. Mécs, and Z. Rajkó, “Lagrange relaxation based method for the QoS routing problem,” in Proceedings IEEE INFOCOM 2001, 2001, pp. 859–868.

[37]   M. Grötschel, C. Monma, and M. Stoer, Network Models, ser. Handbooks in Operations Research and Management Science. Elsevier, North-Holland, Amsterdam, 1995, vol. 7, ch. 10 : Design of Survivable Networks, pp. 617–672, m.O. Ball, T.L. Magnanti, C.L. Monma, G.L. Nemhauser (Eds.).

[38]   G. Dahl and M. Stoer, “A cutting plane algorithm for multicommodity survivable network design problems,” INFORMS Journal on Computing, vol. 10, no. 1, pp. 1–11, 1998.

[39]   D. Alevras, M. Grötschel, and R. Wessäly, “Cost-efficient network synthesis from leased lines,” Annals of Operations Research, vol. 76, pp. 1–20, 1998.

[40]   V. Gabrel, A. Knippel, and M. Minoux, “Exact solution of multicommodity network optimization problems with general step cost functions,” Operations Research Letters, vol. 25, pp. 15–23, 1999.

[41]   C. Bienstock and G. Muratore, “Strong inequalities for capacitated survivable network design problems,” Mathematical Programming, vol. A89, pp. 127–147, 2000.

[42]   C. Barnhart, E. Johnson, G. Nemhauser, G. Savelsbergh, and P. Vance, “Branch-and-price: column generation for solving huge integer programs,” Operations Research, vol. 46, no. 3, pp. 316–329, 1998.

[43]   J. Geffard, “A solving method for singly routing traffic demand in telecommunication networks,” Annales des Telecommunicationes, vol. 56, no. 3–4, pp. 140–149, 2001.

[44]   M. Belaidouni and W. Ben-Ameur, “A superadditive approach to solve the minimum cost single path routing problem: preliminary results,” In Proceedings of the 1st International Network Optimization Conference (INOC 2003), Paris, France, 2003, pp. 67–71.

[45]   K. Hoffman and M. Padberg, “LP-based combinatorial problem solving,” Annals of Operations Research, vol. 4, pp. 145–194, 1985.

[46]   E. Balas, S. Ceria, G. Cornuéjols, and N. Natraj, “Gomory cuts revisited,” Operations Research Letters, vol. 19, pp. 1–9, 1996.

[47]   L. Wolsey, “Strong formulations for mixed integer programming: A survey,” Mathematical Programming, no. 45, pp. 173–191, 1989.

[48]   E. Balas, S. Ceria, and G. Cornuejols, “Mixed 0–1 programming by lift-and-project in a branch-and-cut framework,” Management Science, no. 42, pp. 1229–1246, September 1996.

[49]   O. Günlük, “A branch-and-cut algorithm for capacitated network design,” Mathematical Programming, vol. A, no. 86, pp. 17–39, 1999.

[50]   C. Barnhart, C. Hane, E. Johnson, and G. Sigismondi, “A column generation and partitioning approach for multi-commodity flow problems,” Telecommunication Systems, vol. 3, pp. 239–258, 1995.

[51]   J. Desrosiers, Y. Dumas, M. Solomon, and F. Soumis, “Time constrained routing and scheduling,” in Operations Research and Management Science, M. Ball, T. Magnanti, C. Monma, and G. Nemhauser, Eds. Amsterdam: Elsevier Science, B. V., 1995, vol. 8, pp. 35–139.

[52]   F. Vanderbeck and L. Wolsey, “An exact algorithm for IP column generation,” Operations Research Letters, vol. 19, pp. 151–159, 1995.

[53]   C. Barnhart, C. Hane, and P. Vance, “Using branch-and-price-and-cut to solve origin-destination integer multicommodity flow problems,” Operations Research, vol. 48, no. 2, pp. 318–326, 2000.

[54]   Z. Gu, G. L. Nemhauser, and M. W. P. Savelsbergh, “Lifted cover inequalities for 0–1 integer programs: computation,” INFORMS Journal on Computing, vol. 10, pp. 427–438, 1998.

[55]   S. Kirkpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by simulated annealing,” Science, vol. 220, no. 4598, pp. 671–680, May 1983.

[56]   D. S. Johnson, C. R. Aragon, L. A. McGeoch, and C. Schevon, “Optimization by simulated annealing: An experimental evaluation,” Operations Research, vol. 39, no. 1, 1991.

[57]   J. Korst, E. Aarts, and A. Korst, Simulated Annealing and Boltzman Machines: A Stochastic Approach to Combinatorial Optimization and Neural Computing. New York: John Wiley & Sons, 1989.

[58]   D. Goldberg, Genetic Algorithms in Search, Optimization, and Machine Learning. Reading, Massachusetts: Addison-Wesley, 1989.

[59]   Z. Michalewicz, Genetic Algorithms + Data Structures = Evolution Programs. Berlin, Heidelberg, New York: Springer, III edition, 1996.

[60]   E. Mulyana and U. Killat, “Load balancing in IP networks by optimizing link weights,” in Proc. 2nd Polish-German Teletraffic Symposium, PGTS’2002, 2000, Gdansk, Poland.

[61]   F. Glover, “Tabu search fundamentals and uses,” University of Colorado at Boulder, Tech. Rep., 1994.

[62]   M. Laguna and F. Glover, “Bandwidth packing: A tabu search approach,” Management Science, vol. 39, pp. 492–500, 1993.

[63]   P. Gajowniczek and M. Pióro, “Solving an OSPF routing problem with simulated allocation,” in The first Polish-German Teletraffic Symposium (PGTS’2000), 2000, Dresden, Germany.

[64]   P. Zhou, P.-H. Yuh, and S. Sapatnekar, “Application-specific 3d network-on-chip design using simulated allocation,” in Design Automation Conference (ASP-DAC), January 2010, pp. 517–522.

[65]   M. Fischetti, F. Glover, and A. Lodi, “The feasibility pump,” Mathematical Programming, vol. 104, no. 1, pp. 91–104, 2005.

[66]   P. Raghavan and C. Thompson, “Randomized rounding: A technique for provably good algorithms and algorithmic proofs,” Combinatorica, vol. 7, no. 4, pp. 365–374, 1987.

[67]   A. Koster, A. Zymolka, M. Jäger, and R. Hülsermann, “Demand-wise shared protection for meshed optical networks,” Journal of Network and Systems Management, vol. 13, no. 1, pp. 35–55, March 2005.

[68]   R. Wessäly, S. Orlowski, A. Zymolka, A. Koster, and C. Gruber, “Demand-wise shared protection revisited: A new model for survivable network design,” in Proceedings of the 2nd International Network Optimization Conference (INOC 2005), Lisbon, Portugal, March 2005, pp. 100–105.

[69]   A. Koster and A. Zymolka, “Demand-wise shared protection and multiple failures,” in Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, April 2007.

[70]   A. Tomaszewski, M. Pióro, and M. Żotkiewicz, “On the complexity of resilient network design,” Networks: an International Journal, vol. 55, no. 2, pp. 109–118, 2010.

[71]   S. Orlowski and M. Pióro, “On the complexity of column generation in network design with path-based survivability mechanisms,” Networks, to appear in 2011.

[72]   J. Strand, A. L. Chiu, and R. Tkach, “Issues for routing in the optical layer,” IEEE Communications Magazine, pp. 81–87, 2001.

[73]   J. W. Suurballe, “Disjoint paths in a network,” Networks, vol. 4, pp. 125–145, 1974.

[74]   R. Bhandari, Survivable Networks – Algorithms for Diverse Routing. Norwell, Massachusetts: Kluwer, 1999.

[75]   J. Hu, “Diverse routing in optical mesh networks,” IEEE Trans. Com., vol. 51, no. 3, pp. 489–494, 2003.

[76]   M. Minoux and J.-Y. Serreault, “Synthese optimal d’un reseau de telecommunication avec contraintes de securite,” Annales des Telecommunications, vol. 36, no. 3–4, pp. 211–230, 1981.

[77]   K. Murakami and H. Kim, “Optimal capacity and flow assignment for selfhealing ATM networks based on line and end-to-end restoration,” IEEE/ACM Trans. on Networking, vol. 6, no. 2, pp. 207–221, April 1998.

[78]   S. Orlowski, “Local and global restoration of node and link failures in telecommunication networks,” M.Sc. thesis, Technische Universität Berlin, February 2003, http://www.zib.de/orlowski/.

[79]   J.-F. Maurras and S. Vanier, “Network synthesis under survivability constraints,” 4OR – A Quarterly Journal of Operations Research, vol. 2, no. 1, pp. 53–67, March 2004.

[80]   T. Stidsen, B. Petersen, K. Rasmussen, S. Spoorendonk, M. Zachariasen, F. Rambach, and M. Kiese, “Optimal routing with single backup path protection,” in Proceedings of the 3rd International Network Optimization Conference (INOC 2007), Spa, Belgium, 2007.

[81]   M. Żotkiewicz, M. Pióro, and A. Tomaszewski, “Complexity of resilient network optimization,” European Transactions on Telecommunications, vol. 20, no. 7, pp. 701–709, 2009.

[82]   S. Fortune, J. Hopcroft, and J. Wyllie, “The directed subgraph homeomorphism problem,” Ithaca, NY, USA, Tech. Rep., 1978.

[83]   H. P. Williams, Model Building in Mathematical Programming – Third Edition Revised. Chichester, England: John Wiley & Sons, 1993.

[84]   M. Minoux, “Optimal synthesis of a network with non-simultaneous multicommodity flow requirements,” in Studies in Graphs and Discrete Programming, P. Hansen, Ed. Amsterdam: North-Holland, 1981, pp. 269–277.

[85]   S. Orlowski, R. Wessäly, M. Pióro, and A. Tomaszewski, “SNDlib 1.0 – survivable network design library,” Networks, vol. 55, no. 3, pp. 276–286, 2010.