Survivable capacitated network design problem: new formulation and Lagrangean relaxation

This work is focused on the analysis of the survivable capacitated network design problem. This problem can be stated as follows: Given a supply network with point-to-point traffic demands, specific survivability requirements, a set of available capacity ranges and their corresponding discrete costs for each arc, find minimum cost capacity expansions such that these demands can be met even if a network component fails. Solving this problem consists of selecting the links and their capacity, as well as the routings for each demand in every failure situation. This type of problem can be shown to be NP-hard. A new linear mixed-integer mathematical programming formulation is presented. An effective solution procedure based on Lagrangean relaxation is developed. Comparison heuristics and improvement heuristics are also described. Computational results using these procedures on different sizes of randomly generated networks are reported.     

Designing Least-Cost Survivable Wireless Backhaul Networks

This paper presents a new heuristic algorithm for designing least-cost telecommunications networks to carry cell site traffic to wireless switches while meeting survivability, capacity, and technical compatibility constraints. This requires solving the following combinatorial optimization problems simultaneously: (1) Select a least-cost subset of locations (network nodes) as hubs where traffic is to be aggregated and switched, and choose the type of hub (high-capacity DS3 vs. lower-capacity DS1 hub) for each location; (2) Optimally assign traffic from other nodes to these hubs, so that the traffic entering the network at these nodes is routed to the assigned hubs while respecting capacity constraints on the links and routing-diversity constraints on the hubs to assure survivability; and (3) Optimally choose the types of links to be used in interconnecting the nodes and hubs based on the capacities and costs associated with each link type. Each of these optimization problems must be solved while accounting for its impacts on the other two. This paper introduces a short term Tabu Search (STTS) meta-heuristic, with embedded knapsack and network flow sub-problems, that has proved highly effective in designing such backhaul networks for carrying personal communications services (PCS) traffic. It solves problems that are challenging for conventional branch-and-bound solvers in minutes instead of hours and finds lower-cost solutions. Applied to real-world network design problems, the heuristic has successfully identified designs that save over 20% compared to the best previously known designs.     

Design of partially survivable networks for cellular telecommunication systems

In cellular networks, cells are connected to the mobile telephone switching office (MTSO) directly or via hubs. It may also be desirable for some cells to split their traffic to two or more hubs for partial survivability in the case of equipment failures; such cells are said to have a diversity requirement greater than one. Assuming that hubs are connected to the MTSO via self-healing rings, as is common in current cellular implementations, the objective is to find the assignment of cells to hubs – including the MTSO – that meets demand as well as survivability requirements at minimum cost. With the increasing use of fiber for high capacity backbone transmission, networks have become sparser, and the consequences of link failures much more serious. Hence network survivability has taken on added urgency. Our paper models this problem in the context of cellular networks.     

Multi-service multi-facility network design under uncertainty

The problem of designing high speed networks using different modules of link capacities, in the same model, in order to meet uncertain demands obtained from different probability distribution functions (PDF) is a very hard and challenging real network design problem. The novelty of the new model, compared to previous ones, is to allow installing more than one module per link having equal or different capacities. Moreover, the scenarios of traffic can be generated, according to practical observations, from the main classes of uncertain demands (multi-service) simulated from different PDFs, including heavy tailed ones. These classes of traffic are considered simultaneously for the scenario generation, different from related works in the literature that use only one probability distribution function to simulate the scenarios of traffic. In this work we present the problem formulation and report computational results using branch-and-bound and L-shaped decomposition solution approaches. We consider in the same model up to three different types of modular capacities (multi-facility), since it seems that using more than this can lead to an intractable model. The objective is to minimize penalty (in case of unmet demands) and investment costs. We obtain confidence intervals (with 95% of covering rate) on the expected optimal solution value for the resulting two-stage stochastic integer-modular problem and discuss when they are meaningful. Numerical experiments show that our model can handle up to medium real size instances.     

Constraint Generation for Network Reliability Problems

