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     

Cutting plane approach for the maximum flow interdiction problem

The maximum flow interdiction is a class of leader–follower optimization problems that seek to identify the set of edges in a network whose interruption minimizes the maximum flow across the network. Particularly, maximum flow interdiction is important in assessing the vulnerability of networks to disruptions. In this paper, the problem is formulated as a bi-level mixed-integer program and an iterative cutting plane algorithm is proposed as a solution methodology. The cutting planes are implemented in a branch-and-cut approach that is computationally effective. Extensive computational results are presented on 336 different instances with varying parameters and with networks of sizes up to 50 nodes, 1200 edge, and 800 commodities. The computational results show that the proposed cutting plane approach has significant computational advantage over the direct solution of the monolithic formulation of the maximum flow interdiction problem for the majority of the tested instances.     

Computational experience with a difficult mixedinteger multicommodity flow problem

The following problem arises in the study of lightwave networks. Given a demand matrix containing amounts to be routed between corresponding nodes, we wish to design a network with certain topological features, and in this network, route all the demands, so that the maximum load (total flow) on any edge is minimized. As we show, even small instances of this combined design/routing problem are extremely intractable. We describe computational experience with a cutting plane algorithm for this problem.This research was partially supported by a Presidential Young Investigator Award and the Center for Telecommunications Research, Columbia University.Corresponding author.     

A variable neighborhood search for the network design problem with relays

Given a set of commodities to be routed over a network, the network design problem with relays involves selecting a route for each commodity and determining the location of relays where the commodities must be reprocessed at certain distance intervals. We propose a hybrid approach based on variable neighborhood search. The variable neighborhood algorithm searches for the route for each commodity and the optimal relay locations for a given set of routes are determined by an implicit enumeration algorithm. We show that dynamic programming can be used to determine the optimal relay locations for a single commodity. Dynamic programming is embedded into the implicit enumeration algorithm to solve the relay location problem optimally for multiple commodities. The special structure of the problem is leveraged for computational efficiency. In the variable neighborhood search algorithm, the routes of the current solution are perturbed and reconstructed to generate neighbor solutions using random and greedy construction heuristics. Computational experiments on three sets of problems (80 instances) show that the variable neighborhood search algorithm with optimal relay allocations outperforms all existing algorithms in the literature.     

A fast heuristic algorithm for the maximum concurrent <Emphasis Type="Italic">k</Emphasis>-splittable flow problem

In this paper, we propose a fast heuristic algorithm for the maximum concurrent k-splittable flow problem. In such an optimization problem, one is concerned with maximizing the routable demand fraction across a capacitated network, given a set of commodities and a constant k expressing the number of paths that can be used at most to route flows for each commodity. Starting from known results on the k-splittable flow problem, we design an algorithm based on a multistart randomized scheme which exploits an adapted extension of the augmenting path algorithm to produce starting solutions for our problem, which are then enhanced by means of an iterative improvement routine. The proposed algorithm has been tested on several sets of instances, and the results of an extensive experimental analysis are provided in association with a comparison to the results obtained by a different heuristic approach and an exact algorithm based on branch and bound rules.     

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.     

Network design problem with relays: A genetic algorithm with a path-based crossover and a set covering formulation

The network design problem with relays arises in telecommunications and distribution systems where the payload must be reprocessed at intermediate stations called relays on the route from its origin to its destination. In fiber-optic networks, for example, optical signals may be regenerated several times to overcome signal degradation because of attenuation and other factors. Given a network and a set of commodities, the network design problem with relays involves selecting network edges, determining a route for each commodity, and locating relays to minimize the network design cost. This paper presents a new formulation to the problem based on set covering constraints. The new formulation is used to design a genetic algorithm with a specialized crossover/mutation operator which generates a feasible path for each commodity, and the locations of relays on these paths are determined by solving the corresponding set covering problem. Computational experiments show that the proposed approach can outperform other approaches, particularly on large size problems.     

Robust Capacity Assignment in Telecommunications

