Koster A., Munoz X. Graphs and Algorithms in Communication Networks

Подождите немного. Документ загружается.

3 Two-Layer Network Design 97

into the link at one end, extracted at the other end, and cannot be accessed inside.

The actual physical representation of a logical link usually does not matter to its end

nodes.

As this work was motivated by a project with Nokia-Siemens Networks (NSN)

on SDH/WDM network planning, we will use that setting to explain our model and

algorithm, which are actually in use at NSN in the strategic planning process now.

But the concepts are more general and can, at least with slight modiﬁcations, be

applied to many technological settings.

In our SDH/WDM scenario, a lightpath can be equipped with different band-

widths, and lower-rate trafﬁc demands have to be routed via the lightpaths without

exceeding their capacities. A demand may be 1+1-protected, i.e., twice the demand

value must be routed such that in the case of any single physical link or node failure,

at least the demand value survives. To terminate a lightpath, a sufﬁciently large elec-

trical cross-connect (EXC) must be installed at both end nodes. The EXC converts

the wavelength signal into an electrical SDH signal and extracts lower-rate trafﬁc

from it. The latter is either terminated at that node or recombined with other trafﬁc

to form new wavelength signals which are sent out on other lightpaths. This process

is called grooming. The optimization goal is to minimize total installation cost.

Like in any other publication where an integrated two-layer model is actually

used for computations, we do not explicitly assign wavelengths to the lightpaths

because ﬁnding a suitable wavelength assignment is an extremely hard problem

on its own. Instead, we make sure that the maximum number of lightpaths on each

ﬁber is not exceeded, and propose to solve the wavelength assignment and converter

installation problem in a subsequent step, as successfully done in [19]. It has been

shown in [20] that such an approach causes at most a marginal increase in the overall

installation cost in practical instances.

Already, the optimal design of a single layer network is a challenging task that

has been considered by many research groups; see for instance [4, 14, 28] and ref-

erences therein. A branch-and-cut algorithm enhanced by user-deﬁned, problem-

speciﬁc cutting planes has been proved to be a very successful solution approach

in this context. The combined optimization of two layers signiﬁcantly increases the

complexity of the planning task. In most previous publications, mixed-integer pro-

gramming techniques have been used for designing a logical layer with respect to

a ﬁxed physical layer [5, 11, 12] or for solving an integrated two-layer planning

problem with some simplifying assumptions, like no node hardware or wavelength

granularity demands [15, 21]. Knippel and Lardeux [17] and Fortz and Poss [13]

have modeled the two-layer network design problem using metric inequalities for

both network layers. Recently, Belotti et al. [6] have used a Lagrangean approach

for a two-layer network design problem with simultaneous mean demand values

and nonsimultaneous peak demand values. Raghavan and Stanojevic [29] consider

the case where all logical links are eligible and develop a branch-and-price algo-

rithm with respect to a ﬁxed physical layer for the case of unprotected demands and

one facility on the logical links. Orlowski et al. [25] present several heuristics for a

two-layer network design problem, which solve a restricted version of the original

problem as a sub-MIP within a branch-and-cut framework. In a recent paper [18],

98 S. Orlowski et al.

we have presented a mathematical model for the described planning problem with

a predeﬁned set of logical links. It includes node hardware, several bit rates on

the logical links, and survivability against physical node and link failures. To our

knowledge, this was the ﬁrst time that so many practically relevant side constraints,

and in particular, multilayer survivability, were taken into account in an integrated

two-layer planning model.

We have solved this model using a branch-and-cut approach with problem-

speciﬁc preprocessing, user-deﬁned cutting planes, and heuristics. This chapter

combines results from [25] and [18]. In addition to the preprocessing and cutting

planes presented in [18], we have also adapted the MIP-based primal heuristics

from [25] to the full planning problem and call them at various places during the

branch-and-cut tree. The algorithm is tested on several network instances provided

by Nokia Siemens Networks. The paper is structured as follows. In Section 3.2, we

present and discuss our mixed-integer programming model. Section 3.3 describes

our MIP-based primal heuristics used within the branch-and-cut algorithm. In Sec-

tion 3.4, we describe the cutting planes used and state some known results about

