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 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.     

A heuristic approach for combined equipment-planning and routing in multi-layer SDH/WDM networks

The paper deals with a multi-layer network design problem for a high-speed telecommunication network based on Synchronous Digital Hierarchy (SDH) and Wavelength Division Multiplex (WDM) technology. The network has to carry a certain set of demands with the objective of minimizing the investment in the equipment. The different layers are the fiber-layer, 2.5 Gbit/s-, 10 Gbit/s- and WDM-systems. Several variations of the problem including path-protected demands and specific types of cross-connect equipment are considered. The problem is described as a mixed integer linear programming model and some results for small networks are presented. Two greedy heuristics, a random start heuristic and a GRASP-like approach are implemented to solve large real world problems.     

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.     

Heuristics for Distribution Network Design in Telecommunication

A distribution network problem arises in a lower level of an hierarchical modeling approach for telecommunication network planning. This paper describes a model and proposes a lagrangian heuristic for designing a distribution network. Our model is a complex extension of a capacitated single commodity network design problem. We are given a network containing a set of sources with maximum available supply, a set of sinks with required demands, and a set of transshipment points. We need to install adequate capacities on the arcs to route the required flow to each sink, that may be an intermediate or a terminal node of an arborescence. Capacity can only be installed in discrete levels, i.e., cables are available only in certain standard capacities. Economies of scale induce the use of a unique higher capacity cable instead of an equivalent set of lower capacity cables to cover the flow requirements of any link. A path from a source to a terminal node requires a lower flow in the measure that we are closer to the terminal node, since many nodes in the path may be intermediate sinks. On the other hand, the reduction of cable capacity levels across any path is inhibited by splicing costs. The objective is to minimize the total cost of the network, given by the sum of the arc capacity (cables) costs plus the splicing costs along the nodes. In addition to the limited supply and the node demand requirements, the model incorporates constraints on the number of cables installed on each edge and the maximum number of splices at each node. The model is a NP-hard combinatorial optimization problem because it is an extension of the Steiner problem in graphs. Moreover, the discrete levels of cable capacity and the need to consider splicing costs increase the complexity of the problem. We include some computational results of the lagrangian heuristics that works well in the practice of computer aided distribution network design.     

Algorithms for the non-bifurcated network design problem

In this paper we consider the non-bifurcated network design problem where a given set of cities must be connected by installing on a given set of links integer multiples of some base capacity so that a set of commodity demands can be routed. Each commodity flow is constrained to run through a single path along the network. The objective is to minimize the sum of capacity installation and routing costs. We present an exact algorithm and four new heuristics. The first heuristic generates an initial feasible solution, then it improves it until a necessary condition for optimality is satisfied. Two heuristics are partial enumeration methods and the last one iteratively applies a tabu search method to different initial feasible solutions. Computational results over a set of test problems from the literature show the effectiveness of the proposed algorithms.     

A column generation algorithm for tactical timber transportation planning

We present a tactical wood flow model that appears in the context of the Canadian forestry industry, and describe the implementation of a decision support system created for use by an industrial partner. In this problem, mill demands and harvested volumes of a heterogeneous set of log types are given over a multi-period planning horizon. Wood can be stored at the forest roadside before delivery at a financial cost. Rather than solve this as a network linear programme on the basis of out-and-back deliveries, we choose to model this problem as a generalization of a log-truck scheduling problem. By routing and scheduling the trucks in the resolution, this allows us to both anticipate potential backhaul opportunities for cost and fuel savings, and also minimize queuing times at log-loaders, management of which is a major concern in the industry. We model this problem as a mixed integer linear programme and solve it via column generation. The methodology is tested on several case studies.     

Network synthesis under survivability constraints

Telecommunication networks are subject to link and equipment failures. Since failures cannot be entirely avoided, networks have to be designed so as to survive failure situations. In this paper, we are interested in designing low cost survivable networks. Given point-to-point traffic demands and a cost/capacity function for each link, we aim at finding the minimum cost capacities satisfying the given demands and survivability requirements. A survivability model that reroutes interrupted traffic using all the available capacities on the network is presented and studied. In the proposed model, capacity and flow assignments for each network operating state are jointly optimized. We prove the -hardness of the optimisation problem defined by dual constraints. Then, we propose a polynomial relaxation along with a fast heuristic to compute a feasible solution of the problem from its relaxed optimal solution. Our solution approaches are tested on a set of problem instances.Received: September 2002, Revised: July 2003, AMS classification: 90C05     