This paper presents a constraint generation approach to the network reliability problem of adding spare capacity at minimum cost that allows the traffic on a failed link to be rerouted to its destination. Any number of non-simultaneous link failures can be part of the requirements on the spare capacity. The key result is a necessary and sufficient condition for a multicommodity flow to exist, which is derived in the appendix. Computational results on large numbers of random networks are presented.     

Routing and capacity assignment in backbone communication networks under time varying traffic conditions

This paper studies the problem of assigning capacities to links in a backbone communication network and determining the routes used by messages for all communicating node pairs in the network under time varying traffic conditions. The best routes are to be chosen from among all possible routes in the network. Tradeoffs between link costs and response time to users are achieved by specifying an upper limit on the average link queueing delay in the network. The goal is to minimize total link fixed and variable costs. The topology of the network and the end-to-end traffic requirements during the different busy-hours are assumed to be known. The problem is formulated as a mathematical programming model. An efficient solution procedure based on a Lagrangian relaxation of the problem is developed. The results of extensive computational experiments across a variety of networks are reported. These results indicate that the solution procedure is effective for a wide range of traffic loads and cost structures.     

Telecommunication Network Capacity Design for Uncertain Demand

The expansion of telecommunication services has increased the number of users sharing network resources. When a given service is highly demanded, some demands may be unmet due to the limited capacity of the network links. Moreover, for such demands, telecommunication operators should pay penalty costs. To avoid rejecting demands, we can install more capacities in the existing network. In this paper we report experiments on the network capacity design for uncertain demand in telecommunication networks with integer link capacities. We use Poisson demands with bandwidths given by normal or log-normal distribution functions. The expectation function is evaluated using a predetermined set of realizations of the random parameter. We model this problem as a two-stage mixed integer program, which is solved using a stochastic subgradient procedure, the Barahona's volume approach and the Benders decomposition.     

Discrete Cost Multicommodity Network Optimization Problems and Exact Solution Methods

We first introduce a generic model for discrete cost multicommodity network optimization, together with several variants relevant to telecommunication networks such as: the case where discrete node cost functions (accounting for switching equipment) have to be included in the objective; the case where survivability constraints with respect to single-link and/or single-node failure have to be taken into account. An overview of existing exact solution methods is presented, both for special cases (such as the so-called single-facility and two-facility network loading problems) and for the general case where arbitrary step-increasing link cost-functions are considered. The basic discrete cost multicommodity flow problem (DCMCF) as well as its variant with survivability constraints (DCSMCF) are addressed. Several possible directions for improvement or future investigations are mentioned in the concluding section.     

Designing Least-Cost Nonblocking Broadband Networks

Integrated network technologies, such as ATM, support multimedia applications with vastly different bandwidth needs, connection request rates, and holding patterns. Due to their high level of flexibility and communication rates approaching several gigabits per second, the classical network planning techniques, which rely heavily on statistical analysis, are less relevant to this new generation of networks. In this paper, we propose a new model for broadband networks and investigate the question of their optimal topology from a worst-case performance point of view. Our model is more flexible and realistic than others in the literature, and our worst-case bounds are among the first in this area. Our results include a proof of intractability for some simple versions of the network design problem and efficient approximation algorithms for designing nonblocking networks of provably small cost. More specifically, assuming some mild global traffic constraints, we show that a minimum-cost nonblockingstarnetwork achieves near-optimal cost; the cost ratio is at most 2 if switch source and sink capacities are symmetric and at most 3 when the total source and sink capacities are balanced. In the special case of unit link costs, we can show that a star network is indeed the cheapest nonblocking network.     

A problem identification taxonomy for classification and automated formulation of multiple objective linear programming models

This paper considers a network supply problem in which flows between any pair of nodes are possible. It is assumed that users place a value on connection to other users in the network, and (possibly) on access to an external source. Cost on each link is an arbitrary concave function of link capacity. The objective is to study coalitional stability in this situation, when collections of flows can be served by competing suppliers. In contrast to other network games, this approach focuses on the cost of serving flows rather than the cost of attaching nodes to the network. The network is said to be stable if the derived cost function is supportable. Supportable cost functions, defined by Sharkey and Telser [9], are cost functions for which there exists a price vector which covers total cost, and simultaneously deters entry at any lower output by a rival firm with the same cost function. If the minimal cost network includes a link between every pair of nodes, then the cost function is shown to be supportable. In the special case in which link cost is independent of capacity, the cost function is also supportable. The paper also considers Steiner networks in which new nodes may be created in order to minimize total cost, or in which access may be obtained at more than one source location. When link costs are independent of capacity in such a network, it is argued that the cost function is approximately supportable in a well defined sense.     