their strength. Computational results are provided in Section 3.5. We conclude with

Section 3.6.

We assume that that reader has basic knowledge of mixed-integer programming

and branch-and-cut techniques; good introductions to this topic are [24] and [31].

3.2 Mathematical Model

3.2.1 Mixed-Integer Programming Model

We will now introduce the mixed-integer programming (MIP) model on which our

cutting planes are based. Afterwards, we will describe some basic preprocessing

steps that we have applied to strengthen the formulation.

Parameters

The physical network is represented by an undirected graph (V, E). The logical net-

work is modeled by an undirected graph (V,L) with the same set of nodes and a ﬁxed

set L of admissible logical links. Each logical link represents an undirected path in

the physical network. In consequence, any two nodes i, j ∈V may be connected by

many parallel logical links corresponding to different physical paths, collected in

the set L

= L

. Looped logical links are forbidden, i.e., L

= /0 for all i ∈ V .Let

(i)=∪

j∈V

be the set of all logical links starting or ending at i. Eventually,

⊆ L denotes the set of logical links containing edge e ∈ E, and likewise, L

⊆ L

refers to the set of logical links containing node i ∈V as an inner node.

3 Two-Layer Network Design 99

We consider different types of capacities for logical links, physical links, and

nodes. Each logical link  ∈ L has a set M



of available capacity modules, each of

them with a cost of



∈ R

and a base capacity (bit rate) of C



∈ Z

that can be

installed on  in integer multiples. Similarly, every node i ∈V has a set M

of node

modules (representing different EXC types), at most one of which may be installed

at i. Module m ∈ M

provides a switching capacity of C

∈ Z

(e.g., in bits per

second) at a cost of

∈R

.Onaphysicallinke ∈ E, a ﬁber may be installed at a

cost of

∈ R

. Each ﬁber supports up to B ∈Z

lightpaths.

For the routing part, a set H of undirected point-to-point communication de-

mands is given, which may be protected or unprotected. Protected demands are

expected to survive any single physical node or link failure, whereas unprotected de-

mands are allowed to fail. Each demand h ∈ H has a source node, a target node, and

a demand value d

to be routed between these two nodes. Without loss of generality,

we may assume the demands to be directed in an arbitrary way. For 1+1-protected

demands, d

refers to twice the original demand value that would have to be routed

if the demand were unprotected. Adding constraints that limit the amount of ﬂow

for a protected commodity through a node or physical link to

guarantees that at

least the original demand survives any single physical link or node failure. This sur-

vivability model, called diversiﬁcation [3], is a slight relaxation of 1+1-protection,

but its solutions can often be transformed into 1+1-solutions.

From the demands, two sets K

and K

of protected and unprotected commodi-

ties are constructed, where K = K

∪K

denotes the set of all commodities. With

every commodity k ∈K and every node i ∈V , a net demand value d

∈ Z is associ-

ated such that

∑

i∈V

= 0. Every protected commodity k ∈ K

consists of a single

1+1-protected point-to-point demand, i.e., d

= 0 only for the source and target node

of the demand. In contrast, unprotected commodities k ∈ K

are derived by aggre-

gating unprotected point-to-point demands at a common source node. Summarizing,

every commodity k ∈K has a unique source node s

∈V . Unprotected commodities

may have several target nodes, whereas protected commodities have a unique target

∈V . The (undirected) emanating demand of a node i ∈V , i.e., the total demand

value starting or ending at node i, is given by d

∑

k∈K

|. The demand value d

of a commodity is deﬁned as the demand for k emanating from its source node, i.e.,

= d

> 0. Notice that for protected commodities, this value is twice the requested

bandwidth to ensure survivability.

Variables

The model comprises four classes of variables representing the ﬂow and different

capacity types. First, for a logical link  ∈ L and a module m ∈ M



, the logical link

capacity variable y



∈ Z

represents the number of modules of type m installed on

. For a physical link e ∈ E, the binary physical link capacity variable z

∈{0,1}

indicates whether e is equipped with a ﬁber or not. Similarly, for a node i ∈V and

a node module m ∈ M

, the binary variable x

∈{0, 1} denotes whether module m

is installed at node i or not. Eventually, the routing of the commodities is modeled

