Single-commodity network design with random edge capacities

This paper examines the single-commodity network design problem with stochastic edge capacities. We characterize the structures of the optimal designs and compare with the deterministic counterparts. We do this partly to understand what constitutes robust network designs, but also to construct a heuristic for the stochastic problem, leading to optimality gaps of about 10%. In our view, that is a rather good result for problems that otherwise cannot be solved at all.     

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 capacity scaling heuristic for the multicommodity capacitated network design problem

In this paper, we propose a capacity scaling heuristic using a column generation and row generation technique to address the multicommodity capacitated network design problem. The capacity scaling heuristic is an approximate iterative solution method for capacitated network problems based on changing arc capacities, which depend on flow volumes on the arcs. By combining a column and row generation technique and a strong formulation including forcing constraints, this heuristic derives high quality results, and computational effort can be reduced considerably. The capacity scaling heuristic offers one of the best current results among approximate solution algorithms designed to address the multicommodity capacitated network design problem.     

Survivable network design under optimal and heuristic interdiction scenarios

We examine the problem of building or fortifying a network to defend against enemy attacks in various scenarios. In particular, we examine the case in which an enemy can destroy any portion of any arc that a designer constructs on the network, subject to some interdiction budget. This problem takes the form of a three-level, two-player game, in which the designer acts first to construct a network and transmit an initial set of flows through the network. The enemy acts next to destroy a set of constructed arcs in the designer’s network, and the designer acts last to transmit a final set of flows in the network. Most studies of this nature assume that the enemy will act optimally; however, in real-world scenarios one cannot necessarily assume rationality on the part of the enemy. Hence, we prescribe optimal network design algorithms for three different profiles of enemy action: an enemy destroying arcs based on capacities, based on initial flows, or acting optimally to minimize our maximum profits obtained from transmitting flows.     

The multi-layered network design problem

We address the problem of designing a network built on several layers. This problem occurs in practical applications but has not been studied extensively from the point of view of global optimisation, since the problem of designing a single-layered network is complex. An example of an application is the design of a virtual network (Internet Protocol) built on a sparse optical transport network.     

Hierarchical approach for survivable network design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.     

Incremental network design with shortest paths

We introduce a class of incremental network design problems focused on investigating the optimal choice and timing of network expansions. We concentrate on an incremental network design problem with shortest paths. We investigate structural properties of optimal solutions, show that the simplest variant is NP-hard, analyze the worst-case performance of natural greedy heuristics, derive a 4-approximation algorithm, and conduct a small computational study.     

Breakout local search for the Steiner tree problem with revenue,budget and hop constraints

The Steiner tree problem (STP) is one of the most popular combinatorial optimization problems with various practical applications. In this paper, we propose a Breakout Local Search (BLS) algorithm for an important generalization of the STP: the Steiner tree problem with revenue, budget and hop constraints (STPRBH), which consists of determining a subtree of a given undirected graph which maximizes the collected revenues, subject to both budget and hop constraints. Starting from a probabilistically constructed initial solution, BLS uses a Neighborhood Search (NS) procedure based on several specifically designed move operators for local optimization, and employs an adaptive diversification strategy to escape from local optima. The diversification mechanism is implemented by adaptive perturbations, guided by dedicated information of discovered high-quality solutions. Computational results based on 240 benchmarks show that BLS produces competitive results with respect to several previous approaches. For the 56 most challenging instances with unknown optimal results, BLS succeeds in improving 49 and matching one best known results within reasonable time. For the 184 instances which have been solved to optimality, BLS can also match 167 optimal results.     

Optimal double-resource assignment for the robust design problem in multistate computer networks

This paper proposes a novel approach to get the exact optimal double-resource assignment for the robust design problem in multistate computer networks. A multistate computer network consists of links and vertices where both kinds of resources may have several states due to failure, partial failure or maintenance. Therefore, each link (vertex) in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a multistate computer network (MCN) is to search for the minimum capacity assignment of each link and vertex such that the network still survived even under both kinds of failures. However, how to optimally assign the capacity to each resource is not an easy task. This paper proposes an efficient approach to do such assignment and illustrates the efficiency of the proposed approach by some numerical examples.     

An optimal capacity assignment for the robust design problem in capacitated flow networks

This paper proposes an exact algorithm to solve the robust design problem in a capacitated flow network in which each edge has several possible capacities. A capacitated flow network is popular in our daily life. For example, the computer network, the power transmission network, or even the supply chain network are capacitated flow networks. In practice, such network may suffer failure, partial failure or maintenance. Therefore, each edge in the network should be assigned sufficient capacity to keep the network functioning normally. The robust design problem (RDP) in a capacitated flow network is to search for the minimum capacity assignment of each edge such that the network still survived even under the edge’s failure. However, how to optimally assign the capacity to each edge is not an easy task. Although this kind of problem was known of NP-hard, this paper proposes an efficient exact algorithm to search for the optimal solutions for such a network and illustrates the efficiency of the proposed algorithm by numerical examples.     

Complexity of some parametric integer and network programming problems

Two examples of parametric cost programming problems—one in network programming and one in NP-hard 0-1 programming—are given; in each case, the number of breakpoints in the optimal cost curve is exponential in the square root of the number of variables in the problem. This research is partially supported by the Air Force Office of Scientic Research. Air Force Number AFOSR-78-3646     