A polyhedral approach to multicommodity survivable network design

Summary. The design of cost-efficient networks satisfying certain survivability constraints is of major concern to the telecommunications industry. In this paper we study a problem of extending the capacity of a network by discrete steps as cheaply as possible, such that the given traffic demand can be accommodated even when a single edge or node in the network fails. We derive valid and nonredundant inequalities for the polyhedron of capacity design variables, by exploiting its relationship to connectivity network design and knapsack-like subproblems. A cutting plane algorithm and heuristics for the problem are described, and preliminary computational results are reported. Received August 26, 1993 / Revised version received February 1994     

Using ACCPM in a simplicial decomposition algorithm for the traffic assignment problem

The purpose of the traffic assignment problem is to obtain a traffic flow pattern given a set of origin-destination travel demands and flow dependent link performance functions of a road network. In the general case, the traffic assignment problem can be formulated as a variational inequality, and several algorithms have been devised for its efficient solution. In this work we propose a new approach that combines two existing procedures: the master problem of a simplicial decomposition algorithm is solved through the analytic center cutting plane method. Four variants are considered for solving the master problem. The third and fourth ones, which heuristically compute an appropriate initial point, provided the best results. The computational experience reported in the solution of real large-scale diagonal and difficult asymmetric problems—including a subset of the transportation networks of Madrid and Barcelona—show the effectiveness of the approach.     

Capacitated transit assignment with loading priorities

In a transit network involving vehicles with rigid capacities, we advocate the use of strategies for describing consumer behavior. At each boarding node, a user sorts the transit lines in decreasing order of preference, and boards the first vehicle in this list whose residual capacity is nonzero. Since a users position in the queue varies from day to day, the delay experienced is stochastic. This leads to an equilibrium problem where, at a solution, users are assigned to strategies that minimize their expected delay. This situation is formulated as a variational inequality, whose cost mapping is discontinuous and strongly asymmetric, due to the priority of current passengers over incoming users. We prove that the solution set is nonempty and provide numerical results obtained by an efficient solution algorithm.This research was supported in part by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds pour la formation de chercheurs et laide à la recherche (FCAR).Mathematics Subject Classification (2000):20E28, 20G40, 20C20Accepted: December 20, 2003     

Topological design of wide area communication networks

This paper develops a model for designing a backbone network. It assumes the location of the backbone nodes, the traffic between the backbone nodes and the link capacities are given. It determines the links to be included in the design and the routes used by the origin destination pairs. The objective is to obtain the least cost design where the system costs consist of connection costs and queueing costs. The connection costs depend on link capacity and queueing costs are incurred by users due to the limited capacity of links. The Lagrangian relaxation embedded in a subgradient optimization procedure is used to obtain lower bounds on the optimal solution of the problem. A heuristic based on the Lagrangian relaxation is developed to generate feasible solutions.     

A hybrid approach for optimal design of signalized road network

For a signalized road network with expansions of link capacity, the maximum possible increase in travel demands is considered while total delays for travelers are minimized. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum possible increase in travel demand and determining optimal link capacity expansions can be formulated as optimization programs. In this paper, we present a new solution approach for simultaneously solving the maximum increase in travel demands and minimizing total delays of travelers. A projected Quasi-Newton method is proposed to effectively solve this problem to the KKT points. Numerical computations and comparisons are made on real data signal-controlled networks where obtained results outperform traditional methods.     

Integer programming models for the routing and spectrum allocation problem