100 S. Orlowski et al.

by ﬂow variables. In order to model diversiﬁcation of protected commodities, we

need fractional ﬂow variables f

,ij

, f

, ji

∈ R

representing the ﬂow for commodity

k ∈ K on logical link  ∈ L

directed from i to j and from j to i, respectively. For

notational convenience, f



= f

,ij

+ f

, ji

denotes the total ﬂow for k ∈ K on  ∈ L

in both directions.

In our model, a ﬂow variable f

,ij

for commodity k and logical link  ∈ L

omitted if any of the following conditions is satisﬁed: (i) j = s

, (ii) k ∈ K

and

i = t

, and (iii) k ∈ K

and  contains the source or target node of k as an inner

node. The ﬁrst two types of variables represent ﬂow into the unique source node or

out of the unique target node of a protected commodity. They are not generated in

order to reduce cycle ﬂows in the edge-ﬂow formulation. For aggregated unprotected

commodities, we have to allow ﬂow from one target node to another, and thus ﬂow

out of target nodes. The third type of variable would allow ﬂow to be routed through

an end node u of a protected commodity without terminating at that node, and then

back to u on another logical link. As such routings are not desired in practice, we

exclude ﬂow variables whose logical link contains an end node of the corresponding

commodity as an inner node. Again, in the unprotected case, such variables have to

be admitted because commodities may consist of several aggregated demands.

Objective and Constraints

The objective and constraints of our MIP model read as follows:

min

∑

i∈V

∑

m∈M

∑

∈L

∑

m∈M



∑

e∈E

(3.1a)

s.t.

∑

j∈V

∑

∈L

( f

,ij

− f

, ji

)=d

∀i ∈V, ∀k ∈K (3.1b)

∑

m∈M



−

∑

k∈K



≥ 0 ∀ ∈ L (3.1c)

∑

∈L



∑

∈

(i)



≤

∀i ∈V, ∀k ∈K

(3.1d)

,s

≤

∀k ∈ K

 = e = {s

}

(3.1e)

∑

m∈M

≤ 1 ∀i ∈V (3.1f)

∑

m∈M

−

∑

∈

(i)

∑

m∈M



≥ d

∀i ∈V (3.1g)

−

∑

∈L

∑

m∈M



≥ 0 ∀e ∈E (3.1h)

,ij

, f

, ji

∈ R

, y



∈ Z

, x

∈{0,1} (3.1i)

3 Two-Layer Network Design 101

The objective (3.1a) aims at minimizing the total installation cost. The ﬂow conser-

vation (3.1b) and capacity constraints (3.1c) describe a multi-commodity ﬂow and

modular capacity assignment problem on the logical layer. For protected commodi-

ties, the ﬂow diversiﬁcation constraints (3.1d) restrict the ﬂow through an interme-

diate node to half the demand value. In this way, the original demand is guaranteed

to survive single node failures as well as single physical link failures, except for the

direct physical link between source s

and target t

. This exception is covered by the

variable bound (3.1e). In fact, to reduce cycle ﬂows in the LP, we set an upper bound

of d

and

on all ﬂow variables for unprotected and protected commodities, re-

spectively. The generalized upper bound constraints (3.1f) guarantee that at most

one node module is installed at each node. The node switching capacity constraints

(3.1g) ensure that the switching capacity of the network element installed at a node

is sufﬁcient for all trafﬁc that can potentially be switched at that node. Since all

trafﬁc is counted twice, it is compared to twice the installed node capacity. Finally,

the physical link capacity constraints (3.1h) make sure that the maximum number

of modules on a physical link is not exceeded, and set the physical link capacity

variables to 1 whenever a physical link is used.

Discussion of the Model

Several design choices in our model deserve a brief discussion. First, we assume a

fractional multi-commodity ﬂow on the logical layer although SDH requires an inte-

ger routing in practice. This is motivated by our observations that in good solutions,

the routing is often nearly integer even if this is not required, and that relaxing the

integrality conditions on the ﬂow variables signiﬁcantly reduces the computation

times. If an integral routing is indispensable, it can be obtained in a postprocessing

step, which usually does not deteriorate the cost of the solutions very much if prop-

