I

All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.

Similar Documents

Description

TECHNICAL RESEARCH REPORT Strong Formulations for Network Design Problems with Connectiity Requirements by Thomas L. Magnanti, S. Raghaan T.R I R INSTITUTE FOR SYSTEMS RESEARCH ISR deelops, applies

Transcript

TECHNICAL RESEARCH REPORT Strong Formulations for Network Design Problems with Connectiity Requirements by Thomas L. Magnanti, S. Raghaan T.R I R INSTITUTE FOR SYSTEMS RESEARCH ISR deelops, applies and teaches adanced methodologies of design and analysis to sole complex, hierarchical, heterogeneous and dynamic problems of engineering technology and systems for industry and goernment. ISR is a permanent institute of the Uniersity of Maryland, within the Glenn L. Martin Institute of Technology/A. James Clark School of Engineering. It is a National Science Foundation Engineering Research Center. Web site Strong Formulations for Network Design Problems with Connectiity Requirements Thomas L. Magnanti and S. Raghaan April 1999 Abstract The network design problem with connectiity requirements (NDC) models a wide ariety of celebrated combinatorial optimization problems including the minimum spanning tree, Steiner tree, and suriable network design problems. We deelop strong formulations for two ersions of the edge-connectiity NDC problem: unitary problems requiring connected network designs, and nonunitary problems permitting non-connected networks as solutions. We (i) present a new directed formulation for the unitary NDC problem that is stronger than a natural undirected formulation, (ii) project out seeral classes of alid inequalities partition inequalities, odd-hole inequalities, and combinatorial design inequalities that generalize known classes of alid inequalities for the Steiner tree problem to the unitary NDC problem, and (iii) show how to strengthen and direct nonunitary problems. Our results proide a unifying framework for strengthening formulations for NDC problems, and demonstrate the strength and power of flow-based formulations for network design problems with connectiity requirements. 1 Introduction Network Design Problems with Connectiity Requirements (NDC) arise in a wide ariety of application domains including VLSI design and telecommunication network design. The increasing reliance on communication networks (and expectations of a digital future) places an enormous importance on the reliability of such networks. To stay apace of the explosie growth of data, traffic telecommunication companies (telcos) are adding new fiber as well as deploying fiber capacity enhancing technologies (like Dense Wae Diision Multiplexing) to increase the capacity of their backbone networks. Telcos are also actiely deploying Sloan School of Management and Department of Electrical Engineering and Computer Science, Massachusetts Institute of Technology, Cambridge, MA The Robert H. Smith School of Business and the Institute for Systems Research, Van Munching Hall, Uniersity of Maryland, College Park, MD (competing) technologies in the local loop (the portion of the network that seres the customers premises) to proide greater access bandwidth to customers. Gien the enormous bandwidth capabilities of these networks, and the increasing array of serices proided oer them, the failure of any link in such a network can hae significant, perhaps een catastrophic consequences. In this paper, we consider network design problems with edge connectiity requirements. Informally gien requirements for the number of edge-disjoint paths between eery pair of nodes, we wish to design a minimum cost network that satisfies these requirements. To set notation, and define the class of problems we consider, we formally state the NDC problem as follows: Network Design Problem with Connectiity Requirements (NDC): We are gien an undirected graph G =(N,E), with node set N and edge set E, and a cost ector c R E + on the edges E. We are also gien a symmetric N N requirement matrix R =[r ij ]. The entry r ij prescribes the number of edge-disjoint paths needed between nodes i and j. We wish to select a set of edges that satisfy these requirements at minimum cost, as measured by the sum of costs of edges we choose. The NDC problem models a wide ariety of combinatorial optimization problems including the classical minimum spanning tree and Steiner tree problems. One important specialization of the NDC problem that arises in the design of telecommunications networks(see[cmw89]) isthesuriable Network Design Problem (SND). In this application each node in the graph has a connectiity requirement r and the connectiity requirements between nodes s and t are gien by r st =min{r s,r t }. Table 1 shows seeral other noteworthy cases of the NDC problem. A few obserations concerning the entries in Table 1 are worth making. The k-edge disjoint path problem seeks, at minimum cost, k-edge disjoint paths between specified nodes s and t. Whitney [Whi32] showed that a graph is k-edge connected (i.e., remains connected after elimination of any k 1 edges) if and only if it contains k-edge disjoint paths between eery pair of nodes. As a result, the minimum cost k-edge connected spanning subgraph problem is an SND problem with r = k for all nodes. The network design problem with low connectiity requirements (NDLC) is of particular interest to local telephone companies (see [CMW89]). In this special case of the SND problem, the connectiity requirements are restricted to {0, 1, 2}. (Since most local telephone companies beliee it is sufficient to protect against single link failures in the local loop, this problem is of significant importance to them.) In the Steiner forest problem, we are gien a graph G =(N,E) and node sets T 1,T 2,...,T P with T i T j = φ for all node set pairs i, j. We wish to design a graph at minimum cost that connects all the nodes in each node set. The point to point connection problem is a special case of the Steiner forest problem with T i = {s i,t i } for i =1,...,P. NDC problems can be classified in two ways. If the connectiity requirements imply that 2 Problem Type SND or NDC Connectiity Requirements Minimum Spanning Tree SND r = 1 for all nodes. Problem Steiner Tree Problem SND r = 1 for all nodes required in the tree; r =0forallothernodes. k-edge Disjoint SND r s = r t = k Path Problem requires k edge-disjoint paths between nodes s and t. Minimum Cost k-edge-connected SND r = k for all nodes. Spanning Subgraph Problem Minimum Cost Steiner k-edge- SND r = k for all required nodes; Connected Spanning Subgraph Problem r =0forallothernodes. Network Design with Low SND r {0, 1, 2} for all nodes. Connectiity Requirements (NDLC) Point to Point Connection NDC r si t i = 1 for gien source sets Problems {s 1,s 2,...,s p } and terminal sets {t 1,t 2,...,t p }. r ij =0otherwise. Steiner Forest Problem NDC r ij =1ifi T q and j T q for some pairwise disjoint node set T 1,T 2,...,T p. r ij =0otherwise. Table 1: Specializations of Network Design Problems with Connectiity Constraints 3 all nodes with a (positie) connectiity requirement must be connected, we say the problem is a unitary NDC problem. Otherwise, itisanonunitary NDC problem. For example, the SND problem is a unitary NDC problem, while the general Steiner forest problem is a nonunitary NDC problem. The examples in Table 1 show that the NDC problem models a ery wide ariety of connectiity problems on graphs. These problems appear both as stand alone problems and as subproblems in more complex network design applications (like VLSI design and telecommunications network design and management). Consequently, techniques for modeling and soling NDC problems hae widespread applicability. Considerable accumulated experience in the optimization literature has demonstrated the alue of deeloping good linear programming relaxations (strong formulations) of combinatorial optimization problems. Strong formulations are ery useful in deeloping exact algorithms solution methods (branch and bound, branch and cut, column generation) since their use rapidly accelerates these solution techniques. Strong formulations can also proide good bounds on the optimal solution and so are useful in assessing heuristic solution methods. In particular, dual-ascent heuristic techniques (that generate both lower bounds on the optimal solution alue and feasible solutions to the combinatorial optimization problem) based upon strong formulations typically proide better solutions than those based upon weaker linear programming relaxations. The deelopment in this paper is motiated by a desire to deelop better linear programming relaxations for NDC problems, and to proide a unifying strengthening approach applicable to all NDC problems. Since the NDC problem models a wide ariety of combinatorial optimization problems, the polyhedral structure of many special cases of the NDC problem hae been well studied. Oer the past twenty years, researchers hae proposed a large number of formulations (and solution methods based on them) for the Steiner tree problem. Most noteworthy among these are the papers by Wong [Won84] proposing a (bi)directed model for the undirected Steiner tree problem; Chopra and Rao [CR94a, CR94b] examining the facial structure of the undirected Steiner tree polyhedron and its relationship to a directed formulation for the Steiner tree problem; Goemans [Goe94] inestigating extended formulations 1 with node and edge ariables for the Steiner tree problem and introducing combinatorial design inequalities for the Steiner tree problem; and Goemans and Myung [GM93] establishing the relationship between seeral formulations for the Steiner tree problem. Seeral researchers hae examined special cases of unitary NDC problems with higher connectiity requirements (i.e., greater than 1). For series-parallel graphs, Mahjoub [Mah94] and Baïou and Mahjoub [BM93] proide complete descriptions of the 2-edge-connected 1 A natural formulation has one ariable for each member of its ground set. For example, a natural formulation for the NDC problem would contain one binary (or integer) decision ariable for each edge in the graph. An extended formulation contains additional ariables integer or continuous. Strong models for combinatorial optimization problems are often deeloped by using extended formulations. 4 spanning subgraph polytope and the Steiner 2-edge connected spanning subgraph polytope respectiely. Boyd and Hao [BH93] introduce a class of alid inequalities for the 2-edgeconnected spanning subgraph polytope and describe necessary and sufficient conditions for these alid inequalities to define facets. Based on a result by Robbins, Chopra [Cho92] describes a directed formulation for the NDLC problem in a model that permits unlimited edge replication. Using a result due to Nash-Williams, a generalization of Robbins theorem, Goemans [Goe90] shows how to strengthen a well-known cutset formulation for the SND problem with connectiities r {0, 1, een} in a model that permits unlimited edge replication. Grötschel, Monma, and Stoer [GMS92b, GMS95b, GMS95a, Sto92] inestigate the polyhedral structure of both the edge- and node-connectiity ersions of the SND problem. One of these papers [GMS92b]inestigates the polyhedral structure of the NDLC problem, while another in [GMS95b] examines the polyhedral structure of SND problems whose highest connectiity requirements are three or more. [GMS95a] and [Sto92] contain comprehensie summaries of polyhedral results for the SND problem. Researchers hae proposed many solution methods (both exact and approximate) for the NDC problem and its specializations. Our discussion has focused on polyhedral research in this area. Surey papers by Grötschel, Monma, and Stoer [GMS95a], Raghaan and Magnanti [RM97], and Frank [Fra94] proide more comprehensie reiews of research on the NDC and its specializations. In this paper, we deelop strong formulations for both unitary and nonunitary NDC problems. Our work differs from earlier research in seeral ways. Goemans [Goe90] and Grötschel, Monma, and Stoer [GMS95a] hae shown in arious forms how to use a result due to Nash-Williams to obtain stronger models for the SND problem with connectiities r {0, 1, een}. We show that although the Nash-Williams theorem is useful to motiate the directing procedure, it does not play a role in strengthening the formulation (i.e., it is not necessary)! Consequently, we are able to generalize the directing procedure to strengthen formulations for all unitary NDC problems. Next, we project out three classes of alid inequalities from the strengthened (extended) formulation for the unitary NDC problem that are generalizations of facet-defining alid inequalities for the Steiner tree problem. For special cases of the unitary NDC problems seeral researchers hae shown how to project from extended formulations that are equialent to the flow-based strengthened formulation for the NDC problem. For example, Goemans [Goe94] describes a node weighted formulation for the Steiner tree problem and obtains the three classes of alid inequalities by projection. Chopra and Rao [CR94a, CR94b] describe a directed arc formulation for the Steiner tree problem and show how to project out two classes of alid inequalities partition and odd-hole from it. Grötschel, Monma, and Stoer [GMS95a] describe a directed formulation for the SND problem with connectiities r {0, 1, een} and show how to project out partition inequalities from it. We illustrate the projection from the flow-based formulation for three reasons. First, seeral extended 5 formulations that are equialent to the flow formulation for the Steiner tree problem do not generalize to the NDC problem, for example, node weighted extended formulations for the Steiner tree problem do not generalize to the NDC problem. Second, for nonunitary problems we describe a directing and strengthening technique that requires flow ariables. Consequently, a deeper understanding of the flow-based formulation and its relationship to the cutset formulation is important. Third, we beliee this paper is the first to explicitly show how to project from the flow-based formulation (een for special cases of the unitary NDC problem like the Steiner tree problem). Finally, we show how to direct nonunitary NDC problems which appear to hae receied significantly less attention in the literature. We implement our directing procedure by using flow ariables to obtain strengthened (flow-based) formulations for nonunitary NDC problems, but it is not obious how to implement the directing procedure without using flow ariables. A companion paper [MR99] empirically confirms the theoretical results presented in this paper. It shows that a solution procedure for the NDLC problem using the models deeloped in this inestigation can be effectie in soling large scale problems with up to 300 nodes and 3000 edges to within a (guaranteed) few percent of optimality. The rest of this paper is organized as follows. In Section 2 we reiew two well-known formulations for the NDC problem, a natural formulation with edge ariables, and an extended formulation containing both flow and edge ariables. Next in Section 3, we first motiate the directing procedure applying a result by Nash-Williams that applies to unitary NDC problems with restricted connectiities. We then obiate the need for Nash-Williams result to strengthen the formulation of all unitary NDC problems. Sections 4, 5, 6, and 7 deal with the strength of the improed formulation. Section 4 proides some preliminary results regarding the projection of improed flow formulation onto the space of the edge ariables. Sections 5, 6, and 7 show how to project partition inequalities, odd-hole inequalities, and combinatorial design inequalities respectiely from the improed flow formulation. In Section 8 we examine nonunitary NDC problems. We first show how to strengthen a formulation of the Steiner forest problem by applying a new directing technique. In Section 9 we use this technique to strengthen formulations for all NDC problems. Finally, in Section 10 we proide some concluding remarks. Notation: We assume familiarity with standard graph theory terminology. We work with undirected graphs and directed graphs which we refer to as graphs and digraphs. To distinguish between directed and undirected graphs, we refer to undirected graphs as graphs, undirected edges as edges, directed graphs as digraphs, and directed edges as arcs. Weuse braces to denote an edge between nodes i and j, i.e., {i, j}, and parentheses to denote a directed arc from node i to node j, i.e., (i, j). Econ(T ) := max{r ij j T ; i N\T } denotes the connectiity requirements of a set of nodes T. Itisthemaximumedge-connectiity 6 requirement between any node in T and its complement. For NDC problems we refer to econ(i) asthemaximum connectiity requirement of node i. If econ(i) 0, we say node i is a required node. In models that permit parallel edges, we let G =(N,E) representthe underlying graph and b ij represent the number of parallel edges allowed between nodes i and j. For example, if a model permits two edges between nodes i and j, then the graph G contains the edge {i, j} and b ij = 2. In an undirected graph, any set of nodes T defines a cut δ(t )={{i, j} : i N\T,j T }. Similarly, any set of nodes T in a directed graph defines a dicut δ (T )={(i, j) :i N\T,j T } of arcs directed into the node set T and a set of arcs δ + (T )={(i, j) :i T,j N\T } directed out of T. An s t cut is a cut δ(t ) with s T and t T. Similarly, an s t dicut is a dicut, say δ (T ), with s T and t T. The capacity of a cut δ(w ) is defined as the sum of the capacity of the edges in the cut, and the capacity of a dicut δ (W ) is defined as the sum of the capacity of the arcs in the dicut. Sometimes we will want to eliminate the ariables from an extended formulation of a problem. Let A and B be two gien matrices and d be a column ector, all with the same number of rows. Consider the polyhedron P = {(x, f) :Ax + Bf d}. The polyhedron Q = {x : Ax + Bf d for some ector f} obtained by eliminating the f ariables is called the projection of the polyhedron P. If two formulations for a problem proide, for all objectie function coefficients, the same optimal objectie alue when soled as linear programs, we say the two formulations are equialent. When we compare two extended formulations, we say the two formulations are equialent if they proide the same objectie alue for all objectie function coefficients on the natural ariables (the objectie function coefficients for the additional ariables are zero). In other words two extended formulations are equialent if their projection onto the space of the natural ariables is identical. We say that adding an inequality I strengthens a formulation of a (mixed) integer programming problem if it is alid and adding it to the formulation improes the objectie alue of the linear programming relaxation of the formulation for some choice of the objectie function coefficients. We say that a formulation P 1 is stronger than a formulation P 2 if, when soled as linear programs, the objectie alue of P 1 is always better than the objectie alue of P 2, and sometimes is strictly better than the objectie alue of P 2. 2 Formulations for the NDC Problem In this section we describe two well-known models for the NDC problem, one a cutset model, and the other a multicommodity flow-based model. For the flow-based model we also show how to minimize the number of commodities, a method that proes inaluable in our subsequent discussions. Menger s theorem [Men27] states that the number of edge-disjoint paths between a pair of nodes, say s and t, is equal to the minimum number of edges across any cut between 7 them, i.e., any s t cut. Consequently, the following well-known cutset formulation, with x ij representing the number of copies of edge {i, j} in the network, is a alid representation of the NDC problem. Cutset formulation for the NDC problem: Minimize c ij x ij (1a) subject to: {i,j} E {i,j} δ(s) x ij econ(s) for all node sets S with φ S N; (1b) x ij b ij for all {i, j} E; (1c) x ij 0 and integer, for all {i, j} E. (1d) An alternatie way to formulate the problem is to enforce the connectiity requiremen

Related Search

We Need Your Support

Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks