Gamma-Robust Network Design for Mixed-Line-Rate-Planning of Optical Networks

abstract not available

Exploiting cutting planes in practice: {0,1/2}-cuts as an example

abstract not available

Robust Metric Inequalities for Network Design under Demand Uncertainty

abstract not available

Robust Metric Inequalities for Network Design under Demand Uncertainty

abstract not available

Robust Metric Inequalities

abstract not available

Generalized Metric Inequalities for Robust Network Design

abstract not available

Survivable Network Design under Demand Uncertainty

abstract not available

The Recoverable Robust Knapsack Problem with Gamma-Scenarios

abstract not available

The Recoverable Robust Bandwith Packing Problem

abstract not available

An Integrated Model for Survivable Network Design under Demand Uncertainty

The reliability of a communication network is measured by its ability to cope with the failure of network elements and the fluctuations in traffic volume. Survivable network design is concerned with the installation of (link) capacities such that a routing exists in every considered failure scenario. Robust network design deals with network dimensioning under demand uncertainty.

In this talk, we present a new combined network design model incorporating both survivability and robustness. The network resources cover demand uncertainties as well as single link failures. Computational experiments using real-life traffic data show that (i) significant cost savings compared to a straight-forward 1+1 protected robust network design can be achieved, whereas (ii) the loss of robustness by such designs is negligible.

Robust Design of Telecommunication Networks

abstract not available

Cutset Inequalities for Robust Network Design

Robust optimization is an emerging approach in integer programming taking data uncertainty into account. Recently, the adjustable $\Gamma$-robustness approach of Bertsimas and Sim (2003,2004) has been applied to network design problems. In this talk, we consider this so-called $\Gamma$-robust network design problem. We investigate its polyhedral structure and present robust versions of the cutset inequalities as well as computational results on their effectiveness.

On the robustness of optimal network designs

Robust optimization is an emerging field in telecommunication network design which takes future traffic uncertainty into account. This yields optimal robust network designs which are optimal for all traffic realizations within a pre-defined set of uncertainty. In 2003, Bertsimas and Sim have introduced an adjustable uncertainty set for general optimization problems preserving the computational complexity of the original non-robust problem. Recently, Koster et al. have applied this approach to network design problems.

In this talk, we consider this so-called $\Gamma$-robust network design problem. We investigate the importance of statistical input data analysis to determine reasonable parameter settings for robust network planning. Using detailed real-life traffic measurements of two backbone networks (Abilene and GEANT), we determine optimal robust network designs for 495 design problems each. Afterwards, we evaluate the realized robustness (i. e., the ratio of supported traffic matrices) w. r. t. the planning data and a larger set of historical data to simulate future traffic.

$\Gamma$-Robust Network Design: Models, Valid Inequalities, and Computations

abstract not available

Network Design under Demand Uncertainties - A Case Study on the Abilene and GEANT network data

Traffic in communication networks fluctuates heavily over time. Thus, to avoid capacity bottlenecks, operators highly overestimate the traffic volume during network planning. Often, expensive safety factors of 300% or more are applied to the link capacity.

In this talk, we consider telecommunication network design under demand uncertainty, adopting the robust optimization approach of Bertsimas and Sim (2003, 2004). This deterministic approach provides an adjustable uncertainty and preserves the computational complexity of the original non-robust problem. Recently, Koster et al. (2010) have applied this approach to network design problems.

Using detailed real-life traffic measurements of the US Internet 2 (Abilene) and the pan-European research and education network (GEANT) backbone networks, we present an extensive computational case study for this so-called $\Gamma$-robust network design problem. For each network, we determine optimal robust network designs for 495 different parameter settings. Afterwards, we evaluate the realized robustness of these designs with respect to (i) the traffic measurements used as planning data, and (ii) a larger set of traffic measurements including the planning data to simulate uncertain future traffic. We give different robust measurements (e. g., the percentage of supported traffic matrices, or the percentage of congested links) and compare the corresponding realized robustnesses.

We report on the importance of statistical input data analysis to determine reasonable parameter settings for robust network planning. Further, by determining pareto-optimal parameter settings based on the price of robustness and the evaluated realized robustness, our analysis provides practical decision support criteria for network planners.

Cutset Inequalities for Robust Network Design

abstract not available

{0,1/2}-Chvatal-Gomory cuts

abstract not available

Robust Network Design under Traffic Uncertainties

abstract not available