Price-directive decomposition applied to routing in telecommunication networks

The telecommunication network design problem is considered to study the level of transmission network. A heuristic approach is defined to solve the combined routing-grouping problem, where the grouping one is solved by a heuristic approach. The routing problem is defined considering reliability constraints, supplementary circuits demands and a piecewise linear objective function to take into account the influence of the grouping. This last model is solved using a price-directive decomposition method, which has allowed us to solve real networks using an exact method.     

Production planning and warehouse management in supply networks with inter-facility mold transfers

This paper, considers with the problem of production capacity and warehouse management in a supply network in which inter-plant mold transfers are enabled. The supply network has a limited number of very expensive molds which can be transferred from a plant to another making it possible for each plant to produce the entire product gamut. It is assumed that warehouses in this supply network can be activated and deactivated as required, and that material transfers from a warehouse to another are also possible. The objective is to develop a capacity and warehouse management plan that satisfies the expected market demands with the lowest possible cost. A mixed integer programming model for the problem is suggested and its properties are discussed. A linear programming-based heuristic that combines Lagrangian relaxation and linear programming duality to generate lower and upper bounds for the problem is proposed. Finally, based on a designed experiment the performance of the heuristic on a set of generated test problems is reported and discussed.     

A cost operator approach to multistage location-allocation

The multistage factory-warehouse location-allocation problem is to decide on locations of warehouses and shipping amounts from the factories through the warehouses to meet customer demands in such a way that the total fixed plus variable costs are minimized. Capacity constraints at factories and warehouses are also imposed.We present a cost operator algorithm for solving this problem. The algorithm takes into account the network structure and the submodularity of the objective function. Computational results with problems taken from the literature as well as new problems are provided.     

The hub location and network design problem with fixed and variable arc costs: formulation and dual-based solution heuristic

Many air, less-than-truck load and intermodal transportation and telecommunication networks incorporate hubs in an effort to reduce total cost. These hubs function as make bulk/break bulk or consolidation/deconsolidation centres. In this paper, a new hub location and network design formulation is presented that considers the fixed costs of establishing the hubs and the arcs in the network, and the variable costs associated with the demands on the arcs. The problem is formulated as a mixed integer programming problem embedding a multi-commodity flow model. The formulation can be transformed into some previously modelled hub network design problems. We develop a dual-based heuristic that exploits the multi-commodity flow problem structure embedded in the formulation. The test results indicate that the heuristic is an effective way to solve this computationally complex problem.     

Mixed Integer Models for the Stationary Case of Gas Network Optimization

A gas network basically consists of a set of compressors and valves that are connected by pipes. The problem of gas network optimization deals with the question of how to optimize the flow of the gas and to use the compressors cost-efficiently such that all demands of the gas network are satisfied. This problem leads to a complex mixed integer nonlinear optimization problem. We describe techniques for a piece-wise linear approximation of the nonlinearities in this model resulting in a large mixed integer linear program. We study sub-polyhedra linking these piece-wise linear approximations and show that the number of vertices is computationally tractable yielding exact separation algorithms. Suitable branching strategies complementing the separation algorithms are also presented. Our computational results demonstrate the success of this approach. Received: April, 2004     

Efficient MIP formulation for optimal 1-for-N diversity coding

In the paper we consider a communication network that uses diversity coding in order to achieve reliability. Having a set of demands and a network topology we face a problem of optimal routing of the demands and backup trees, and associations between the demands and the backup trees. We present a compact mixed integer programming (MIP) formulation for the optimization problem, which proves to be more efficient than other approaches that can be found in the literature.     

A branch-and-cut algorithm for the Multiple Steiner TSP with Order constraints

The paper deals with a problem motivated by survivability issues in multilayer IP-over-WDM telecommunication networks. Given a set of traffic demands for which we know a survivable routing in the IP layer, our purpose is to look for the corresponding survivable topology in the WDM layer. The problem amounts to Multiple Steiner TSPs with order constraints. We propose an integer linear programming formulation for the problem and investigate the associated polytope. We also present new valid inequalities and discuss their facial aspect. Based on this, we devise a Branch-and-cut algorithm and present preliminary computational results.     

Mathematical modelling for optimized control of Moscow's sewer network

An algorithm for the optimized control of a branching urban head-and-gravity sewer network is proposed. The control consists in redistribution of the sewage flows between the network structural components. The algorithm is based on a mathematical model and presupposes the use of a computer. The mathematical model consists of a set of algebraic equations with the structure transporting capacities captured as constraints. The mathematical task of control is stated and solved as an optimization problem. The objective function is the minimization of total electric energy consumption over all the network pumping stations. The assumptions substantiated by practice would reduce the problem to the known problem of linear programming. The discharge through each pumping station of the considered subnetwork of Moscow's sewer network was computed using a mathematical model and was compared to the value observed under the same actual conditions. From this comparison, it was concluded that the proposed algorithm was more successful in controlling the network than was the traditional operation. The correction of the working conditions of some pumping stations of the Moscow sewer subnetwork in accordance with the precalculated time schedule, has allowed a significant decrease in the electric energy consumption for conveyance of the sewage through the network.     

Approximating the traffic grooming problem

The problem of grooming is central in studies of optical networks. In graph-theoretic terms, this can be viewed as assigning colors to the lightpaths so that at most g of them (g being the grooming factor) can share one edge. The cost of a coloring is the number of optical switches (ADMs); each lightpath uses two ADMs, one at each endpoint, and in case g lightpaths of the same wavelength enter through the same edge to one node, they can all use the same ADM (thus saving g−1 ADMs). The goal is to minimize the total number of ADMs. This problem was shown to be NP-complete for g=1 and for a general g. Exact solutions are known for some specific cases, and approximation algorithms for certain topologies exist for g=1. We present an approximation algorithm for this problem. For every value of g the running time of the algorithm is polynomial in the input size, and its approximation ratio for a wide variety of network topologies—including the ring topology—is shown to be 2lng+o(lng). This is the first approximation algorithm for the grooming problem with a general grooming factor g.     

Reserve capacity of signal-controlled road network

For a signal control road network subject to equilibrium flows, the maximum possible increase in travel demands is considered in this paper. Using the concept of reserve capacity of signal-controlled junctions, the problem of finding the maximum increase in traffic demands can be formulated as a mathematical program with equilibrium constraints (MPEC). In this paper, we present a projected gradient approach to obtain the maximum increase in travel demands based on the TRANSYT traffic model. Numerical computations are made on a grid network where good results are obtained.     

Sparsity-promoting distributed charging control for plug-in electric vehicles over distribution networks

Uncoordinated charging of plug-in electric vehicles brings a new challenge on the operation of a power system as it causes power flow fluctuations and even unacceptable load peaks. To ensure the stability of power network, plug-in charging needs to be scheduled against the base load properly. In this paper, we propose a sparsity-promoting charging control model to address this issue. In the model, the satisfaction of customers is improved through sparsity-promoting charging where the numbers of charging time slots are optimized. Dynamic feeder overload constraints are imposed in the model to avoid any unacceptable load peaks, and thus ensure the network stability. Then, a distributed solution strategy is developed to solve the problem based on the alternating direction method of multipliers (ADMM) since most of power networks are managed typically in a distributed manner. During solving process, Lagrangian duality is used to transform the original problem into an equivalent dual problem, which can be decomposed into a set of homogeneous small-scaled sub-problems. Particularly, each sub-problem either has a closed-form solution or can be solved locally by an accelerated dual gradient method. The global convergence of the proposed algorithm is also established. Finally, numerical simulations are presented to illustrate our proposed method. In contrast to traditional charging models, our sparsity-promoting charging model not only ensures the stability of power network, but also improves the satisfaction of customers.     

Optimizing the system of virtual paths by tabu search

In an asynchronous transfer mode (ATM) network, given the network topology and traffic demands, the establishment of the system of virtual paths (VPs), and the assignment of connections to them so that the network performance is optimized, entails a number of computationally hard subproblems. The optimization problem discussed here focuses on finding a system of VP routes for a given set of VP terminators and VP capacity demands. Although it has been proven that the existing random path algorithm yields the worst case time bound, the solution performance still depends highly on the number of iterations. In this paper, an exact solution procedure and a heuristic method based on a simple tabu search have been developed for optimizing the system of VPs. Computational results show that the proposed tabu search algorithm is effective in obtaining high quality solutions, and the performance of the proposed algorithm is increasingly attractive as the problem size becomes larger.