A large neighborhood search heuristic for the longest common subsequence problem

Given a set S={S ¹,…,S ^k } of finite strings, the k-Longest Common Subsequence Problem (k-LCSP) seeks a string L ^* of maximum length such that L ^* is a subsequence of each S ⁱ for i=1,…,k. This paper presents a large neighborhood search technique that provides quality solutions to large k-LCSP instances. This heuristic runs in linear time in both the length of the sequences and the number of sequences. Some computational results are provided.     

General network design: A unified view of combined location and network design problems

This paper presents a unified framework for the general network design problem which encompasses several classical problems involving combined location and network design decisions. In some of these problems the service demand relates users and facilities, whereas in other cases the service demand relates pairs of users between them, and facilities are used to consolidate and re-route flows between users. Problems of this type arise in the design of transportation and telecommunication systems and include well-known problems such as location-network design problems, hub location problems, extensive facility location problems, tree-star location problems and cycle-star location problems, among others. Relevant modeling aspects, alternative formulations and possible algorithmic strategies are presented and analyzed.     

Hybrid meta-heuristic algorithms for solving network design problem

Network design problem has been, and is, an important problem in transportation. Following an earlier effort in designing a meta-heuristic search technique by an ant system, this paper attempts to hybridize this concept with other meta-heuristic concepts such as genetic algorithm, simulated annealing, and tabu search. Seven hybrids have been devised and tested on the network of Sioux Falls. It has been observed that the hybrids are more effective to solve the network design problem than the base ant system. Application of the hybrid containing all four concepts on a real network of a city with over 2 million population has also proved to be more effective than the base network, in the sense of finding better solutions sooner.     

On the complexity of the one-terminal network design problem

The one-terminal network design problem considered here is to select a subset of the set of potential edges so as to minimize the sum of construction cost plus expected usage cost with discounting. We distinguish between easy and hard cases of this problem.     

A 2-approximation algorithm for the network substitution problem

The network substitution problem is to substitute an existing network for a new network so that to minimize the cost of exploiting the existing network during the period when the new network is being constructed. We show that this problem is NP-hard, and propose a 2-approximation algorithm for solving it.     

An efficient approximation algorithm for the survivable network design problem

The survivable network design problem (SNDP) is to construct a minimum-cost subgraph satisfying certain given edge-connectivity requirements. The first polynomial-time approximation algorithm was given by Williamson et al. (Combinatorica 15 (1995) 435–454). This paper gives an improved version that is more efficient. Consider a graph ofn vertices and connectivity requirements that are at mostk. Both algorithms find a solution that is within a factor 2k – 1 of optimal fork 2 and a factor 2 of optimal fork = 1. Our algorithm improves the time from O(k ³n⁴) to O ). Our algorithm shares features with those of Williamson et al. (Combinatorica 15 (1995) 435–454) but also differs from it at a high level, necessitating a different analysis of correctness and accuracy; our analysis is based on a combinatorial characterization of the redundant edges. Several other ideas are introduced to gain efficiency. These include a generalization of Padberg and Rao's characterization of minimum odd cuts, use of a representation of all minimum (s, t) cuts in a network, and a new priority queue system. The latter also improves the efficiency of the approximation algorithm of Goemans and Williamson (SIAM Journal on Computing 24 (1995) 296–317) for constrained forest problems such as minimum-weight matching, generalized Steiner trees and others. © 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.A preliminary version of this paper has appeared in the Proceedings of the Third Mathematical Programming Society Conference on Integer Programming and Combinatorial Optimization, 1993, pp. 57–74.Research supported in part by NSF Grant No. CCR-9215199 and AT & T Bell Laboratories.Research supported in part by Air Force contracts AFOSR-89-0271 and F49620-92-J-0125 and DARPA contracts N00014-89-J-1988 and N00014-92-1799.This research was performed while the author was a graduate student at MIT. Research supported by an NSF Graduate Fellowship, Air Force contract F49620-92-J-0125, DARPA contracts N00014-89-J-1988 and N00014-92-J-1799, and AT & T Bell Laboratories.     

LP extreme points and cuts for the fixed-charge network design problem

Many design decisions in transporation, communication, and manufacturing planning can be modeled as problems of routing multiple commodities between various origin and destination nodes of a directed network. Each arc of the network is uncapacitated and carries a fixed charge as well as a cost per unit of flow. We refer to the general problem of selecting a subset of arcs and routing the required multi-commodity flows along the chosen arcs at a minimum total cost as the fixed charge network design problem. This paper focuses on strenghthening the linear programming relaxation of a path-flow formulation for this problem. The considerable success achieved by researchers in solving many related design problems with algorithms that use strong linear programming-based lower bounds motivates this study. We first develop a convenient characterization of fractional extreme points for the network design linear programming relaxation. An auxiliary graph introduced for this characterization also serves to generate two families of cuts that exclude some fractional solutions without eliminating any feasible integer solutions. We discuss a separation procedure for one class of inequalities and demonstrate that many of our results generalize known properties of the plant location problem. Supported in part by grant number ECS-831-6224 of the National Science Foundation.     

A note on the subadditive network design problem

We study approximation algorithms for generalized network design where the cost of an edge depends on the identities of the demands using it (as a monotone subadditive function). Our main result is that even a very special case of this problem cannot be approximated to within a factor 2^log1−ε|D| if D is the set of demands.