Towards Robust Network Design using Integer Linear Programming Techniques

abstract not available

Submodular Bandwidth Packing

Traffic in telecommunication networks fluctuates heavily over time. To design and operate such a network efficiently this demand uncertainty has to be taken into account. We propose the use of submodular functions to describe the bandwidth consumption on single links. The corresponding problem of routing as many profitable demands as possible taking into account the link capacities is called the submodular bandwidth packing problem. As the bandwidth consumption is described by a submodular function this problem includes a submodular knapsack problem for each link.

In telecommunication network design the future traffic demands are unknown when the installation of link capacity and the routing of traffic have to be decided. Instead, estimations are used based on historical data and statistical assumptions. One straight-forward and crude approach is to estimate the future average demand and apply a safety factor on top of the predicted total traffic to cope with demand fluctuations. Safety factors of 300% and more have been used by large telecommunication companies. Hence, the more connection requests are routed across the same link, the more bandwidth is reserved for traffic fluctuations. Unfortunately, this leads to highly over-estimated values leaving most of the available bandwidth unused. This is clearly neither cost-efficient nor resource exploiting as it is very unlikely that all requests have high bandwidth requirements at the same time. This property of communication requests is known as statistical multiplexing.

Clearly, a better approach to estimate the future demand has to be made. This leads to robust network optimization where the uncertain demand is implicitly given by a so-called uncertainty set. The goal of robust optimization is to provide optimal solutions which are feasible for all demand realizations within this uncertainty set. Too large uncertainty sets yield so-called over-conservative solutions where too many opposing worst-cases are taken into account. This results in a significant decrease in the objective value of the optimal robust solution compared to the non-robust one. In 2003 Bertsimas and Sim introduced a new approach to robustness which tackles the problem of over-conservative solutions without increasing the level of complexity of the robust model. The uncertainty set they use is parameterized by a value $\Gamma$ which allows to adjust the level of robustness and hence the danger of conservatism. For every uncertain value (e. g., demand) the estimated average is given as well as a deviation value. This yields a symmetric interval in which the actual traffic demand is assumed. In addition, only at most $\Gamma$ many demands are allowed to be off their average values (i. e., either at at most the lower or upper interval bound). In recent years many theoretical and practical studies of this robust setting have been introduced: in Belotti et al. (2000, 2008) modeled the concept of statistical multiplexing for MPLS and multi-layer networks by provision of two values for every demand: the mean and the peak bandwidth requirements. By modeling the demand requirements as independent stochastic processes with low probability of requiring the peak bandwidth, they assume that at most one peak occurs ($\Gamma$=1). In 2009, Klopfenstein and Nace studied the $\Gamma$-robustness approach applied to the knapsack problem in the context of Bandwidth Packing.

In this talk we propose the modeling of uncertainty set by submodular functions which models the assumption that the total bandwidth requirement of a set of demands may be less than the sum of the individual requirements. Hence, this approach generalizes the previously mentioned approaches, in particular the $\Gamma$ uncertainty set. We illustrate this concept by the single path routing problem with fixed link capacities which corresponds to the bandwidth packing problem. In this case the bandwidth capacity on a link is described by the submodular knapsack polytope which has recently been studied by Atamtürk and Narayanan (2009).

Our polyhedral studies of the submodular knapsack polytope extend those by Atamtürk and Narayanan. We adapt results for the well-known knapsack polytope (cf. Balas (1975)) and generalize them to the submodular knapsack polytope. This includes the generalization of (1,k)-configurations (cf. Padberg (1980)) and weight inequalities to the submodular case giving also conditions when these valid inequalities are facet-defining for the submodular knapsack polytope. In addition, we give some examples of explicit submodular functions suitable to model statistical multiplexing. Further we discuss submodular functions implicitly given by historical data. Finally, computational studies are presented for solving the submodular bandwidth packing problem. On the one hand, we compare the effect of different submodular functions. On the other hand, we study the impact of the various classes of valid inequalities derived by the study of the submodular knapsack polytope.

Robust Network Optimization with Submodular Functions

abstract not available

Multi-commodity Single Path Routing with Submodular Bandwidth Consumption

abstract not available

Improving state-of-the-art ILP-solvers by separating {0,1/2}-cuts for general integer linear programs

abstract not available

Algorithmen zur Separierung von {0,1/2}-Schnitten

abstract not available

Separation of {0,1/2}-Chvatal-Gomory cuts in general integer programs

abstract not available