One of the most promising solutions to deal with huge data traffic demands in large communication networks is given by flexible optical networking, in particular the flexible grid (flexgrid) technology specified in the ITU-T standard G.694.1. In this specification, the frequency spectrum of an optical fiber link is divided into narrow frequency slots. Any sequence of consecutive slots can be used as a simple channel, and such a channel can be switched in the network nodes to create a lightpath. In this kind of networks, the problem of establishing lightpaths for a set of end-to-end demands that compete for spectrum resources is called the routing and spectrum allocation problem (RSA). Due to its relevance, this problem has been intensively studied in the last couple of years. It has been shown to be NP-hard (Christodoulopoulos et al. in IEEE J Lightw Technol 29(9):1354–1366, 2011; Wang et al. in IEEE J Opt Commun Netw 4(11):906–917, 2012) and several models and formulations have been proposed, leading to different solution approaches. In this work, we explore integer programming models for RSA, analyzing their effectiveness over known instances. We resort to several modeling techniques, to find natural formulations of this problem. Since integer programming techniques are known to provide successful practical approaches for several combinatorial optimization problems, the aim of this work is to explore a similar approach for RSA.     

Hop Constrained Network Design Problem with Partial Survivability

This paper studies the hop constrained network design problem with partial survivability, namely, given an undirected network, a set of point-to-point demands (commodities), and transmission link costs, identify two node disjoint paths for each demand (commodity) to minimize the total costs subject to the constraints that each demand is routed and traverses at most a specified number of links (or hops) on both the paths.A mathematical programming formulation of the problem is presented and an efficient solution procedure based on the linear programming relaxation is developed. Extensive computational results across a number of networks are reported. These results indicate that the solution procedure is effective for a wide range of problem sizes.     

Solving survivable two-layer network design problems by metric inequalities

We address the problem of designing a multi-layer network with survivability requirements. We are given a two-layer network: the lower layer represents the potential physical connections that can be activated, the upper layer is made of logical connections that can be set up using physical links. We are given origin-destination demands (commodities) to be routed at the upper layer. We are also given a set of failure scenarios and, for every scenario, an associated subset of commodities. The goal is to install minimum cost integer capacities on the links of both layers in order to ensure that the commodities can be routed simultaneously on the network. In addition, in every failure scenario the routing of the associated commodities must be guaranteed. We consider two variants of the problem and develop a branch-and-cut scheme based on the capacity formulation. Computational results on instances derived from the SNDLib for single node failure scenarios are discussed.     

Telecommunication Link Restoration Planning with Multiple Facility Types

To ensure uninterrupted service, telecommunication networks contain excess (spare) capacity for rerouting (restoring) traffic in the event of a link failure. We study the NP-hard capacity planning problem of economically installing spare capacity on a network to permit link restoration of steady-state traffic. We present a planning model that incorporates multiple facility types, and develop optimization-based heuristic solution methods based on solving a linear programming relaxation and minimum cost network flow subproblems. We establish bounds on the performance of the algorithms, and discuss problem instances that nearly achieve these worst-case bounds. In tests on three real-world problems and numerous randomly-generated problems containing up to 50 nodes and 150 edges, the heuristics provide good solutions (often within 0.5% of optimality) to problems with single facility type, in equivalent or less time than methods from the literature. For multi-facility problems, the gap between our heuristic solution values and the linear programming bounds are larger. However, for small graphs, we show that the optimal linear programming value does not provide a tight bound on the optimal integer value, and our heuristic solutions are closer to optimality than implied by the gaps.     

Location of speed-up subnetworks

Let a network with edge weights, a set of point-to-point transportation requests and a factor \(\alpha \) be given. Our goal is to design a subnetwork of given length along which transportation costs are reduced by \(\alpha \) . This reduces the costs of the network traffic which will choose to use edges of the new subnetwork if this is the more efficient option. Our goal is to design the subnetwork in such a way that the worst-case cost of all routing requests is minimized. The problem occurs in many applications, among others in transportation networks, in backbone, information, communication, or electricity networks. We classify the problem according to the types of the given network and of the network to be established. We are able to clarify the complexity status in all considered cases. It turns out that finding an optimal subtree in a tree already is NP-hard. We therefore further investigate this case and propose results and a solution approach.