In telecommunications, the demand is a key data that drives network planning. The demand exhibits considerable variability, due to customers movement and introduction of new services and products in the present competitive markets. To deal with this uncertainty, we consider capacity assignment problem in telecommunications in the framework of robust optimization proposed in Ben-Tal and Nemcrovski (Math Oper Res 23(4):769–805, 1998, MPS-SIAM series on optimization, 2001) and Kouvelis and Yu. We propose a decomposition scheme based on cutting plane methods. Some preliminary computational experiments indicate that the Elzinga–Moore cutting plane method (Elzinga and Moore in Math Program 8:134–145, 1975) can be a valuable choice. Since in some situations different possible uncertainty sets may exist, we propose a generalization of these models to cope at a time with a finite number of plausible uncertainty sets. A weight is associated with each uncertainty set to determine its relative importance or worth against another.     

Optimal multicast route packing

This paper considers the hop-constrained multicast route packing problem with a bandwidth reservation to build QoS-guaranteed multicast routing trees with a minimum installation cost. Given a set of multicast sessions, each of which has a hop limit constraint and a bandwidth requirement, the problem is to determine the set of multicast routing trees in an arc-capacitated network with the objective of minimizing the cost. For the problem, we propose a branch-and-cut-and-price algorithm, which can be viewed as a branch-and-bound method incorporating both the strong cutting plane algorithm and the column generation method. We implemented and tested the proposed algorithm on randomly generated problem instances with sizes up to 30 nodes, 570 arcs, and 10 multicast sessions. The test results show that the algorithm can obtain the optimal solution to practically sized problem instances within a reasonable time limit in most cases.     

District design for arc-routing applications

In this paper we address the problem of district design for the organisation of arc-routing activities. In particular, the focus is on operations like winter gritting and road maintenance. The problem involves how to allocate the road network edges to a set of depots with given locations. The collection of edges assigned to a facility forms a district in which routes have to be designed that start and end at the facility. Apart from the ability to support good arc routing, well-designed districts for road-maintenance operations should have the road network to be serviced connected and should define clear geographical boundaries. We present three districting heuristics and evaluate the quality of the partitions by solving capacitated arc routing problems in the districts, and by comparing the solution values with a multi-depot CARP cutting plane lower bound. Our experiments reveal that based on global information about the distribution system (ie the number of facilities or districts, the average edge demand and the vehicle capacity) and by using simple guidelines, an adequate districting policy may be selected.     

An interior-point Benders based branch-and-cut algorithm for mixed integer programs

We present an interior-point branch-and-cut algorithm for structured integer programs based on Benders decomposition and the analytic center cutting plane method (ACCPM). We show that the ACCPM based Benders cuts are both pareto-optimal and valid for any node of the branch-and-bound tree. The valid cuts are added to a pool of cuts that is used to warm-start the solution of the nodes after branching. The algorithm is tested on two classes of problems: the capacitated facility location problem and the multicommodity capacitated fixed charge network design problem. For the capacitated facility location problem, the proposed approach was on average 2.5 times faster than Benders-branch-and-cut and 11 times faster than classical Benders decomposition. For the multicommodity capacitated fixed charge network design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the majority of the tested instances.     

Designing a two-echelon distribution network under demand uncertainty

This paper proposes a comprehensive methodology for the stochastic multi-period two-echelon distribution network design problem (2E-DDP) where product flows to ship-to-points are directed from an upper layer of primary warehouses to distribution platforms (DPs) before being transported to the ship-to-points. A temporal hierarchy characterizes the design level dealing with DP location and capacity decisions, as well as the operational level involving transportation decisions as origin-destination flows. These design decisions must be calibrated to minimize the expected distribution cost associated with the two-echelon transportation schema on this network under stochastic demand. We consider a multi-period planning horizon where demand varies dynamically from one planning period to the next. Thus, the design of the two-echelon distribution network under uncertain customer demand gives rise to a complex multi-stage decisional problem. Given the strategic structure of the problem, we introduce alternative modeling approaches based on two-stage stochastic programming with recourse. We solve the resulting models using a Benders decomposition approach. The size of the scenario set is tuned using the sample average approximation (SAA) approach. Then, a scenario-based evaluation procedure is introduced to post-evaluate the design solutions obtained. We conduct extensive computational experiments based on several types of instances to validate the proposed models and assess the efficiency of the solution approaches. The evaluation of the quality of the stochastic solution underlines the impact of uncertainty in the two-echelon distribution network design problem (2E-DDP).     

Greedy primal-dual algorithm for dynamic resource allocation in complex networks