erly done. Notice that the lower bound computed for the model with fractional ﬂow

can also be used to assess the quality of the postprocessed integral solutions.

Second, we assume a predeﬁned set of logical links for computational reasons.

Considering all possible physical paths as logical links in combination with the prac-

tical side constraints and the survivability requirements would ask for a branch-and-

cut-and-price approach with a nontrivial pricing problem already in the root node.

Such an approach can only be successful if the problem with a limited set of logi-

cal links can be solved efﬁciently. For a branch-and-price approach that deals with

all possible logical links on a ﬁxed physical layer using a simpliﬁed model without

survivability, the reader is referred to [29].

3.2.2 Preprocessing

To strengthen the formulation, we now describe the preprocessing steps applied to

the model presented in Section 3.2. In addition to these steps, we have used probing

102 S. Orlowski et al.

techniques to set further bounds on variables [30]. Probing is nowadays part of any

modern MIP solver like SCIP [1] or CPLEX [16].

• If a physical link e ∈E has zero ﬁber cost, the variable z

can be ﬁxed to 1.

• Obviously, at least the emanating demand must be switched at every node. Con-

sequently, an EXC must be installed at every demand end node i ∈V , so the node

GUB inequality (3.1f) can be changed to an equality at such nodes:

∑

m∈M

= 1.

This strengthens the LP relaxation signiﬁcantly.

• For the same reason, node modules whose switching capacity is smaller than

the emanating demand at a node cannot be installed at that node. Consequently,

if C

< d

for some node i ∈ V and a node module m ∈ M

, the corresponding

variable x

can be removed from the MIP formulation. This often leads to more

integral x

variables in the LP relaxation and to better LP values, especially when

combined with the previous rule.

• Two bounds on logical link module variables can be derived from the ﬁber ca-

pacity bounds and the total demand in the network. Both bounds are usually not

tight in the LP relaxation, but may help the MIP solver in deriving further rela-

tions between the variables to strengthen other bounds.

First, as no more than B channels can be routed through a given physical link

e ∈ E, every logical link module variable can be bounded by B. Second, the

amount of ﬂow that can be routed through any logical link  ∈ L is bounded

by the total unprotected demand plus half the protected demand in the network

(except for undesired cycle ﬂow in the edge-ﬂow formulation). Consequently,

the number of modules of type m ∈ M



that possibly needs to be installed on  is

bounded by



≤







∑

h∈H

∑

h∈H



• Sometimes it is evident that in any optimal solution, a small link module will not

be installed more than a given number of times on a link because a larger module

provides the same or more capacity at a lower price. More precisely, consider a

link  ∈ L and two of its capacity modules m

∈ M



such that C



≤C



. If

the relation

r =



≤



holds, then at most r modules of type m

will be installed in any optimal solu-

tion because r modules of type m

incur the same cost as one unit of type m

but the latter provides the same or more capacity. Furthermore, even if equal-

ity holds in the above relation, one large module is preferable to several smaller

ones because every module uses one physical channel, independently of its bit

rate. Consequently, the variable bound y



≤



r −1



can be added to the for-

mulation. It cuts off some non-optimal solutions and maybe some optimal ones

3 Two-Layer Network Design 103

(if equality holds), but always leaves at least one optimal solution if one exists.

Notice that the value



r −1



is exactly r −1ifr is integer, and





otherwise.

3.3 MIP-Based Heuristics Within Branch-and-Cut

We solve the mixed-integer programming formulation using the branch-and-cut

framework SCIP 0.90 [2]. In addition, we have implemented several heuristics to

construct feasible network conﬁgurations based on integer or fractional solutions.

At every node of the search tree, SCIP generates cutting planes and calls both our

heuristics and some of its own to identify feasible integer solutions. If a new best

solution is identiﬁed, it is added to SCIP’s solution pool such that it can be used by

other heuristics which take feasible solutions as a basis for their work. We will now

describe our heuristics and their use within the branch-and-cut framework.

Our MIP-based heuristics address two major subtasks. G

ROOMCAPMIP and

ROOMCAPHEUR solve the grooming and capacity installation subproblem for a

given routing exactly and heuristically, respectively, whereas R

