Refine
Language
- English (9)
Keywords
- mixed integer programming (2)
- multi-layer network design (2)
- SNDlib (1)
- branch-and-cut (1)
- capacitated network design (1)
- cutset-polyhedra (1)
- cutting planes (1)
- energy efficiency (1)
- flow-cutset inequalities (1)
- heuristics (1)
Project
- B3 (9)
Application Area
- B (9)
We investigate the impact of link and path restoration
on the cost of telecommunication networks. The surprising
result is the following: the cost of an optimal network configuration
is almost independent of the restoration concept if (i)
the installation of network elements (ADMs, DXCs, or routers)
and interface cards, (ii) link capacities, and (iii) working and
restoration routings are simultaneously optimized.
We present a mixed-integer programming model which integrates
all these decisions. Using a branch-and-cut algorithm
(with column generation to deal with all potential routing paths),
we solve structurally different real-world problem instances and
show that the cost of optimal solutions is almost independent of
the used restoration concept.
In addition, we optimize spare capacities for given shortest
working paths which are predetermined with respect to different
link metrics. In comparison to simultaneous optimization of
working and restoration routings, it turns out that this approach
does not allow to obtain predictably good results.
We investigate the impact of hop-limited routing
paths on the total cost of a telecommunication network. For
different survivability settings (no survivability, link and path
restoration), the optimal network cost without restrictions on
the admissible path set is compared to the results obtained with
two strategies to impose hop limits on routing paths.
Based on optimal solutions for 10 real-world based problem
instances, we show that hop limits may lead to an unpredictable
raise in total network cost - even with large hop limits. The total
network cost with a hop limit of 7 hops for all demands can be up
to 25% higher than without restrictions on the admissible path
set. With our second strategy, which imposes demand-dependent
hop limits based on the shortest hop count, we obtain similar
results. This indicates that column generation techniques should
be applied to deal with all admissible paths.
We consider the design of a logical network topology, together with node hardware, link capacities, and a survivable routing of demands. In addition to all single node failures, the routing must also survive multiple logical link failures caused by single failures in the underlying physical network. Furthermore, the number of logical links supported by a physical link is bounded. We propose an integer linear programming model for this design problem, together with a branch-and-cut based solution approach combined with column generation. The model and algorithm are tested on three real-world test instances, and preliminary results are given.
This paper deals with MIP-based primal heuristics to be used within a branch-and-cut approach for solving multi-layer telecommunication network design problems. Based on a mixed-integer programming formulation for two network layers, we present three heuristics for solving important subproblems, two of which solve a sub-MIP. On multi-layer planning instances with many parallel logical links, we show the effectiveness of our heuristics in finding good solutions early in the branch-and-cut search tree.
In this article we study capacitated network design problems. We unify and extend polyhedral results for directed, bidirected and undirected link capacity models. Based on valid inequalities for a network cut we show that regardless of the link capacity model, facets of the polyhedra associated with such a cut translate to facets of the original network design polyhedra if the two subgraphs defined by the network cut are (strongly) connected. Our investigation of the facial structure of the cutset polyhedra allows to complement existing polyhedral results for the three variants by presenting facet-defining flow-cutset inequalities in a unifying way. In addition, we present a new class of facet-defining inequalities, showing as well that flow-cutset inequalities alone do not suffice to give a complete description for single-commodity, single-module cutset polyhedra in the bidirected and undirected case – in contrast to a known result for the directed case. The practical importance of the theoretical investigations is highlighted in an extensive computational study on 27 instances from the Survivable Network Design Library (SNDlib).
This survey concerns optimization problems arising in the design of survivable communication networks. It turns out that such problems can be modeled in a natural way as non-compact linear programming formulations based on multicommodity flow network models. These non-compact formulations involve an exponential number of path flow variables, and therefore require column generation to be solved to optimality. We consider several path-based survivability mechanisms and present results, both known and new, on the complexity of the corresponding column
generation problems (called the pricing problems). We discuss results for the case of the single link (or node) failures
scenarios, and extend the considerations to multiple link failures. Further, we classify the design problems corresponding to different survivability mechanisms according to the structure of their pricing problem. Finally, we show that almost all encountered pricing problems are hard to solve for scenarios admitting multiple failures.
We estimate potential energy savings in IP-over-WDM networks achieved by switching off router line cards in low-demand hours. We compare three approaches to react on dynamics in the IP traffic over time, FUFL,
DUFL and DUDL. They provide different levels of freedom in adjusting the routing of lightpaths in the WDM layer and the routing of demands in the IP layer. Using MILP models based on realistic network topologies and node architectures as well as realistic demands, power, and cost values, we show that already a simple monitoring of the lightpath utilization in order to deactivate empty line cards (FUFL) brings substantial
benefits. The most significant savings, however, are achieved by rerouting traffic in the IP layer (DUFL), which allows emptying and deactivating lightpaths together with the corresponding line cards. A
sophisticated reoptimization of the virtual topologies and the routing in the optical domain for every demand scenario (DUDL) yields nearly no additional profits in the considered networks.
We present an integer linear programming model for the design of multi-layer telecommunication
networks which are based on connection-oriented routing protocols. The formulation integrates hardware,
capacity, routing, and grooming decisions in any number of network layers. Practical hardware
restrictions and cost can accurately be taken into account.
We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost
installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context,
helping to increase the dual bound and to reduce the optimality gaps.