In Stolyar (Queueing Systems 50 (2005) 401–457) a dynamic control strategy, called greedy primal-dual (GPD) algorithm, was introduced for the problem of maximizing queueing network utility subject to stability of the queues, and was proved to be (asymptotically) optimal. (The network utility is a concave function of the average rates at which the network generates several “commodities.”) Underlying the control problem of Stolyar (Queueing Systems 50 (2005) 401–457) is a convex optimization problem subject to a set of linear constraints. In this paper we introduce a generalized GPD algorithm, which applies to the network control problem with additional convex (possibly non-linear) constraints on the average commodity rates. The underlying optimization problem in this case is a convex problem subject to convex constraints. We prove asymptotic optimality of the generalized GPD algorithm. We illustrate key features and applications of the algorithm on simple examples. AMS Subject Classifications: 90B15 · 90C25 · 60K25 · 68M12     

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.     

A cutting plane procedure for the travelling salesman problem on road networks

A cutting plane algorithm for the exact solution of the symmetric travelling salesman problem (TSP) is proposed. The real tours on a usually incomplete road network, which are in general non-Hamiltonian, are characterized directly by an integer linear programming model. The algorithm generates special cutting planes for this model. Computational results for real road networks with up to 292 visiting places are reported, as well as for classical problems of the literature with up to 120 cities. Some of the latter problems have been solved for the first time with a pure cutting plane approach.     

Comparing performance of feedforward neural nets and K-means for cluster-based market segmentation

We compare the performance of a specifically designed feedforward artificial neural network with one layer of hidden units to the K-means clustering technique in solving the problem of cluster-based market segmentation. The data set analyzed consists of usages of brands (product category: household cleaners) in different usage situations. The proposed feedforward neural network model results in a two segment solution that is confirmed by appropriate tests. On the other hand, the K-means algorithm fails in discovering any somewhat stronger cluster structure. Classification of respondents on the basis of external criteria is better for the neural network solution. We also demonstrate the managerial interpretability of the network results.     

Cutting plane algorithms for solving a stochastic edge-partition problem

We consider the edge-partition problem, which is a graph theoretic problem arising in the design of Synchronous Optical Networks. The deterministic edge-partition problem considers an undirected graph with weighted edges, and simultaneously assigns nodes and edges to subgraphs such that each edge appears in exactly one subgraph, and such that no edge is assigned to a subgraph unless both of its incident nodes are also assigned to that subgraph. Additionally, there are limitations on the number of nodes and on the sum of edge weights that can be assigned to each subgraph. In this paper, we consider a stochastic version of the edge-partition problem in which we assign nodes to subgraphs in a first stage, realize a set of edge weights from a finite set of alternatives, and then assign edges to subgraphs. We first prescribe a two-stage cutting plane approach with integer variables in both stages, and examine computational difficulties associated with the proposed cutting planes. As an alternative, we prescribe a hybrid integer programming/constraint programming algorithm capable of solving a suite of test instances within practical computational limits.     

An algorithm for single shift scheduling of hierarchical workforce

This paper presents an optimal algorithm for single shift scheduling of hierarchical workforce in seven-day-a-week industries. There are many categories of workers; their capabilities are arranged hierarchically. The objective is to arrive at the most economical mix of categories of employees satisfying the pattern of demand for employees and desired work characteristics. The demand for employees varies from one category to the other and for each category the demand during weekdays is fixed and is different from that of weekends. The desired work characteristics are: (i) each employee must be given two days off every week including at least a proportion A out of every B weekends off and (ii) each employee can have at most 5 working shifts between any two offdays. The algorithm provides a computational scheme for arriving at the minimum workforce size comprising the most economical mix of categories of employees for this demand context and a new technique for characterizing the problem to achieve feasible assignment of employees to shifts.     

Solving real-world linear ordering problems using a primal-dual interior point cutting plane method

Cutting plane methods require the solution of a sequence of linear programs, where the solution to one provides a warm start to the next. A cutting plane algorithm for solving the linear ordering problem is described. This algorithm uses the primaldual interior point method to solve the linear programming relaxations. A point which is a good warm start for a simplex-based cutting plane algorithm is generally not a good starting point for an interior point method. Techniques used to improve the warm start include attempting to identify cutting planes early and storing an old feasible point, which is used to help recenter when cutting planes are added. Computational results are described for some real-world problems; the algorithm appears to be competitive with a simplex-based cutting plane algorithm.Research partially supported by ONR Grant number N00014-90-J-1714.