EROUTINGMIP com-

putes a routing within certain link capacities, trying to reduce the required capacity

at the same time. By construction, the MIP-based heuristics can easily be adapted

to include additional planning requirements, such as node hardware or survivability

constraints.

3.3.1 Computing Capacities over a Given Flow

GROOMCAPMIP

The GROOMCAPMIP procedure addresses the grooming and capacity assignment

subproblem for a given routing by solving a MIP. For a logical link  ∈ L

,let

∗



∑

k∈K

∑

∈L

( f

,ij

+ f

, ji

) be the total ﬂow on  in an integer or LP solution (after

removing possible cycle ﬂows). We construct a sub-MIP of the original formulation

(3.1a)–(3.1i) that contains logical and physical capacity variables but no routing

information:

min



(3.1a) subject to (3.1f)−(3.1h),

∑

m∈M



≥



∗





∀ ∈L, z



∈Z



Using SCIP’s branch-and-cut algorithm, this sub-MIP is solved as an improvement

heuristic every time a new best solution is identiﬁed, trying to reduce link capacity

cost based on the given routing. As the focus of the sub-MIP is on feasible solutions

and not on the lower bound, we disable cut generation and expensive heuristics in

the subproblem and impose a node limit of 20,000 and a stall node limit of 10,000,

i.e., the sub-MIP is stopped if either a total of 20,000 branch-and-cut nodes has

104 S. Orlowski et al.

been computed or if the primal bound could not be improved during the last 10,000

nodes.

ROOMCAPHEUR

In contrast to the GROOMCAPMIP algorithm, which solves the grooming and ca-

pacity assignment problem exactly, the fast and simple G

ROOMCAPHEUR proce-

dure addresses this problem heuristically by decomposition. Again, let f

∗



be the

total ﬂow on logical link  ∈ L in an integer or LP solution after removing cycle

ﬂows. Installing capacities on  at minimum cost with a lower bound of f

∗



can be

formulated as an integer knapsack problem:

min



∑

m∈M



subject to

∑

m∈M



≥



∗





, y



∈ Z



For



= 1 this knapsack problem is trivial to solve. Otherwise, it is solved heuris-

tically for each logical link  ∈ L using a greedy algorithm, taking the maximum

capacity of each physical link into account. In a second step, node capacities are in-

stalled as much as needed for the given link capacities (if possible). As this heuristic

runs very fast, we call it at every branch-and-cut node to construct feasible solutions

from the current LP solution.

3.3.2 Rerouting Flow to Reduce Capacities

REROUTINGMIP

The REROUTINGMIP heuristic determines a routing together with a minimum-cost

capacity installation subject to an upper capacity bound on the logical links. More

precisely, given an upper bound U

∗



on the capacity of each logical link  ∈ L,

EROUTINGMIP solves the following problem using SCIP’s branch-and-cut ca-

pabilities:

min



(3.1a) subject to (3.1b)–(3.1i),

∑

m∈M



≤U

∗



∀ ∈ L



With small U

∗



, this problem is much easier to solve than the original problem. By

setting U

∗



to the total capacity of link  ∈ L in an integer solution, REROUTINGMIP

can be used as an improvement algorithm that tries to reduce capacities by rerouting

ﬂow. This generalizes the rerouting step in the iterative heuristics proposed in [15,

21], making it independent of the ordering of the demands.

We employ R

EROUTINGMIP not as an improvement heuristic but as a construc-

tion algorithm. Given some value

≥ 1 and an LP solution with total logical link

3 Two-Layer Network Design 105

capacities y

∗



∑

m∈M



∗

, we solve the above sub-MIP with U

∗



:= C





∗



where C

is the smallest module capacity installable on . If the installable capaci-

ties form a divisibility chain (which is often the case in practical applications), U

∗



is the smallest installable integer capacity greater than or equal to

∗



. Obviously,

a higher value of

augments the solution space of the subproblem, allowing for

better solutions but also making it harder to solve. Experimenting with different

values, we found that

= 2 often allowed us to quickly determine good solutions

in the sub-MIP.

As the R

EROUTINGMIP algorithm consumes much more time than the other

heuristics, we restrict its application to the LP solution at the end of the branch-and-

cut root node. In the sub-MIP (as well as in the original problem), good solutions

are often found within the ﬁrst few branch-and-bound nodes, whereas much time

is spent afterwards on proving optimality of the solution. Hence, we disable cut

generation and expensive heuristics in the subproblem, and we impose a node limit

of 10,000 nodes and a stall node limit of 5,000 nodes. To increase the chance of

ﬁnding good solutions, we also apply the G

ROOMCAPHEUR and GROOMCAPMIP

algorithms within the sub-MIP, which tends to improve the overall solution quality.

3.4 Cutting Planes

Backed by theoretical results of polyhedral combinatorics, cutting plane procedures

have proved to be a feasible approach to improve the performance of mixed-integer

programming solvers for many single-layer network design problems. In this sec-

tion we show how an appropriate selection of these inequalities can be adapted to

our problem setting. Their separation within a branch-and-cut algorithm, i.e., the

problem to ﬁnd a violated inequality that cuts off a fractional LP solution or to de-

termine that no such inequality exists, is only brieﬂy summarized here; details can

be found in [18].

3.4.1 Cutting Planes on the Logical Layer

On the logical layer, we consider cutset inequalities and ﬂow-cutset inequalities.

These cutting planes have, for instance, been studied in [4, 8, 10, 22, 28] for a variety

of network settings (e.g., directed, undirected, and bidirected link models, single or

multiple capacity modules) and have been successfully used within branch-and-cut

algorithms for capacitated single-layer network design problems [7, 8, 14, 28].

To be precise, the inequalities on the logical layer are valid for the polyhedron P

deﬁned by the multi-commodity ﬂow constraints (3.1b) and the capacity constraints

(3.1c). That is,

P = conv



( f ,y) ∈ R

×Z

| ( f,y) satisﬁes (3.1b),(3.1c)



106 S. Orlowski et al.

where n

= 2|K||L| and n

∑

∈L



|. As P is a relaxation of the model discussed

in Section 3.2, the inequalities are also valid for that model.

We introduce the following notation. For any subset /0 = S ⊂V of nodes, let



 ∈ L | ∈ L

, i ∈ S, j ∈V \S



be the set of logical links having exactly one end node in S. Furthermore, deﬁne d

∑

i∈S

≥0 to be the total demand value to be routed over the cut L

for commodity

k ∈K. By reversing the direction of demands and exchanging the corresponding ﬂow

variables, we may w. l. o. g. assume that d

≥ 0 for all k ∈ K (i.e., the commodity is

directed from S to V \S, or the end nodes of k are either all in S or all in V \S). This

reduction is done implicitly in our code. More generally, let d

∑

k∈Q

denote

the total demand value to be routed over the cut L

for all commodities k ∈Q.

Mixed-Integer Rounding (MIR)

In order to derive strong valid inequalities on the logical layer we aggregate model

inequalities and apply a strengthening of the resulting base inequalities; this is

known as mixed-integer rounding (MIR). It exploits the integrality of the capac-

ity variables. Further details on mixed-integer rounding can be found in [23], for

instance.

Let a,c,d ∈ R with c > 0 and

/∈ Z, and a

= max(0, a). Furthermore, let

a,c

= a −c(





−1) > 0

be the remainder of the division of a by c if

/∈ Z, and c otherwise. Now assume

that d/c /∈Z and consider the subadditive MIR functions

d,c

: R → R : a →





d,c

−(r

d,c

−r

a,c

)

and

d,c

(a)=lim

t0

d,c

(at)

= a

. Given any valid inequality for our problem, ap-

plying F

d,c

and

d,c

to the integer and continuous variables, respectively, yields an-

other valid inequality [24]. Moreover, the resulting coefﬁcients are integral (if a, c,

and d are integral) and |F

d,c

(a)|,|

d,c

(a)|≤|a|, as shown in [28]. Both features are

desirable from a numerical point of view. For more details and explanations see [28].

Cutset Inequalities

Let L

be a cut in the logical network as deﬁned above. Obviously, the total capacity

on the cut links L

must be sufﬁcient to accommodate the total demand over the cut:

∑

∈L

∑

m∈M



≥ d

. (3.2)