ISR develops, applies and teaches advanced methodologies of design and analysis to solve complex, hierarchical, heterogeneous and dynamic problems of engineering technology and systems for industry and government. ISR is a permanent institute of the University of Maryland, within the Glenn L. Martin Institute of Technol- ogy/A. James Clark School of Engineering. It is a National Science Foundation Engineering Research Center. Web site http://www.isr.umd.edu I R INSTITUTE FOR SYSTEMS RESEARCH TECHNICAL RESEARCH REPORT Strong Formulations for Network Design Problems with Connectivity Requirements by Thomas L. Magnanti, S. Raghavan T.R. 99-28 Strong Formulations for Network Design Problems with Connectivity Requirements Thomas L. Magnanti and S. Raghavan y April 1999 Abstract The network design problem with connectivity requirements (NDC) models a wide variety of celebrated combinatorial optimization problems including the minimum span- ning tree, Steiner tree, and survivable network design problems. We develop strong for- mulations for two versions of the edge-connectivity NDC problem: unitary problems re- quiring 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 several classes of valid inequalities|partition inequalities, odd-hole inequalities, and combi- natorial design inequalities|that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem, and (iii) show how to strengthen and direct nonunitary problems. Our results provide a unifying framework for strengthening formulations for NDC problems, and demonstrate the strength and power of flow-based formulations for net- work design problems with connectivity requirements. 1 Introduction Network Design Problems with Connectivity Requirements (NDC) arise in a wide variety 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 explosive growth of data, tra c telecommunication companies (telcos) are adding new ber as well as deploying ber capacity enhancing technologies (like Dense Wave Division Multiplexing) to increase the capacity of their backbone networks. Telcos are also actively deploying Sloan School of Management and Department of Electrical Engineering and Computer Science, Mas- sachusetts Institute of Technology, Cambridge, MA 02139 y The Robert H. Smith School of Business and the Institute for Systems Research, Van Munching Hall, University of Maryland, College Park, MD 20742 1 (competing) technologies in the local loop (the portion of the network that serves the customers premises) to provide greater access bandwidth to customers. Given the enormous bandwidth capabilities of these networks, and the increasing array of services provided over them, the failure of any link in such a network can have signi cant, perhaps even catastrophic consequences. In this paper, we consider network design problems with edge connectivity requirements. Informally given requirements for the number of edge-disjoint paths between every pair of nodes , we wish to design a minimum cost network that satis es these requirements. To set notation, and de ne the class of problems we consider, we formally state the NDC problem as follows: Network Design Problem with Connectivity Requirements (NDC): We are given an undirected graph G =(N;E), with node set N and edge set E, and a cost vector c2R jEj + on the edges E. We are also given a symmetricjNj jNjrequirement 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 variety of combinatorial optimization problems in- cluding the classical minimum spanning tree and Steiner tree problems. One important specialization of the NDC problem that arises in the design of telecommunications net- works(see[CMW89])istheSurvivable Network Design Problem (SND). In this application each node v in the graph has a connectivity requirement r v and the connectivity require- ments between nodes s and t are given by r st =minfr s ;r t g.Table1showsseveralother noteworthy cases of the NDC problem. A few observations concerning the entries in Table 1 are worth making. The k-edge dis- joint path problem seeks, at minimum cost, k-edge disjoint paths between speci ed 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 every pair of nodes. As a result, the minimum cost k-edge connected spanning subgraph problem is an SND problem with r v = k for all nodes. The network design problem with low connectivity requirements (NDLC) is of particular interest to local telephone companies (see [CMW89]). In this special case of the SND problem, the connectivity requirements are restricted to f0;1;2g. (Since most local telephone companies believe it is su cient to pro- tect against single link failures in the local loop, this problem is of signi cant importance to them.) In the Steiner forest problem, we are given 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 =fs i ;t i g for i =1;:::;P. NDC problems can be classi ed in two ways. If the connectivity requirements imply that 2 Problem Type SND or NDC Connectivity Requirements Minimum Spanning Tree SND r v = 1 for all nodes v. Problem Steiner Tree Problem SND r v = 1 for all nodes required in the tree; r v =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 v = k for all nodes v. Spanning Subgraph Problem Minimum Cost Steiner k-Edge- SND r v = k for all required nodes; Connected Spanning Subgraph Problem r v =0forallothernodes. Network Design with Low SND r v 2f0;1;2g for all nodes v. Connectivity Requirements (NDLC) Point to Point Connection NDC r s i t i = 1 for given source sets Problems fs 1 ;s 2 ;:::;s p g and terminal sets ft 1 ;t 2 ;:::;t p g. r ij =0otherwise. Steiner Forest Problem NDC r ij =1ifi2T q and j2T q for some pairwise disjoint node set T 1 ;T 2 ;:::;T p . r ij =0otherwise. Table 1: Specializations of Network Design Problems with Connectivity Constraints 3 all nodes with a (positive) connectivity 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 very wide variety of con- nectivity problems on graphs. These problems appear both as stand alone problems and as subproblems in more complex network design applications (like VLSI design and telecom- munications network design and management). Consequently, techniques for modeling and solving NDC problems have widespread applicability. Considerable accumulated experience in the optimization literature has demonstrated the value of developing good linear programming relaxations (strong formulations) of com- binatorial optimization problems. Strong formulations are very useful in developing exact algorithms solution methods (branch and bound, branch and cut, column generation) since their use rapidly accelerates these solution techniques. Strong formulations can also provide good bounds on the optimal solution and so are useful in assessing heuristic solution meth- ods. In particular, dual-ascent heuristic techniques (that generate both lower bounds on the optimal solution value and feasible solutions to the combinatorial optimization problem) based upon strong formulations typically provide better solutions than those based upon weaker linear programming relaxations. The development in this paper is motivated by a desire to develop better linear programming relaxations for NDC problems, and to provide a unifying strengthening approach applicable to all NDC problems. Since the NDC problem models a wide variety of combinatorial optimization problems, the polyhedral structure of many special cases of the NDC problem have been well studied. Over the past twenty years, researchers have 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] investigating extended formulations 1 with node and edge variables for the Steiner tree problem and introducing combinatorial design inequalities for the Steiner tree problem; and Goemans and Myung [GM93] establishing the relationship between several formulations for the Steiner tree problem. Several researchers have examined special cases of unitary NDC problems with higher connectivity requirements (i.e., greater than 1). For series-parallel graphs, Mahjoub [Mah94] and Ba? ou and Mahjoub [BM93] provide complete descriptions of the 2-edge-connected 1 A natural formulation has one variable for each member of its \ground" set. For example, a natural formulation for the NDC problem would contain one binary (or integer) decision variable for each edge in the graph. An extended formulation contains additional variables|integer or continuous. Strong models for combinatorial optimization problems are often developed by using extended formulations. 4 spanning subgraph polytope and the Steiner 2-edge connected spanning subgraph polytope respectively. Boyd and Hao [BH93] introduce a class of valid inequalities for the 2-edge- connected spanning subgraph polytope and describe necessary and su cient conditions for these valid inequalities to de ne 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 theo- rem, Goemans [Goe90] shows how to strengthen a well-known cutset formulation for the SND problem with connectivities r v 2f0;1;eveng in a model that permits unlimited edge replication. Gr?otschel, Monma, and Stoer [GMS92b, GMS95b, GMS95a, Sto92] investi- gate the polyhedral structure of both the edge- and node-connectivity versions of the SND problem. One of these papers [GMS92b]investigates the polyhedral structure of the NDLC problem, while another in [GMS95b] examines the polyhedral structure of SND problems whose highest connectivity requirements are three or more. [GMS95a] and [Sto92] contain comprehensive summaries of polyhedral results for the SND problem. Researchers have 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. Survey papers by Gr?otschel, Monma, and Stoer [GMS95a], Raghavan and Magnanti [RM97], and Frank [Fra94] provide more comprehensive reviews of research on the NDC and its specializations. In this paper, we develop strong formulations for both unitary and nonunitary NDC problems. Our work di ers from earlier research in several ways. Goemans [Goe90] and Gr?otschel, Monma, and Stoer [GMS95a] have shown in various forms how to use a result due to Nash-Williams to obtain stronger models for the SND problem with connectivities r v 2f0;1;eveng. We show that although the Nash-Williams theorem is useful to motivate 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 valid inequalities from the strengthened (extended) formulation for the unitary NDC problem that are generalizations of facet-de ning valid inequalities for the Steiner tree problem. For special cases of the unitary NDC problems several researchers have shown how to project from extended formulations that are equiva- lent to the flow-based strengthened formulation for the NDC problem. For example, Goe- mans [Goe94] describes a node weighted formulation for the Steiner tree problem and obtains the three classes of valid inequalities by projection. Chopra and Rao [CR94a, CR94b] de- scribe a directed arc formulation for the Steiner tree problem and show how to project out two classes of valid inequalities|partition and odd-hole|from it. Gr?otschel, Monma, and Stoer [GMS95a] describe a directed formulation for the SND problem with connectivities r v 2f0;1;eveng and show how to project out partition inequalities from it. We illustrate the projection from the flow-based formulation for three reasons. First, several extended 5 formulations that are equivalent 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 variables. Consequently, a deeper understanding of the flow-based formulation and its relationship to the cutset formulation is important. Third, we believe this paper is the rst to explicitly show how to project from the flow-based formulation (even 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 have received signi cantly less attention in the literature. We implement our directing procedure by using flow variables to obtain strengthened (flow-based) formulations for nonunitary NDC problems, but it is not obvious how to implement the directing procedure without using flow variables. A companion paper [MR99] empirically con rms the theoretical results presented in this paper. It shows that a solution procedure for the NDLC problem using the models developed in this investigation can be e ective in solving 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 review two well-known for- mulations for the NDC problem, a natural formulation with edge variables, and an extended formulation containing both flow and edge variables. Next in Section 3, we rst motivate the directing procedure applying a result by Nash-Williams that applies to unitary NDC problems with restricted connectivities. We then obviate the need for Nash-Williams re- sult to strengthen the formulation of all unitary NDC problems. Sections 4, 5, 6, and 7 deal with the strength of the improved formulation. Section 4 provides some preliminary results regarding the projection of improved flow formulation onto the space of the edge variables. Sections 5, 6, and 7 show how to project partition inequalities, odd-hole inequali- ties, and combinatorial design inequalities respectively from the improved flow formulation. In Section 8 we examine nonunitary NDC problems. We rst show how to strengthen a formulation of the Steiner forest problem by applying a new directing technique. In Sec- tion 9 we use this technique to strengthen formulations for all NDC problems. Finally, in Section 10 we provide 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., fi;jg, and parentheses to denote a directed arc from node i to node j, i.e., (i;j). Econ(T) := maxfr ij jj2T;i2NnTgdenotes the connectivity requirements of a set of nodes T.Itisthemaximumedge-connectivity 6 requirement between any node in T and its complement. For NDC problems we refer to econ(i)asthemaximum connectivity 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 fi;jg and b ij = 2. In an undirected graph, any set of nodes T de nes a cut (T)=ffi;jg : i2NnT;j2Tg. Similarly, any set of nodes T in a directed graph de nes a dicut ? (T)=f(i;j):i2NnT;j2Tg of arcs directed into the node set T and a set of arcs + (T)=f(i;j):i2T;j2NnTg directed out of T.Ans{t cut is a cut (T) with s62T and t2T. Similarly, an s{t dicut is a dicut, say ? (T), with s62T and t2T. The capacity of a cut (W) is de ned as the sum of the capacity of the edges in the cut, and the capacity of a dicut ? (W) is de ned as the sum of the capacity of the arcs in the dicut. Sometimes we will want to eliminate the variables from an \extended" formulation of a problem. Let A and B be two given matrices and d be a column vector, all with the same number of rows. Consider the polyhedron P = f(x;f):Ax + Bf dg. The polyhedron Q = fx : Ax + Bf d for some vector fg obtained by eliminating the f variables is called the projection of the polyhedron P. If two formulations for a problem provide, for all objective function coe cients, the same optimal objective value when solved as linear programs, we say the two formulations are equivalent. When we compare two extended formulations, we say the two formulations are equivalent if they provide the same objective value for all objective function coe cients on the natural variables (the objective function coe cients for the additional variables are zero). In other words two extended formulations are equivalent if their projection onto the space of the natural variables is identical. We say that adding an inequality I strengthens a formulation of a (mixed) integer programming problem if it is valid and adding it to the formulation improves the objective value of the linear programming relaxation of the formulation for some choice of the objective function coe cients. We say that a formulationP 1 is stronger than a formulationP 2 if, when solved as linear programs, the objective value of P 1 is always better than the objective value of P 2 , and sometimes is strictly better than the objective value 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 proves invaluable 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 edgefi;jgin the network, is a valid representation of the NDC problem. Cutset formulation for the NDC problem: Minimize X fi;jg2E c ij x ij (1a) subject to: X fi;jg2 (S) x ij econ(S) for all node sets S with 6= S6= N; (1b) x ij b ij for all fi;jg2E; (1c) x ij 0 and integer, for all fi;jg2E: (1d) An alternative way to formulate the problem is to enforce the connectivity requirements of the matrix R using commodity flows. For each pair fs;tg of nodes, with r st 1, create a commodity, arbitrarily choosing one of the nodes as the origin of the commodity and the other node as the destination. Let K denote the set of commodities and let q k ,foreach k 2 K, denote the edge-connectivity requirement between the origin and destination of commodity k:ifr st =3,thenq k = 3 for the commodity k corresponding to the node pair fs;tg. The following mixed integer program, with x ij representing the number of copies of edge fi;jg in the network and f k ij flows, is a valid formulation for the NDC problem. Undirected flow formulation for the NDC problem: Minimize X fi;jg2E c ij x ij (2a) subject to: X j2N f k ji ? X l2N f k il = 8 > > < > > : ?q k q k 0 if i = O(k); if i = D(k); for all i2N and k2K otherwise; (2b) f k ij f k ji ) x ij for all fi;jg2E and k2K (2c) f k ij ;f k ji 0 for all fi;jg2E and k2K (2d) x ij b ij for all fi;jg2E;(2e x ij 0 and integer, for all fi;jg2E: (2f) The max-flow min-cut theorem implies that the cutset and flow formulations are equiv- alent in the following sense. Lemma 2.1 The projection of the feasible space of the linear programming relaxation of the undirected flow formulation for the NDC problem (2) onto the space of the edge variables 8 is the feasible space of the linear programming relaxation of the cutset formulation for the NDC problem (1). Notice that the cutset formulation is of exponential size, while the flow formulation is compact: it has O(jKj(jEj+jNj)) constraints and O(jKjjEj)variables. A simple, and naive, way to determine the number of commodities in the flow formula- tion is to create a commodity for every pair of nodes with a connectivity requirement. For an underlying graph with 100 nodes and 1000 edges and positive connectivity requirements between all nodes this approach would create a commodity for every node pair and so 4,950 commodities. Consequently, the model would contain 495;000 flow balance constraints, 9;900;000 constraints of type (2c), 9,900,000 nonnegativity constraints for the flow vari- ables, 1,000 constraints of type (2e), and 1,000 nonnegativity and integrality constraints for the edge variables. As this example shows, the flow formulation can be very large. By using fewer commodities, if possible, we could reduce the size of the formulation. To accomplish this objective, we can use an idea that Gomory and Hu [GH61] used when solving the classical network synthesis problem. Given the connectivity requirements matrix R, create a \requirement" graph G R on the node set N, giving edgefi;jg between nodes i and j in G R aweightr ij . Gomory and Hu showed that it is su cient to consider the connectivity requirements only for the edges on a maximum spanning tree of this graph. It is easy to verify this result using the max-flow min-cut theorem and the maximum spanning tree optimality conditions. As is well known, a spanning tree is a maximum spanning tree if and only if it satis es the following optimality condition: For every nontree edgefk;lg of G R , r ij r kl for every edgefi;jgcontained in the (tree) path P on the maximum spanning tree connecting nodes k and l. As a result, any network that satis es the requirements of the maximum spanning tree has su cient capacity to satisfy the requirements of nontree edges. (By the max-flow min-cut theorem, the network has su cient capacity to connect nodes k and l if every cut in the network design separating these nodes has capacity at least r kl . Since some pairs i;j of nodes on the path P must lie on opposite sides of this cut, the cut must have capacity at least r ij r kl .) Gomory and Hu?s result permits us to model the edge-connectivity requirements in any NDC problem with jNj?1 or fewer commodities. We simply compute the maximum spanning tree of the requirement graph, which we now refer to as the requirement spanning tree, and create commodities only for those edges of the maximum spanning tree with nonzero weight. Since the requirement spanning tree has jNj?1 edges and nding it requiresO(jEj+jNjlogjNj) time, this procedure creates at mostjNj?1 commodities (we will not create commodities for zero weight edges of the requirement spanning tree) and requires O(jEj+jNjlogjNj)time. The two formulations 1 and 2 for the NDC problem are known to be weak. That is, the objective value of the linear programming relaxation are typically signi cantly less than 9 the optimal objective value of the integer program. Computational experiments reported by Gr?otschel, Monma, and Stoer [GMS92a, GMS95b] con rm this result, particularly when the requirement spanning tree has edges with connectivity requirement 1. (In a remarkable paper, Jain (see [Jai98]) provides some theoretical evidence to support these results. He shows that the worst case ratio of the optimal value of the integer program to the optimal value of the linear programming relaxation of the cut formulation is 2, independent of the problems?s size.) 3 Stronger Formulations for Unitary NDC Problems In this section we rst show how to direct unitary NDC problems for situations when the connectivity requirements are all even or one, and obtain a stronger formulation for this special case of the unitary NDC problem. We then generalize this result, developing an improved model for any unitary NDC problem (i.e., even those with odd connectivity requirements). For ease of exposition, for the rest of this paper we assume that the model does not permit edge replication. It is straightforward to verify that the results apply to models that permit edge replication. 3.1 Directing the Unitary NDC Problem The following result due to Nash-Williams [NW60] provides a key ingredient for transform- ing the undirected formulation to a directed one. Theorem 3.1 (Nash-Williams) Suppose G is an undirected graph with r xy edge-disjoint paths connecting each pair x and y of its nodes. Then it is possible to direct the graph (i.e., orient its edges) so that the resulting digraph contains br xy =2c arc-disjoint paths from node x to node y and br xy =2c arc-disjoint paths from node y to node x. Consider any unitary NDC problem whose connectivity requirements r st are even or one. We can view any feasible integer solution to this problem as follows: it is connected and contains several 2-edge-connected components. If we contract the 2-edge-connected components, the solution becomes a tree. The edges on the tree are the bridge edges in the feasible solution before we contracted the 2-edge-connected components; that is, removing these edges disconnects the graph de ned by that solution. The Nash-Williams theorem permits us to direct the edges of each 2-edge-connected component so that for any pair of nodes i and j with r ij 2 (by assumption these require- ments must be even), the network contains r ij =2 directed arc-disjoint paths from node i to node j,andr ij =2 directed arc-disjoint paths from node j to node i. Once oriented, each 2-edge-connected component contains a directed path between every pair of its nodes. Therefore, if nodes i and j belong to the same 2-edge-connected component and r ij =2, 10 the oriented network contains a directed path from node i to node j and a directed path from node j to node i. To direct the bridges, consider the tree obtained by contracting each 2-edge-connected component of the solution. Select any one of the nodes created by the contraction as a root node and direct the tree away from this node. Figure 1 illustrates this directing procedure. In this example a, b, c and g are 2-edge- connected components. Between every pair of nodes s and t in these components r st =2. We orient the edges of each component (see Figure 1b) so that it contains a directed path between every pair of nodes in each 2-edge-connected component. Next, we select the node created by contracting component b as the root node and direct the tree edges (i.e., the bridges of the solution) away from node b. Figure 1c shows the graph at the conclusion of the directing procedure. These observations permit us to formulate the unitary NDC problem as follows. Let y ij be 1 if edge fi;jg is oriented from node i to node j in the directing procedure applied to the optimal solution (i.e., the oriented network contains arc (i;j)) and be 0 otherwise. Directed cut formulation for the unitary NDC problem (r st 2f0,1,eveng): Minimize X fi;jg2E c ij x ij (3a) subject to: X (i;j)2 ? (S) y ij econ(S) 2 if econ(S) 2; for all S N,(3b) X (i;j)2 ? (S) y ij 1 if econ(S)=1;forallS,root62S (3c) y ij +y ji x ij for all fi;jg2E (3d) x ij 1 for all fi;jg2E (3e) y ij ;y ji ;x ij 0 and integer, for all fi;jg2E.(3f) Since econ(S) maxfr ij jj2S;i2NnSg, constraint (3b) ensures that for every pair of nodes s and t with r st 2, every s{t dicut contains at least r st =2 arcs and every t{s dicut contains at least r st =2 arcs. Menger?s theorem ensures that the oriented network contains at least r st =2 arc-disjoint paths from node s to node t and r st =2 arc-disjoint paths from node t to node s. Similarly, constraints (3b) and (3c) ensure that the oriented network contains a directed path from the root to every required node. Constraint (3d) ensures that the oriented network contains at most one of the arcs (i;j)and(j;i). Proposition 3.2 The directed cut model is a valid formulation for the unitary NDC prob- lem in the sense that (x;y) is a feasible solution to this model if and only if x is an incidence vector of a feasible NDC design (that is, x is a feasible solution to the cutset model (1)). Proof: Suppose x is an incidence vector of a feasible NDC design. The argument preceding 11 ab c d e f g (a) (b) ab c d e f g ab c d e f g (c) Figure 1: Directing the bridges of a feasible solution to the unitary NDC problem. (a) Fea- sible solution. (b) Direct the edges of each 2-edge-connected component. (c) Direct the bridges away from component b. 12 Formulation (3) shows how to construct an integer vector y so that (x;y) is a valid solution for the directed cut model. To establish the converse, suppose (x;y) is a feasible solution to the directed cut model. Let Q be any node set with econ(Q) = econ(NnQ) 2. Combining inequality (3b) for S = Q and S = NnQ and the inequalities (3d) summed over all fi;jg2 (Q)gives X fi;jg2 (Q) x ij X (i;j)2 + (Q) y ij + X (j;i)2 ? (Q) y ji econ(Q): If Q is any node set with econ(Q) = econ(NnQ) = 1, assume without loss of generality that the root node is not in Q. Then the inequality (3c) with S = Q and the inequality (3d) summed over fi;jg2 (Q) implies that X fi;jg2 (Q) x ij 1: Therefore, x is a feasible solution to the cutset formulation (1). To see that the linear programming relaxation of the directed cut formulation is stronger than linear programming relaxation of the cutset formulation, consider the NDLC example shown in Figure 2. In this example, each edge has unit cost. Nodes a, b and c have a connectivity requirement of 2. Nodes d, e and f have a connectivity requirement of 1. The optimal solution to the linear programming relaxation of the cutset formulation is x ab = x ac =1andx bc = x bd = x cd = x de = x df = x ef =0:5, with objective value 5. The optimal solution to the linear programming relaxation of the directed cut model has integer values for the edge variables. The solution is y ab = y bd = y dc = y ca = y de = y df =1, x ab = x ac = x bd = x cd = x de = x df = 1, with objective value 6. By reformulating the problem and solving the linear programming relaxation, we have obtained the optimal solution. In the next section we show how that the Nash-Williams procedure is not necessary for this directing procedure. Consequently, we generalize the results in this section to all unitary NDC problems. 3.2 Generalizing the Directing Procedure The directed cut formulation (3) is not valid for unitary NDC problems with odd connec- tivity requirements. As an example, consider an SND problem de ned on K 4 ,thecomplete graph on four nodes, assuming each node has a connectivity requirement of 3. The optimal solution for this problem is K 4 . For any node i in K 4 , there is no way to direct the edges so that both + (i)and ? (i) are at least 1.5. Suppose, however, that in the directed cut formulation we relax the integrality con- straints imposed upon the y ij variables, and interpret y ij as the capacity on the flow from node i to node j. We will show that this formulation is a valid mixed integer program for 13 x ij = 1 x ij = 1 2 a bc d ef a bc d ef a bc d ef (a) (b) (c) Connectivity 2 node Connectivity 1 node Figure 2: The directed cut formulation is stronger than the cutset formulation. (a) Underly- ing graph with all edge costs equal to 1. (b) Optimal LP solution to the cutset formulation. (c) Optimal LP solution to the directed cut formulation. any unitary NDC problem. Consider any feasible solution to an unitary NDC problem. As we noted previously, the solution is a connected graph consisting of 2-edge-connected components and bridges. Suppose (i) we select y ij = y ji =1=2 for each edge on the 2-edge- connected components, and (ii) direct the bridges away from the component that contains the root node, setting y ij to1ifedgefi;jg is oriented from node i to node j,and0oth- erwise. (If we contract the 2-edge-connected components the directing procedure for the bridges is similar to the directing procedure for the Steiner tree.) The resulting solution (x;y) is feasible in the directed cut formulation if we relax the integrality condition on y. Therefore, the following directed cut formulation is valid for all unitary NDC problems. Directed cut formulation for the unitary NDC problem: Minimize X fi;jg2E c ij x ij (4a) subject to: X (i;j)2 ? (S) y ij econ(S) 2 if econ(S) 2; for all S N,(4b) X (i;j)2 ? (S) y ij 1 if econ(S)=1;forallS,root62S (4c) y ij +y ji x ij for all fi;jg2E (4d) x ij 1 for all fi;jg2E (4e) 14 y ij ;y ji 0 for all fi;jg2E (4f) x ij 0 and integer, for all fi;jg2E.(4g) Proposition 3.3 The directed cut model (4) is a valid formulation for the unitary NDC problem in the sense that (x;y) is a feasible solution to this model if and only if x is an incidence vector of a feasible NDC design. Proof: Similar to the proof of Proposition 3.2. 3.2.1 Flow Formulation The max-flow min-cut theorem permits us to formulate an improved flow model, with multiple commodities, that is equivalent to the directed cut model (4). Improved undirected flow formulation for the unitary NDC problem: Minimize X fi;jg2E c ij x ij (5a) subject to: X j2N f k ji ? X l2N f k il = 8 > > < > > : ?q k q k 0 if i = O(k); if i = D(k); for all i2N and k2K otherwise; (5b) f k ij +f h ji x ij for all fi;jg2E and k;h2K (5c) f k ij ;f k ji 0 for all fi;jg2E and k2K (5d) x ij 1 for all fi;jg2E (5e) x ij 0 and integer, for all fi;jg2E.(5f Using the procedure described in Section 2, we can create the commodities as follows. Select any node i whose maximum connectivity requirement is greater than or equal to 2 as the root node. (If the maximum connectivity requirement of all nodes is 1, and so the problem is a Steiner tree problem, we arbitrarily select any one of the nodes as the root node.) Commodity selection procedure for Formulation (5) 1. Find the requirement spanning tree. 2. Delete all edges with r st = 0 from the requirement spanning tree. The resulting tree is connected because, by assumption, the NDC problem is unitary. 3. For each edge fs;tg of the requirement spanning tree with r st 2, create two com- modities: one with origin node s and destination node t, and the other with origin node t and destination node s; each of these commodities has a flow requirement of r st =2. 15 1 1 1 11 g h i a, b c, d j (b) (c) 4 1 1 61 11 cba g d h i j 40 1 1 6 0 1 11 cba g ed f h i j (a) Figure 3: Commodity selection procedure for the unitary NDC problem. (a) Requirement spanning tree. (b) Tree obtained by deleting edges fs;tg with r st = 0. (c) Tree obtained by contracting edges fs;tg with r st 2. 4. Contract each edge fs;tg with r st 2 in the requirement spanning tree, creating a contracted requirement spanning treeT withr ij =1foralledgesfi;jg. We distinguish nodes created by the contraction from the original nodes, by calling them components. We denote a component by any one of the nodes it contains in the original requirement spanning tree (e.g., if we create a component by contracting nodes s and t,thenwe denote the component s). Select a component i in T as the root node (if T does not contain any components, then select any node as the root node arbitrarily). Create a commodity for every node j in T other than the root node, with node i as its origin (in the original graph), and node/component j as its destination (in the original graph), with a requirement of 1. Figure 3 illustrates this procedure. Figure 3a shows the requirement spanning tree of a unitary NDC problem. Figure 3b shows the requirement spanning tree after we have deleted edges fs;tg with r st = 0. Notice that because the problem is a unitary NDC problem, the graph in Figure 3b is connected. Otherwise, it would be a forest. Table 2 identi es the commodities obtained by applying the directing procedure to the example in Figure 3. Edges fa;bg and fc;dg are the only edges with a requirement of at least 2 on this tree. Therefore, we create four commodities|those shown in the rst 16 Commodity Origin Commodity Destination Commodity Requirement a b 2 b a 2 c d 3 d c 3 a c 1 a g 1 a h 1 a i 1 a j 1 Table 2: Commodities in Formulation (5) for example in Figure 3. four rows of Table 2. Figure 3c shows the contracted requirement spanning tree (i.e., after contracting edges with r st 2). Let node a denote the componentfa;bg, and node c denote component fc;dg. We select node a as the root. The tree in Figure 3c contains 6 nodes. Therefore, we create 5 commodities, each with origin node a, and destination nodes c, g, h, i and j. The following useful property is a consequence of the commodity selection procedure. Property 3.4 For any node set S, 1. If econ(S) 2, then the improved flow formulation contains a commodity k whose flow requirement is econ(S)=2,originisinNnS, and destination is in S. 2. If econ(S)=1and root 62 S, then the improved flow model contains a commodity whose flow requirement is 1, origin is the root node, and destination is in S. 3. If econ(S)=1and root 2S, then no commodity in the improved flow model has its origin in NnS, and destination in S. Proof: This result follows from the commodity selection procedure and the fact that r st = maxfr ij jj2S;i2NnSg econ(S) for any edge fs;tg in the requirement spanning tree. We now establish the validity of the improved undirected flow formulation for the unitary NDC problem by showing that the improved undirected flow formulation and the directed cut formulation are equivalent. Lemma 3.5 The improved undirected flow formulation (5) and the directed cut formula- tion (4) are equivalent. 17 Proof: We assume that we select the same root node in both formulations. First, consider any feasible solution (x ;y ) to the directed cut formulation. If we interpret y ij as a capacity imposed upon the flow from node i to node j, the max-flow min-cut theorem implies that we can (i) send r st =2 units of flow between any pair of nodes s and t in the requirement spanning tree with r st 2, and (ii) send one unit of flow from the root component in the contracted requirement spanning tree to any other node/component in the contracted requirement spanning tree. Furthermore, the constraint y ij + y ji x ij implies that we can ful ll conditions (i) and (ii) while ensuring that for each edge fi;jg, the sum of the maximum flow sent (on the edge fi;jg)fromnodei to node j, and the maximum flow sent from node j to node i does not exceed x ij . These arguments show that we can nd flow variables f so that (x ;f ) is feasible in the flow formulation. Suppose ( x; f) is a feasible solution to the improved flow formulation. For each edge fi;jg,set y ij =max k2K f k ij and y ji =max k2K f k ji . We claim the solution ( x; y)isfeasible in the directed cut formulation. Whenever edge fs;tg is in the requirement spanning tree and r st 2, the improved undirected flow formulation sends r st =2 units of flow from node s to node t and r st =2 units of flow from node t to node s. Consequently, if edgefs;tgis in the requirement spanning tree and r st 2, the capacity of every s{t dicut and every t{s dicut is at least r st =2(forthesolution( x; y)). For any node set S, the requirement spanning tree contains an edge fs;tg in (S) with econ(S)=r st . Therefore, whenever econ(S) 2, the capacity of the dicut ? (S) is at least econ(S)=2. The improved undirected flow formulation sends 1 unit of flow from the root component to every node/component in the contracted requirement spanning tree. Therefore, the capacity of every dicut ? (S)withroot62 S and econ(S) = 1 is at least 1. The constraint f k ij + f h ji x ij implies that for every edge, y ij + y ji x ij .Consequently,( x; y) is feasible for the directed cut model, and thus the improved undirected flow formulation and the directed cut formulation are equivalent. Before concluding this section, we note the improved models (4) and (5) are stronger, as linear programs, than the cutset (1) and the undirected flow (2) model only if the requirement spanning tree contains an edge fs;tg with r st = 1. To see this result, observe that if no pair of nodes i and j has a connectivity requirement of 1, then for all node sets S, econ(S)6=1. Butthen,if x is any feasible solution to the cutset formulation, the vector ( x; y), with y ij = y ji = x ij =2, is feasible in the directed cut formulation. As we have shown before, if ( x; y) is any feasible solution to the directed cut formulation, then x is feasible in the cutset formulation. Therefore, in this case, the two models are equivalent. Finally we note that a simple modi cation of the formulations we have considered per- mits us to model situations that allow edge replication: we just replace the constraint x ij 1 by the constraint x ij b ij throughout our discussion. 18 4 Projecting from the Improved Flow Formulation To compare the improved flow formulation and the cutset formulation, we would like to project out the flow variables from the improved flow formulation so that the resulting models have the same set of variables. An elegant method for projection, proposed by Balas and Pulleyblank [BP83], and implicit in the work of Benders [Ben62], is based upon a theorem of the alternatives. Theorem 4.1 (Projection Theorem) The projection of the set P =f(x;f)2R n+m jAx+ Bf dg onto the space of the x variables is Proj x (P)=fx2R n j(g j ) T Ax (g j ) T d; forj =1;2;:::;Jg; which is de ned by a nite set of generators fg j jj =1;:::;Jg of the cone C =fgjB T g = 0; g 0g. The cone C in the statement of Theorem 4.1 is just the linear programming dual to the feasibility problem obtained by deleting the x variables and setting the righthand side to zero in the inequality Ax+Bf d. When the polyhedron P is de ned by equality as well as inequality constraints, as in the improved undirected formulation Theorem 4.1 assumes the following form. Corollary 4.2 The projection of the set P =f(x;f) 2R n+m jAx + Bf d; A 0 x + B 0 f = d 0 ; x2X; f 0g onto the space of the x variables is Proj x (P)=fx2Xj(g j u ) T Ax +(g j v ) T A 0 x (g j u ) T d +(g j v ) T d 0 ; forj =1;2;:::;Jg; which is de ned by a nite set of generators f(g j u ;g j v )jj =1;:::;Jg of the cone C = f(u;v)jB T u + B 0 T v 0; u 0; v unrestrictedg. If we can identify a set of nite generators of the cone C, then we obtain the projection of the set P. The Projection Theorem has the additional advantage that every member (u;v) of the cone C de nes a valid inequality (u T A+ v T A 0 )x u T d + v T d 0 )forProj x (P). As a consequence, even if we cannot characterize the generators of the cone, we can still use the cone to obtain valid inequalities for Proj x (P). 4.1 Projection Cone of the Improved Undirected Flow Formulation (5) In Sections 5, 6, and 7, we will use the Projection Theorem to show that the improved flow formulation (5) implies three classes of valid inequalities for the cutset formulation and, therefore, that the flow formulation is stronger than the cutset formulation. To develop these results, we need to nd generators for the cone C in the statement of Theorem 4.1, 19 which is the dual linear program to the feasibility problem obtained by deleting the x variables and setting the righthand side to zero. For the improved flow formulation (5), we need to consider the following projection cone: P h2K u kh ij +v k i ?v k j P h2K u hk ij +v k j ?v k i ) 0 8fi;jg2E; 8k2K (6a) u kh ij 0 8fi;jg2E; 8k;h2K: (6b) In these inequalities, v k i is the dual variable corresponding to the flow balance equation at node i for commodity k,andu kh ij is the dual variable corresponding to the forcing constraint f k ij +f h ji x ij . Note that for any edgefi;jgand any pair of commodities k and h, the model contains two forcing constraints f k ij + f h ji x ij and f h ij + f k ji x ij . We identify the dual variable u kh ij with the constraint f k ij +f h ji x ij and the dual variable u hk ij with the constraint f h ij +f k ji x ij . By convention, the dual variables obtained by reversing the indices, i.e., u kh ij and u hk ji ,arethesame. Since one flow balance equation for each commodity is redundant, we can set, for each commodity k, v k O(k) to value zero. Using Corollary 4.2 for any member of this cone, we obtain a valid inequality of the form X fi;jg2E ( X k2K X h2K u kh ij )x ij X k2K q k v k D(k) : (7) In this expression, q k is the number of units of commodity k sent from commodity k?s origin to its destination. We refer to the coe cient of x ij in this inequality as ij and the righthand side coe cient as 0 . Given some choice of the variables v k i for all the nodes i and commodities k,therearea number of choices for u hk ij . How do we determine the best such choice? Since the coe cient ij of x ij in the inequality x 0 is P k2K P h2K u kh ij , we would like P k2K P h2K u kh ij to be as small as possible for each edge. The following theorem describes the choice of u hk ij that minimizes P k2K P h2K u kh ij . We give a constructive proof that also shows how to determine the u hk ij values. Theorem 4.3 Suppose we are given values for v k i for all nodes i and all commodities k.For any edge fi;jg,lett k ij =max(0;v k j ?v k i ) and t k ji =max(0;v k i ?v k j ). De ne t ij = P k2K t k ij and t ji = P k2K t k ji .Thenmax (t ij ;t ji ) is the minimum feasible value of P k2K P h2k u kh ij in the inequalities (6a). Proof: We will establish this result for each edgefi;jg. Let us rst show that max (t ij ;t ji )is a lower bound on the value of P k2K P h2K u kh ij in any feasible solution to the inequalities (6a). Let I be the set of all commodities with t k ij > 0andJ be the set of commodities with t k ji > 0. For any edge fi;jg with v k j ?v k i > 0, equation (6a) implies P h2K u kh ij v k j ?v k i . Summing over all commodities in the set I gives P k2I P h2K u kh ij P k2I (v k j ?v k i )=t ij . Similarly, 20 by considering the commodities in the set J,weobtain P k2J P h2K u hk ij P k2J (v k i ?v k j )= t ji . But then the inequalities P k2K P h2K u kh ij P k2I P h2K u kh ij and P k2K P h2K u kh ij P k2J P h2K u hk ij imply that P k2K P h2K u kh ij max (t ij ;t ji ). We next prescribe values for the variables u kh ij that achieve the lower bound max (t ij ;t ji ). Initially, each u kh ij =0and P k2K P h2K u kh ij = 0. Select a commodity l from I and a commodity m from J.Setu lm ij =minft l ij ;t m ji g.Ift l ij t m ji , delete m from J, and if t l ij t m ji , delete l from I.Sett l ij = t k ij ?u lm ij and t m ji = t m ji ?u lm ij . Repeat this procedure until one of the two sets I and J,sayJ, is empty. Note that at this point P k2K P h2K u kh ij =min(t ij ;t ji )and the u and v variables satisfy inequality (6a) for every commodity we have deleted from I and J. For the remaining commodities l2I,letm be any commodity in K and set u lm ij = t l ij . Thus, P k2K P h2K u kh ij =min(t ij ;t ji )+(max(t ij ;t ji )?min (t ij ;t ji )) = max (t ij ;t ji ). By construction, this choice of u hk ij satis es the equations of the cone. With the aid of Theorem 4.3, we will now derive three classes of valid inequalities| partition inequalities, odd-hole inequalities, and combinatorial design inequalities|that generalize known classes of valid inequalities for the Steiner tree problem to the unitary NDC problem. For ease of exposition we will rst consider the NDLC problem, and then generalize the results to the unitary NDC problem. 5 Partition Inequalities For the NDLC problem, partition inequalities (also called multicut inequalities by some au- thors) have the following form. Partition the node setN into disjoint node setsN 0 ;N 1 ;:::;N p satisfying the property that each node set has at least one node i with a connectivity re- quirement r i > 0. A partition inequality is an inequality of the form 1 2 k=p X k=0 X (N k ) x ij 8 > > < > > : p+ 1 if at least two sets have a node with a connectivity requirement of two; p otherwise. This inequality implies that (i) if no set or exactly one set in the partition has a node with a connectivity requirement of two, then the network contains at least p edges between the p + 1 sets, and (ii) if two or more sets have a node with a connectivity requirement of two, then the network contains at least p+ 1 edges between these sets. Chopra [Cho89] and Magnanti and Wolsey [MW95] show that the partition inequalities describe the dominant of the spanning tree polytope. Chopra and Rao [CR94a] and Gr?otschel and Monma [GM90] show that under appropriate conditions, partition inequalities are facet de ning for the Steiner tree problem and for the NDLC problem respectively. Consider the ve node example shown in Figure 4. Nodes 0 and 1 have a connectivity requirement of two; nodes 2, 3 and 4 have a connectivity requirement of 1. The improved undirected formulation (with node 0 as the root node) for this network has four commodities 21 v 0 = 0 1 1 0 23 4 v 1 = 1 1 v 2 = 0 1 v 3 = 0 1 v 4 = 0 1 r 0 = 2 1 0 23 4 r 1 = 2 r 2 = 1r 3 = 1 r 4 = 1 1 0 23 4 v 0 = 0 2 v 1 = 0 2 v 2 = 1 2 v 3 = 0 2 v 4 = 0 2 1 0 23 4 v 0 = 0 3 v 1 = 0 3 v 2 = 0 3 v 3 = 1 3 v 4 = 0 3 1 0 23 4 v 0 = 0 4 v 1 = 0 4 v 2 = 0 4 v 3 = 0 4 v 4 = 1 4 1 0 23 4 v 0 = 1 0 v 1 = 0 0 v 2 = 0 0 v 3 = 0 0 v 4 = 0 0 (a) (b) (c) (d) (e) (f) Figure 4: Projecting partition inequalities for a ve node example. (a) Connectivity re- quirements (b) Value of the v 0 i variables (c) Value of the v 1 i variables (d) Value of the v 2 i variables (e) Value of the v 3 i variables (f) Value of the v 4 i variables. (1, 2, 3 and 4) with the origin as the root node and node 1, 2, 3 and 4, respectively, as the destination node. It also has a commodity (commodity 5) with node 1 as the origin and node 0 as the destination. We will refer to commodity 5 as commodity 0 to simplify our discussion. Therefore, for each commodity i,nodei is the destination. Consider the partition inequality with each node de ning a set in the partition (i.e., 1 2 P i P j6=i x ij 5). Each edge variable in the partition inequality has a coe cient of 1 (note that the inequality counts each edge twice in the double summation). Consequently, in projecting out these variables to obtain this inequality, we need P k2K P h2K u kh ij = 1. Since the righthand side has value 5, we also need P k2K v k D(k) =5(q k = 1 for all commodities in the NDLC problem). In the example of Figure 4, for each commodity k =0;:::;4, let v k i =0ifi6= k and v k k = 1. Consider any edgefi;jg. Note that the v k i and v k j values are the same for all commodities, except for (i) commodity i,withv i i =1andv i j = 0, and (ii) commodity j,withv j i =0and v j j =1. Thus,foreachedgefi;jg, P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ?v k j )=1. Therefore, in accordance with Theorem 4.3 we can set u hk ij =1ifh = j and k = i,and u hk ij = 0 otherwise. This choice of variables in the projection cone imply the partition 22 1 2 P i P j6=i x ij 5. In general, consider a partition N 0 ;:::;N p . Without loss of generality assume that the root node is a node in N 0 . Suppose econ(N i ) = 2. Recall, from Property 3.4, if econ(N i )=2 the improved flow formulation must contain two commodities: one with origin n i 2N i and destination some node m i 62N i , and one with destination n i 2N i and origin m i 62N i ,both with a flow requirement of econ(N i )=2=1. Leti denote the commodity with destination node n i 2 N i (and origin m i 62 N i ) and a requirement of 1. Similarly, if econ(N i )=1 and i6= 0, the improved flow formulation must contain a commodity i with destination a node n i 2N i (the origin would be the root node) and a requirement of 1. For commodities 0;:::;p,weset v k i = ( 1ifi2N k , 0otherwise, and set v k i =0otherwise. With this choice of values for the v k i variables, we ensure that for all edges fi;jg across the partition P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ?v k j ) = 1 and for edges fi;jg not in the partition P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ?v k j ) = 0. Thus, by choosing the values of u kh ij as indicated by Theorem 4.3, we nd that ij = P k2K P h2K u kh ij is 1 if i and j are in di erent sets of the partition and ij =0otherwise. Also, 0 = P k2K v k D(k) = p+1, since v k D(k) = 1 for commodities 0;:::;pand v k D(k) =0otherwise. If all the nodes with a connectivity requirement of two lie in one of the sets (i.e., N 0 ) of the partition or the problem has no node with a connectivity requirement of two (in this case the problem is a Steiner tree problem), by Property 3.4, there is no commodity in the improved flow formulation with destination in N 0 . Consequently, we select p commodities with destinations in N 1 ;:::;N p and origin in N 0 (i.e., the root node). With the same choice of v k i for k =1;:::;p(i.e., v k i =1ifi2N k and 0 otherwise), for all edges fi;jg across the partition, max ( P k2K max (0;v k j ?v k i ); P k2K max (0;v k i ?v k j )) = 1; and for edgesfi;jgnot in the partition, P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ?v k j ) = 0. Thus, in accordance with Theorem 4.3 the edges across the partition have coe cient 1; all others have coe cient 0. Since we have only p commodities, the resulting righthand side is 0 = P k v k D(k) = p. 5.1 Partition Inequalities for the Unitary NDC Problem Since the structure of the projection cone obtained from the improved flow model for the NDLC problem and the improved flow model for the unitary NDC problem are identical, any member of the cone that provides a valid inequality for the NDLC problem also provides a valid inequality for the unitary NDC problem. Consider a partition N 0 ;:::;N p . Without loss of generality assume that the root node is a node in N 0 . Consider any set N i of the partition. If econ(N i ) 2, Property 3.4 23 implies the improved flow formulation must contain two commodities: one with origin n i 2N i and destination some node m i 62N i , and one with destination n i 2N i and origin m i 62N i , both with a flow requirement of econ(N i )=2. Let i denote the commodity with destination node n i 2N i (and origin m i 62N i ) and a requirement of econ(N i )=2. Similarly, if econ(N i )=1andi6= 0, the improved flow formulation must contain a commodity i with destination a node n i 2N i (the origin would be the root node) and a requirement of 1. For commodities 0;:::;p,weset v k i = ( 1ifi2N k , 0otherwise, and set v k i =0otherwise. We have not changed anything so far. These values for v k i variables are the same as for the NDLC problem. Therefore, for all edges in the partition, ij =1ifi and j are in di erent sets of the partition and ij = 0 otherwise. For commodities k =0;:::;p, q k =1if econ(N k ) = 1, and q k = econ(N k )=2 if econ(N k ) 2. Substituting these values, we obtain the following valid inequality: 1 2 k=p X k=0 X (N k ) x ij ( p if I 2 = ; 1 2 P i2I 2 econ(N i )+jI 1 j otherwise. (8) In this inequality, I 1 =fi : econ(N i )=1g and I 2 =fi : i2econ(N i ) 2g. But since, in the mixed integer program, the variables x ij are either 0 or 1 we can round up the righthand side in this inequality and still maintain feasibility. Thus, the following inequalities are valid: 1 2 k=p X k=0 X (N k ) x ij ( p if I 2 = d 1 2 P i2I 2 econ(N i )e+jI 1 j otherwise. (9) Gr?otschel, Monma and Stoer [GMS95b, Sto92] call inequalities (9) partition inequalities and show that under appropriate conditions they are facet de ning for the SND problem. Our derivation shows that these inequalities are valid for the more general unitary NDC problem. If the number of sets in the partition inequality with odd connectivity requirement greater than one is odd, then the improved undirected formulation implies a weaker form of the partition inequality that we refer to as weak partition inequalities (i.e., inequalities (8)). Otherwise, the formulation implies the partition inequality. Note that the weak partition inequalities are stronger than the cutset formulation (as long as I 1 6= ). Since the flow model implies the weak partition inequalities, and does not always im- ply the partition inequalities, we might like to characterize, in a certain sense, how much stronger a model containing the partition inequalities would be compared to a model con- taining the weak partition inequalities. 24 To compare two classes of valid inequalities, we use the following notion previously intro- duced by Goemans [Goe95]. LetX 1 andX 2 be two classes of valid inequalities. Then, the relative strength of the class of the valid inequalitiesX 1 to the class of the valid inequalities X 2 is de ned as max 8 < : fmin cx : x2R jEj + ; x2X 1 ; x2X 2 g fmin cx : x2R jEj + ; x2X 2 g 9 = ; : The relative strength measures how much, in the best case, the objective function of a linear program that contains the class of valid inequalities X 2 improves by adding to it the class of valid inequalitiesX 1 . The following result characterizes the relative strength of the partition inequalities with respect to the weak partition inequalities when (unlimited) edge replication is permitted. Theorem 5.1 The relative strength of the class of partition inequalitiesX 1 with respect to the class of weak partition inequalities X 2 is 10 9 : Proof: We will show that by multiplying any feasible solution (including any optimal solu- tion) to the linear programfmin cx : x2R jEj + ; x2X 2 g(we refer to this linear program as LP2) by 10 9 gives a feasible solution to the linear program fmin cx : x2R jEj + ; x2X 1 ; x2 X 2 g(we refer to this linear program as LP1). This result implies that the optimal value to LP1 is at most 10 9 times the optimal value to LP2. Note that the weak partition inequalities are implied by the partition inequalities. Consequently, we can delete x2X 2 from LP1. LP1 and LP2 di er when the righthand side of the weak partition inequalities is frac- tional. If we show the maximum ratio between the righthand side of any partition inequal- ity and its corresponding weak partition inequality is 10 9 , we have shown that the relative strength of the partition inequalities with respect to the weak partition inequalities is 10 9 . (Since multiplying any solution that satis es the weak partition inequalities by 10 9 gives a solution that satis es the partition inequalities.) The righthand sides of the weak partition inequalities and the partition inequalities di er by at most 0.5. This happens when the cardinality of the setfi : econ(N i ) odd; and econ(N i ) 3gis odd (i.e., for an odd number of sets, econ(N i ) is (i) odd, and (ii) greater than or equal to 3). Noting that the partition contains at least two sets with the highest value of econ(N i ), we nd that the maximum ratio is obtained by considering a partition with three sets, each with connectivity 3. The righthand side for the weak partition inequality is 4.5 and the righthand side for the partition inequality is 5. The ratio is 10 9 . 6 Odd-Hole Inequalities Chopra and Rao [CR94a] introduced odd-hole inequalities for the Steiner tree problem. These inequalities have the following form. Consider a graph G p =(N p ;E p )withN p = 25 (T p [Z p ), T p = fa 0 ;a 1 ;:::;a p g the set of nodes with nonzero connectivity requirements, and Z p = fb 0 ;b 1 ;:::;b p g the set of nodes with zero connectivity requirements. The edge set E p consists of edges of the form fa i ;b i g, fa i ;b i?1 g and fb i ;b i?1 g for i =0;:::;p.Note that we de ne b ?1 = b p , a ?1 = a p , b p+1 = b 0 and a p+1 = a 0 . An odd-hole inequality is an inequality of the form X fi;jg2E p x ij 2p: When p is even, the graph G p is called an odd-hole. 2 Chopra and Rao [CR94a] show that if p is even and p 2, then an odd-hole inequality de nes a facet for the Steiner tree polytope on the graph G p . We extend the de nition of odd-hole inequalities to obtain the following valid inequalities for the NDLC problem. X fi;jg2E p x ij 8 > > < > > : 2(p+ 1) if at least two nodes have a connectivity requirement of two; 2p otherwise. To prove that these inequalities are valid, we now show how to project these inequalities from the improved undirected formulation. Consider the odd-hole shown in Figure 5. Nodes a 0 and a 1 have a connectivity require- ment of 2, and a 2 , a 3 and a 4 have a connectivity requirement of 1. The improved undirected formulation, with root node a 0 , has ve commodities. Commodities 1, 2, 3 and 4 have a 0 as the origin and a 1 , a 2 , a 3 and a 4 as the destination nodes. Commodity 5, which we will also refer to as commodity 0, has a 1 as the origin and a 0 as the destination. Note, with this notation, each commodity i has destination a i . In the example of Figure 5, for all commodities k =0;:::;4, let v k i =0ifi6= a k ;b k or b k?1 .Letv k a k =2andv k b k = v k b k?1 = 1. Notice that with this choice of values v i a i ?v i b i = v i+1 b i ?v i+1 a i =1 v i a i ?v i b i?1 = v i?1 b i?1 ?v i?1 a i =1 v i?1 b i?1 ?v i?1 b i = v i+1 b i ?v i+1 b i?1 =1: All other v k i ?v k j =0.Thus,foreachedgefi;jg, P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ? v k j ) = 1. Therefore in accordance with Theorem 4.3 we can set u (k+1)k a k b k , u (k?1)k a k b k?1 and u (k+1)(k?1) b k b k?1 to1fork =0;:::;4, and u hk ij = 0 otherwise. Since P k2K v k a k = 10, this choice of variables de nes the odd-hole inequality P fi;jg2E 4 x ij 10. In general, let node a 0 be the root node. For each node a l , select a commodity l with D(l)=a l . For commodities k2f0;:::;pg,set 2 The odd in odd-hole refers to the number of nodes with nonzero connectivity requirements. 26 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 r a 0 = 2 r a 1 = 2 r a 2 = 1 r a 3 = 1 r a 4 = 1 v b 1 = 1 1 v a 1 = 2 1 v b 0 = 1 1 v b 2 = 0 1 v b 3 = 0 1 v b 4 = 0 1 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 v a 2 = 0 1 1 v a 3 = 0 1 v a 4 = 0 v a 0 = 0 1 v b 1 = 1 2 v a 1 = 0 2 v b 0 = 0 2 v b 2 = 1 2 v b 3 = 0 2 v b 4 = 0 2 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 v a 2 = 2 2 2 v a 3 = 0 2 v a 4 = 0 v a 0 = 0 2 v b 1 = 0 3 v a 1 = 0 3 v b 0 = 0 3 v b 2 = 1 3 v b 3 = 1 3 v b 4 = 0 3 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 v a 2 = 0 3 3 v a 3 = 2 3 v a 4 = 0 v a 0 = 0 3 v b 1 = 0 4 v a 1 = 0 4 v b 0 = 0 4 v b 2 = 0 4 v b 3 = 1 4 v b 4 = 1 4 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 v a 2 = 0 4 4 v a 3 = 0 4 v a 4 = 2 v a 0 = 0 4 v b 1 = 0 0 v a 1 = 0 0 v b 0 = 1 0 v b 2 = 0 0 v b 3 = 0 0 v b 4 = 1 0 b 4 a 0 b 0 a 1 b 1 a 2 b 2 a 3 b 3 a 4 v a 2 = 0 0 0 v a 3 = 0 0 v a 4 = 0 v a 0 = 2 0 (a) (b) (c) (d) (e) (f) Figure 5: Projecting odd-hole inequalities for a ten node example. (a) Connectivity re- quirements (b) Value of the v 0 i variables (c) Value of the v 1 i variables (d) Value of the v 2 i variables (e) Value of the v 3 i variables (f) Value of the v 4 i variables. v k i = 8 > > < > > : 2ifi = a k ; 1ifi = b k or i = b k?1 ; 0otherwise, and set all other v k i values to zero. With this choice of the v k i variables, we once again ensure that P k2K max (0;v k j ?v k i )= P k2K max (0;v k i ?v k j ) = 1 for any edge fi;jg. Thus, by choosing the values of u kh ij as indicated in Theorem 4.3, we nd that ij = P k2K P h2K u kh ij is 1 for each edge fi;jg; and 0 = P k2K v k D(k) =2(p +1), sincev k D(k) = 2 for commodities 0;:::;p,andv k D(k) =0 otherwise. Suppose the graph G p has more edges than E p . What inequality is implied? Retain the same choice of v k i variables and consider an edge fi;jg62E p . This edge can be of three 27 types|fa i ;b j g, fb i ;b j g and fa i ;a j g. For edges of type fa i ;a j g, v j a j ?v j a i = v i a i ?v i a j =2: For edges of type fa i ;b j g62E p , j6= i and j6= i?1, v j b j ?v j a i = v j+1 b j ?v j+1 a i =1 and v i a i ?v i b j =2: Finally, for edges of type fb i ;b j g62E p , j6= i?1andj6= i+1, v j b j ?v j b i = v j+1 b j ?v j+1 b i = v i b i ?v i b j = v i+1 b i ?v i+1 b j =1: Thus, for any edge fi;jg62E p , X k2K max (0;v k i ?v k j )= X k2K max (0;v k j ?v k i )=2: Selecting u kh ij values as prescribed by Theorem 4.3, shows that ij = P k2K P h2K u kh ij is 2 for each edge fi;jg62E p . The projected inequality X fi;jg2E p x ij + X fi;jg2EnE p 2x ij 2(p+1) is called a lifted odd-hole inequality and is also a facet-de ning inequality for the Steiner tree problem (see Chopra and Rao [CR94a]). If the problem has no node with a connectivity requirement of two, it does not contain any commodity with destination the root node. Therefore we select p commodities, one for each node a 1 ;:::;a p , each with origin a 0 (the root node). With the same choice of v k i for commodities 1;:::;p, we obtain max ( P k2K max (0;v k j ?v k i ); P k2K max (0;v k i ?v k j )) = 1 for all edges fi;jg2E p and max ( P k2K max (0;v k j ?v k i ); P k2K max (0;v k i ?v k j )) = 2 for edges fi;jg2EnE p . Since we have only p commodities, the resulting righthand side is 0 = P k2K v k D(k) =2p. Both the odd-hole inequality and its lifted version are new valid inequalities for the NDLC problem. By examining the cone element that generates the odd-hole inequality, we can obtain valid odd-hole inequalities for the unitary NDC problem. In the next section, we study a generalization of odd-hole inequalities called combinatorial design inequalities. Therefore, to avoid repetition, we will not derive odd-hole inequalities for the unitary NDC problem. 28 7 Combinatorial Design Inequalities Goemans [Goe94] introduced a new class of facet de ning valid inequalities called combi- natorial design inequalities for Steiner tree problems. He showed that under appropriate conditions combinatorial design inequalities are facet de ning for the Steiner tree problem. He derives the combinatorial design inequalities by projecting from a node weighted (undi- rected) extended formulation for the Steiner tree problem. We show how to project out the combinatorial design inequalities from the improved undirected flow formulation (5), and as a result generalize the combinatorial design inequality to the unitary NDC problem, obtaining a new class of valid inequalities for this problem. The description of the combinatorial design inequality is fairly involved. Let T p = fa 0 ;:::;a p g be the set of nodes with nonzero connectivity requirements. Z q = N?T p = fb 0 ;:::;b q gis the set of nodes with zero connectivity requirements. Associate with each node a i of T p a subset T a i containing elements of Z q . Based on these subsets, we also de ne sets Z b i associated with each node b i in Z q . Z b i contains those elements of T p whose associated subset contains the node b i . For example, consider the odd hole with p = 4 (see Figure 5). T 4 = fa 0 ;a 1 ;a 2 ;a 3 ;a 4 g and Z 4 = fb 0 ;b 1 ;b 2 ;b 3 ;b 4 g.HereT a 0 = fb 0 ;b 4 g, T a 1 = fb 0 ;b 1 g, T a 2 =fb 1 ;b 2 g, T a 3 =fb 2 ;b 3 g, T a 4 =fb 3 ;b 4 g. Thus, the sets associated with the elements in Z 4 are Z b 0 =fa 0 ;a 1 g, Z b 1 =fa 1 ;a 2 g, Z b 2 =fa 2 ;a 3 g, Z b 3 =fa 3 ;a 4 g, Z b 4 =fa 4 ;a 0 g.(The odd-hole inequality is a special case of the combinatorial design inequality). De ne the (q +1) (p +1) matrix D =[d ij ]withd ij =1ifa j 2 Z b i and d ij =0 otherwise. The following two conditions are imposed on D:(i)rank(D)=p +1, and (ii) the unit vector e belongs to the cone generated by the columns of D; i.e., Dy = e for some vector y 2R (p+1) + . For any xed d>0, if we set = dy,weseethatD = de. Letting j denote the jth component of (i.e., j = dy j ), we see that X a j 2Z b i j = d for all i =0;1;:::;q: (10) If we select d so that the greatest common divisor of 0 ; 1 ;:::; p ; and d is 1, the coe cients of x ij in the following combinatorial design inequalities will be integer and as small as possible. For every edge fs;tg, de ne d st = 8 > > < > > : P k:a k 2(Z b i \Z b j ) k fs;tg=fb i ;b j g where b i ;b j 2Z p ; j fs;tg=fa j ;b i g with b i 2T a j ; 0otherwise. For the Steiner tree problem, the inequality X fi;jg2E (d?d ij )x ij dp; is a combinatorial design inequality. The odd-hole inequality is a special case of the combi- natorial design inequality when d =2, j =1forj =0;:::;p,andjT p j=jZ q j. 29 We extend the de nition of the combinatorial design inequality to obtain the following valid inequalities for the NDLC problem. X fi;jg2E (d?d ij )x ij 8 > > < > > : d(p+ 1) if at least two nodes have a connectivity requirement of two; dp otherwise. (11) Let us now project the combinatorial design inequality from the improved undirected flow formulation. In the improved undirected flow formulation, let node a 0 be the root node. For each node a l , select a commodity l with destination a l and set v k i = 8 > > < > > : d if i = a k ; k if i2T a k ; 0otherwise. Forallothercommoditiesk set v k i to zero. Consider an edge fs;tg = fa j ;b i g with b i 2 T a j .Whena j is the destination node, v j a j = d and v j b i = j if i2T a j . Consider any node a k 2Z b i nfa j g. v l a k 6= 0 only if a k is a destination node for commodity l, i.e., l = k and, in this case, v k b i = k and v k a j =0. Note that, v k b i ?v k a j = k .Thus, 3 X a k 2fZ b i nfa j gg v k b i ?v k a j = X a k 2fZ b i nfa j gg k (10) = d? j = v j a j ?v j b i : If a k 62Z b i ,thenv k a j = v k b i = 0. Therefore, P k2K max (0;v k a j ?v k b i )= P k2K max (0;v k b i ? v k a j )=d? j . By Theorem 4.3, in the projected inequality d? j is the coe cient of an edge fs;tg=fa j ;b i g with b i 2T a j . Consider an edge fs;tg = fb i ;b j g. For any commodity k with destination a k , v k b i and v k b j di er only if exactly one of b i and b j belongs to T a k .Ifb i belongs to T a k then v k b i = k and v k b j =0. Thusv k b i ?v k b j = k . Summing over all sets T a k that contain node b i but not node b j , we nd that X k:b i 2T a k ;b j 62T a k v k b i ?v k b j = X k:b i 2T a k ;b j 62T a k k (10) = d? X k:b i 2T a k ;b j 2T a k k : Similarly, summing up over all sets T a k that contain node b j but not node b i , we nd that X k:b j 2T a k ;b i 62T a k v k b j ?v k b i = X k:b j 2T a k ;b i 62T a k k (10) = d? X k:b j 2T a k ;b i 2T a k k : 3 The notation (10) = means that the equality follows from expression (10). 30 Therefore, P k2K max (0;v k b j ?v k b i )= P k2K max (0;v k b i ?v k b j )=d? P k:b j 2T a k ;b i 2T a k k .By Theorem 4.3, d? P k:b j 2T a k ;b i 2T a k k is the coe cient of an edge fs;tg = fb i ;b j g in the projected inequality. All the other edges are either of the form fs;tg = fa i ;a j g or fs;tg = fa j ;b i g with b i 62T a j . For any edge of the form fa i ;a j g, v j a j ?v j a i = v i a i ?v i a j = d for commodities i and j and v k a i = v k a j = 0 otherwise. Consider an edge of the form fs;tg = fa j ;b i g with b i 62T a j . For all commodities k with a k 2Z b i , i.e. a k is the destination, v k b i ?v k a i = k . For commodity j, a j is the destination and v j a j ?v j b i = d. For all other commodities k, v k a j = v k b i = 0. Therefore, for both edges of the form fs;tg = fa i ;a j g and fs;tg = fa j ;b i g with b i 62 T a j , we nd that P k2K max (0;v k s ?v k t )= P k2K max (0;v k s ?v k t )=d.By Theorem 4.3, d is the coe cient of these edges in the projected inequality. The righthand side of the projected inequality is 0 = P k v k D(k) = d(p+1) sincev k D(k) = d for commodities 0;:::;p,andv k D(k) =0otherwise. If the problem has exactly one node or no nodes with a connectivity requirement of 2, with the same choice of v k i variables we obtain the same coe cients for x ij and a righthand side of dp (there will be no commodity with destination the root node a 0 ). 7.1 Combinatorial Design Inequalities for the Unitary NDC Problem To conclude this discussion, we examine the valid inequality for the unitary NDC problem that is implied by the cone element that generates the combinatorial design inequality for the NDLC problem. For each node a k , k =0;:::;p, we select a commodity k with destination a k as follows. If the maximum connectivity requirement r a k of node a k is greater than or equal to 2, then we select a commodity k with destination node a k and flow requirement r a k =2. If the maximum connectivity requirement r a k of node a k is equal to 1, then we select a commodity k with destination node a k and flow requirement 1. Retain the same choice of variables v k i .The projected inequality is X fi;jg2E (d?d ij )x ij ( dp if L 2 = , d( 1 2 P l2L 2 r l +jL 1 j)otherwise. (12) In this inequality L 1 = fi : i2T p ;r i =1g and L 2 = fi : i2T p ;r i 2g (r i denotes the maximum connectivity requirement of a node). Once again, noting that the lefthand side should be integer if the x variables are integer, we can round up the righthand side, giving the inequality X fi;jg2E (d?d ij )x ij ( dp if L 2 = , (d d 2 P l2L 2 r l e+djL 1 j)otherwise. (13) We refer to inequalities (12) and (13) as weak combinatorial design and combinatorial design inequalities. Noting that d 1, it is easy to prove a result similar to Theorem 5.1| 31 namely, if edge replication is permitted, the value of the linear program determined by the weak combinatorial design inequalities is at least 10 9 ths the value of the linear program determined by the combinatorial design inequalities. 8 Nonunitary Problems So far we have restricted our attention to unitary problems. We now examine nonunitary NDC problems. Our starting point will be the special case of the Steiner forest problem. Recall that in the Steiner forest problem we are given a graph G =(N;E) and node sets T 1 ;T 2 ;:::;T P with T i \T j = for all node set pairs (i6= j). We wish to design a graph at minimum cost that connects the nodes in each node set (possibly by including multiple node sets in any connected component of the graph). For the unitary NDC problem, we derived a stronger formulation by generalizing a well- known directing procedure for the Steiner tree problem. The essential idea used was to direct the bridge edges of a solution to the unitary NDC problem in a manner akin to the directing procedure for the Steiner tree. Analogously, to strengthen the formulation for the nonunitary NDC problem we will rst determine how to strengthen the Steiner forest problem|a nonunitary NDC problem with each r st 2f0;1g|by directing it. To our knowledge, we are unaware of any models stronger than the cutset model for the Steiner forest problem. We believe the model we present is the rst directed model in the literature for this problem. 8.1 Directing the Steiner Forest Problem For convenience, we once again describe the cutset and undirected flow formulations for the NDC problem as applied to the Steiner forest problem. Cutset formulation for the Steiner forest problem Minimize X fi;jg2E c ij x ij (14a) subject to: X fi;jg2 (S) x ij 1 for all S, S N, S\T i 6= and (NnS)\T i 6= for some i, (14b) x ij 1 for all fi;jg2E (14c) x ij 0andinteger: (14d) In the following undirected flow formulation for the Steiner forest problem, we select a root node for each node set and send one unit of flow from the root node of each node set to every node in that node set. Recall that K denotes the set of all commodities in this formulation. 32 Undirected flow formulation for Steiner forest problem: Minimize X fi;jg2E c ij x ij (15a) subject to: X j2N f k ji ? X l2N f k il = 8 > > < > > : ?1 1 0 if i = O(k); if i = D(k); for all i2N and k2K otherwise; (15b) f k ij f k ji ) x ij for all fi;jg2E and k2K (15c) f k ij ;f k ji 0 for all fi;jg2E and k2K (15d) x ij 1 for all fi;jg2E (15e) x ij 0 and integer; for all fi;jg2E. (15f) If we assume each c ij 0, these formulations always have a Steiner forest as an optimal solution, and so each component of the forest is a tree. Nodes belonging to any node set T i , for any i, lie in the same component. As an example, Figure 6a shows the optimal solution to a Steiner forest problem with ve components. One component contains the two node sets T 1 and T 4 . All the other components do not contain nodes from other node sets. How might we direct the Steiner forest problem? Since each component in the optimal solution is a tree, we could arbitrarily choose a node in each component and direct each tree away from it. Unfortunately, before we solve the problem, although we know that nodes in each node set will lie in the same component, we do not know the number of components in the optimal solution and the node sets they contain. The problem is to determine, a priori, the root node for each component. For this reason, directing the Steiner forest problem raises di culties not encountered in directing the Steiner tree (and the unitary NDC) problem. To direct the Steiner forest, for each set T i , we choose an arbitrary root node r i 2T i .We then direct each component (tree) away from the lowest indexed root node that it contains. In the example shown in Figure 6(a), one component contains two node sets T 1 and T 4 . Since T 1 is the lowest indexed node set in this component, we have directed the component away from the root node r 1 of node set T 1 . All the other components contain nodes from only one node set T i ,fori =1;2;3;4;5, and we direct each of them away from the root node r i of node set T i . Figure 6(b) shows the forest after we have applied the directing procedure. For notation, if j 2T i ,welet (j)=r i denote the root node of the node set T i that contains node j. We refer to r i as node j?s root node. We also de ne T = T 1 [T 2 [:::T P , and let R be the set of all root nodes, that is, R =fr 1 ;r 2 ;:::;r P g. 33 j ? T 4 T 5 T 3 T 6T 2 T 1 U T 4 r 1 r 2 r 3 r 4 r 5 r 6 (a) Undirected forest. j ? T 4 T 5 T 1 U T 4 T 3 T 2 T 6 r 1 r 2 r 3 r 4 r 5 r 6 (b)Directeachforestawayfromthelowestindexedrootnodethatitcontains. Figure 6: Example of the directing procedure. 34 8.2 Improved Flow Formulation for the Steiner Forest Problem We model the Steiner forest problem using multicommodity flows. Since the network we obtain after directing the Steiner forest contains a directed path from the lowest indexed root node in a component to all other nodes in that component, we can send a unit of flow from the root node of each directed component to every node in that component. For each node j 2 T i ,withj 6= r i ,andforeachp i, we de ne a commodity with origin node r p and destination node j, and for each root node r i and for each p > < > > : = ?1 1 0 if i = O(k); if i = D(k); otherwise; 9 > > = > > ; 8i2N; and k2K; (16b) X k2CD(i) X j2N f k jD(k) =1 forali2TnR (16c) X j2N f k jD(k) X j2N f k jD(k ) 8i2TnR;8k2CD(i), s.t. O(k)=O(k ); and D(k )= (i); (16d) X k2H f k ij + X k2 H f k ji x ij for all fi;jg2E,and all H; H pairs in H (16e) X i2N X k2H f k ij 1 for all j2N,and all H in H (16f) f k D(k)l =0 for all l2N,and k2K (16g) f k ij f k ji ) 0 for all fi;jg2E,and k2K (16h) x ij 2f0;1g for all fi;jg2E. (16i) 35 Constraints (16b), (16c), and (16g) ensure that each node i in TnR obtains a unit of flow from either its root node, or the root node of a lower indexed node set. Constraints (16d) and (16g) ensure that if node i2T j , i6= r j , is supplied by a commodity k whose origin is not the root node of set T j , then its root node also is supplied from the origin of com- modity k (i.e., its root node belongs to the same component that it belongs to). Note that constraint (16g) simply states that flow of a commodity out of its destination node is zero, and so allows us to simplify notation in constraints (16c) and (16d) (they contain only terms for flow into the destination node). Constraint (16e) follows from the property that in an optimal solution flow travels in only one direction across an edge, and all the flow across an edge originates from the same source (the root node of the component the edge belongs to). Constraint (16f) follows from the fact that flow into any node in a component originates from a single node (the root node of that component). Figure 7 shows that the improved undirected flow formulation is stronger than the cutset formulation (or undirected flow formulation, since they are equivalent) for the Steiner forest problem. In this example T 1 =fa;dg, T 2 =fb;cg, and each edge has a cost of 1 unit. The optimal solution to the cutset formulation sets x ab = x bd = x dc = x ca =0:5withacost of 2 units. In the improved undirected flow formulation, we select node a as the root of node set T 1 , and select node b as the root of node set T 2 . This formulation contains four commodities. Commodities 1, 2, and 3 have origin node a and destinations nodes b, c and d. Commodity 4 has origin node b and destination node c. The optimal solution to the linear programming relaxation of the improved undirected flow formulation sets x ab = x bd = x ad =1,f 2 ac = f 1 ab = f 3 ab = f 3 bd = 1 (notice that all the commodities originate at the node a, the lowest indexed root node of the optimal solution), and has a cost of 3 units. Researchers have previously shown that the linear programming relaxations of the im- proved undirected flow formulation provide integer solutions (i.e., the edge design vari- ables are integer) for the Steiner tree problem when the underlying graph is series-parallel (see [PLG85]). The example in Figure 7 suggests that a similar result might be true for the Steiner forest problem (since the underlying graph in that example is series-parallel). However, adding a single edge fb;cg with unit cost to the example in Figure 7 shows that this property is not true. The optimal solution to the linear programming relax- ation of the improved undirected flow formulation is x ab = x bd = x dc = x ca = x bc =0:5, f 3 ab = f 3 bd = f 3 ac = f 3 cd = f 1 ab = f 2 ac = f 4 bc =0:5, with a cost of 2.5. The optimal integer solution and the optimal solution to the linear programming relaxation of the cutset for- mulation (or undirected flow formulation) are the same as in the previous example with a cost of 3 units and 2 units respectively. Thus improved flow-based models for Steiner forest problems de ned on series-parallel graphs need not have integer solutions. In this section we modeled the directing procedure on an undirected graph by using directed commodity flows. It is also possible to implement this directing procedure by 36 (c) a bc d (b) a bc d a b c d x ij = 1 x ij = 1 2 (a) Figure 7: (a) Graph with unit edge costs and T 1 = fa;dg,andT 2 = fb;cg.(b)Optimal solution to LP relaxation of cutset formulation. (c) Optimal solution to LP relaxation of improved undirected flow formulation. transforming the problem onto a directed graph. Raghavan [Rag95] describes equivalent directed flow formulations for the Steiner forest problem. To conclude this section, we note that we modeled the directing procedure using com- modity flows. Unlike the unitary NDC problem, there does not seem to be any obvious way to formulate a directed cut model. This shows the flexibility and power of flow models for modeling network design problems with connectivity constraints. 9 Directing the NDC Problem In this section we show how to generalize the directing procedure we have just presented for the Steiner forest problem to obtain a directed model for all NDC problems. As a result, we obtain a stronger formulation for the NDC model with edge-connectivity requirements. To sketch the basic idea underlying the directing procedure, consider any solution to the NDC problem. It consists of one or more connected components. By following the procedure described in Section 3 for each connected component of the integer solution to the NDC problem, we can direct each component. However, like the Steiner forest problem, because the problem is nonunitary, we do not know a priori the number of connected components in the optimal solution and the required nodes they contain. (We do know that if we delete the 37 edgesfs;tgwith r st = 0 from the requirement spanning tree, then the nodes that belong to the same tree (component) of the requirement forest will be in the same component of the solution to the NDC problem.) By combining the directing procedure for the unitary NDC problem and the directing procedure for the Steiner forest problem, we obtain a directed model for the NDC problem. The following commodity selection procedure outlines the essential idea of the directing procedure. We rst use the directing procedure described in Section 3.2 to direct the problem for commodities with r st 2. We then apply the Steiner forest problem?s directing procedure to direct the bridge edges in each component of the optimal integer solution to the NDC problem. Commodity selection procedure for Formulation (17) 1. Find the requirement spanning tree. 2. Delete all edges with r st = 0 from the requirement spanning tree. 3. For each edge fs;tg of the requirement spanning tree with r st 2, create two com- modities: one with origin node s and destination node t, and the other with origin node t and destination node s; each of these commodities has a flow requirement of r st =2. Let L denote this set of commodities. 4. Contract each edge fs;tg with r st 2 in the requirement spanning tree, creating aforestF in which r ij =1foralledgesfi;jg. Identify the connected components T 1 ;T 2 ;:::;T P of this forest. Denote any node in F created by contraction by any of the nodes it contains in the original requirement spanning tree (e.g., if contracting nodes s and t creates a node in F, then we denote the contracted node by s). Select a contracted node in each set T i as the root node r i of the node set T i . (If node set T i does not contain a contracted node, then arbitrarily select any one of the nodes as the root node.) Now create commodities as described for the Steiner forest problem with node sets T 1 ;T 2 ;:::;T P , and root nodes r 1 ;r 2 ;:::r P .LetK denote this set of commodities. Using this set of commodities we obtain the following improved undirected flow formu- lation. Improved undirected flow formulation for NDC problem: Minimize X (i;j)2E c ij x ij (17a) subject to X j2N f k ji ? X l2N f k il 8 > > < > > : = ?1 1 0 if i = O(k); if i = D(k); otherwise; 9 > > = > > ; 8i2N; and k2K; (17b) 38 X j2N f k ji ? X l2N f k il = ?q k q k 0 if i = O(k); if i = D(k); otherwise; 9 > > = > > ; 8i2N; and k2L; (17c) X k2CD(i) X j2N f k jD(k) =1 forali2TnR (17d) X j2N f k jD(k) X j2N f k jD(k ) 8i2TnR;8k2CD(i), s.t. O(k)=O(k ); and D(k )= (i); (17e) X k2H f k ij + X k2 H f k ji x ij for all fi;jg2E,and all H; H pairs in H (17f) X i2N X k2H f k ij 1 for all j2N,and all H in H (17g) f k ij +f h ji x ij for all k;h2K[L (17h) f k D(k)l =0 forall2N and k2K (17i) x ij 1 for all fi;jg2E (17j) f k ij f k ji ) 0 for all fi;jg2E,and k2K[L (17k) x ij 0 and integer, for all fi;jg2E. (17l) In this formulation, T = T 1 [:::[T P , R = fr 1 ;:::;r P g,and (j) denotes node j?s root node. CO(k), CD(k), and H are de ned as for the Steiner forest problem for the commodities k2K. If the requirement spanning tree contains no edgefs;tg,withr st = 1, Formulation (17) contains no commodities inK, and so the model contains only constraints (17c), (17h), (17j), (17k), and (17l). In this case, an argument similar to the one we used in Section 3.2 shows that this formulation is equivalent to the undirected flow formulation. Consequently, the improved formulation for the NDC problem is stronger than the undirected flow formulation only when the maximum spanning tree of the requirement graph contains some edge fs;tg with r st =1. 10 Concluding Remarks In this paper we showed how to improve formulations for NDC problems by generalizing directing procedures for NDC problems that have connectivity requirements r st of 0 or 1. For unitary NDC problems, we generalized the directing procedure for the Steiner tree problem and for nonunitary NDC problems, we generalized a new directing procedure for the Steiner forest problem. For unitary NDC problems we also showed that the projection of the new formulations 39 connectivity 2 node a bc 3 1 11 3 3 Steiner node edge cost d Figure 8: The flow formulation does not always give integer solutions. The LP solution is 7.5 and the optimal solution to the problem has cost 8. onto the space of the edge design variables contains three classes of valid inequalities (par- tition, odd-hole, and combinatorial design) that are generalizations of valid inequalities for the Steiner tree problem. For nonunitary NDC problems, we have not fully investigated the projection of the improved models (the projection cones are quite complex!) to determine valid inequalities implied by them in the space of the original edge variables. This is one potential direction of future research. Although we have shown that the improved flow formulation implies three classes of valid inequalities, some classes of facet de ning inequalities cannot be obtained by projecting from the flow formulation. Consider the SND problem shown in Figure 8. In this SND problem, nodes a, b,andc have a connectivity requirement of 2. Figure 8 shows the underlying graph and the cost of the edges. One optimal integer solution to the problem has the edges x ad = x db = x bc = x ca = 1 and has cost 8. Assume that in the improved flow model, commodity 1 is from node a to b, commodity 2 is from node a to c, commodity 3 is from node b to a and commodity 4 is from node c to a. The optimal linear programming solution to the improved undirected flow model (5) is f a1 ad = f a1 db = f c1 ad = f c1 dc = f a2 bd = f a2 da = f c2 cd = f c2 da =0:5, f a1 ab = f a1 ac = f a1 cb = f c1 ab = f c1 ac = f c1 bc = f a2 ba = f a2 ca = f a2 bc = f c2 ca = f c2 cb = f c2 ba =0:25, x ad = x bd = x cd =1andx ab = x bc = x ca =0:5 with cost 7.5. Gr?otschel, Monma and Stoer [GMS92b] introduced a class of inequalities for the SND problem, called r-cover inequalities, that eliminates such fractional solutions in the cutset model. It is unlikely that any polynomial size flow formulation implies the r-cover inequalities because, in a certain sense, the r-cover inequalities are complements of the blossom inequalities of the matching polytope. Therefore, if we can project out the r-cover inequalities from a polynomial size flow-based formulation, then we will have a polynomial size extended formulation for the matching polytope. However, Yanakakis [Yan88] showed that the matching polytope has no polynomial size extended formulation unlessP =NP. In this paper we did not consider node-connectivity requirements. Raghavan [Rag95] describes formulations and algorithms for NDC problems with node-connectivity require- 40 ments, as well as NDC problems with both edge- and node-connectivity requirements. We note however that because node connectivity implies edge connectivity, all the valid in- equalities derived for the edge-connectivity version of the NDC problem are valid for the node-connectivity version. Consequently, the partition, odd-hole and combinatorial design inequalities are valid for the node-connectivity version of the unitary NDC problem, and in some instances they can be facet de ning. For instance, Stoer [Sto92] shows that under certain conditions, the partition inequalities are facet de ning for the node-connectivity version of the SND problem. For the Steiner tree problem, Goemans and Myung [GM93] show that the choice of the root node in the directing procedure does not a ect the optimal objective value of linear programming relaxation of the improved undirected flow formulation. Using this result it is easy to show that the choice of the root node does not a ect the value of the linear programming relaxation of the improved undirected flow formulation for the unitary NDC problem. A natural question to ask for the Steiner forest problem is whether (i) the choice of root node for each node set, and (ii) the order of node sets, a ects the optimal objective value of the linear programming relaxation of the improved flow formulation for the Steiner forest problem. Although we have not proved this result in this paper, it is possible to establish this result. With some further argument, this result implies that for nonunitary NDC problems, the choice of root node for each set, and the order of node sets does not a ect the optimal objective value of the linear programming relaxation of the improved flow formulation. We note that the strong formulation for the Steiner forest problem also leads to a stronger formulation for a more general version of a problem called the Multi-Level Network Design problem that has been studied in the literature (see [BMM94]). In the two-level network design problem, we are given a network with two facility types available for each edge|primary and secondary|and a partition of the nodes into two types|primary nodes and secondary nodes. In this scenario, primary edges are more expensive than secondary edges. We wish to design a minimum cost connected network that connects the primary nodes to each other by primary edges. A more general version of this problem splits the primary nodes into primary sets T 1 ;:::;T P with T i \T j = for all primary node set pairs. We wish to design a minimum cost connected network that connects the nodes in each primary set by primary edges. We can interpret this problem as a Steiner forest problem overlayed on a tree (the primary edges in the optimal solution de ne a forest, and the edges in the optimal solution, both primary and secondary, de ne a tree). The stronger model for the Steiner forest problem yields a stronger model for this two-level network design problem (and for the multi-level network design problem). Although we did not use Nash-Williams theorem to obtain stronger formulations for the unitary NDC problem, the Nash-Williams result proves useful when designing dual-ascent algorithms from the improved flow formulation. For example consider the NDLC problem. 41 In this case because of Nash-Williams result, we can transform and thus formulate the prob- lem on a directed graph (recall this transformation is only valid when r st 2f0;1;eveng)). This, in turn, signi cantly simpli es the dual-ascent algorithm (as compared to performing dual-ascent using the improved undirected flow formulation). In a companion paper [MR99] we consider the NDLC problem and derive a dual-ascent algorithm using a directed flow model on a directed graph. Computational experiments reported in that paper show that the dual ascent algorithm applied to the directed flow model is able to solve problems with up to 300 nodes and 3000 edges to within a few percent of optimality, indicating that the linear programming relaxation of the improved flow formulation provides a good approxi- mation to this mixed integer program model. References [Ben62] J. F. Benders. Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik, 4:238{252, 1962. [BH93] S. C. Boyd and T. Hao. An integer polytope related to the design of survivable communication networks. SIAM Journal on Discrete Mathematics, 6(4):612{ 630, 1993. [BM93] M. Ba? ou and A. R. Mahjoub. The 2-edge connected Steiner subgraph polytope of a series-parallel graph. Technical report, D epartment d?informatique, Univer- sit e de Bretagne Occidentale, 6 Avenue Victor Le Gorgeu, B.P. 452, 29275 Brest Cedex, France, 1993. [BMM94] A. Balakrishnan, T. L. Magnanti, and P. Mirchandani. A dual-based algorithm for multi-level network design. Management Science, 40:567{581, 1994. [BP83] E. Balas and W. R. Pulleyblank. The perfectly matchable subgraph polytope of a bipartite graph. Networks, 13:495{516, 1983. [Cho89] S. Chopra. On the spanning tree polyhedron. Operations Research Letters, 8(1):25{29, 1989. [Cho92] S. Chopra. Polyhedra of the equivalent subgraph problem and some edge con- nectivity problems. SIAM Journal on Discrete Mathematics, 5:321{337, 1992. [CMW89] R. H. Cardwell, C. L. Monma, and T. H. Wu. Computer-aided design proce- dures for survivable ber optic networks. IEEE Journal on Selected Areas in Communications, 7:1188{1197, 1989. 42 [CR94a] S. Chopra and M. R. Rao. The Steiner tree problem I: Formulations, com- positions and extensions of facets. Mathematical Programming, 64(2):209{229, 1994. [CR94b] S. Chopra and M. R. Rao. The Steiner tree problem II: Properties and classes of facets. Mathematical Programming, 64(2):231{246, 1994. [Fra94] A. Frank. Connectivity augmentation problems in network design. In John R. Birge and Katta G. Murty, editors, Mathematical Programming: State of the Art 1994. The University of Michigan, 1994. [GH61] R. E. Gomory and T. C. Hu. Multi-terminal network flows. SIAM Journal of Applied Mathematics, 9:551{570, 1961. [GM90] M. Gr?otschel and C. L. Monma. Integer polyhedra arising from certain net- work design problems with connectivity constraints. SIAM Journal on Discrete Mathematics, 3:502{523, 1990. [GM93] M. X. Goemans and Y.-S. Myung. A catalog of Steiner tree formulations. Net- works, 23(1):19{28, January 1993. [GMS92a] M. Gr?otschel, C. L. Monma, and M. Stoer. Computational results with a cutting plane algorithm for designing communication networks with low-connectivity constraints. Operations Research, 40:309{330, 1992. [GMS92b] M. Gr?otschel, C. L. Monma, and M. Stoer. Facets for polyhedra arising in the design of communication networks with low-connectivity requirements. SIAM Journal on Optimization, 2, 1992. [GMS95a] M. Gr?otschel, C. L. Monma, and M. Stoer. Design of survivable networks. In M. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Models, volume 7 of Handbooks in Operations Research and Management Science, pages 617{672. North-Holland, 1995. [GMS95b] M. Gr?otschel, C. L. Monma, and M. Stoer. Polyhedral and computational in- vestigations for designing communication with high survivability requirements. Operations Research, 43:1012{1024, 1995. [Goe90] M. X. Goemans. Analysis of linear programming relaxations for a class of connec- tivity problems. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA 02139, 1990. Also Working paper OR 233-90, Operations Research Center, M.I.T. 43 [Goe94] M. X. Goemans. The Steiner tree polytope and related polyhedra. Mathematical Programming, 63(2):157{182, January 1994. [Goe95] M. X. Goemans. Worst-case comparison of valid inequalities for the TSP. Math- ematical Programming, 69(2):335{349, 1995. [Jai98] K. Jain. A factor 2 approximation algorithm for the generalized Steiner net- work problem. Technical report, College of Computing, Georgia Institute of Technology, Atlanta, GA 30332, 1998. [Mah94] A. R. Mahjoub. Two-edge connected spanning subgraphs and polyhedra. Math- ematical Programming, 64:199{208, 1994. [Men27] K. Menger. Zur allgemeinen kurventheorie. Fundamenta Mathematicae, 10:96{ 115, 1927. [MR99] T. L. Magnanti and S. Raghavan. A dual-ascent algorithm for low-connectivity network design. Technical report, OR-Center, Massachusetts Institute of Tech- nology, Cambridge, MA 02139, 1999. [MW95] T. L. Magnanti and L. A. Wolsey. Optimal trees. In M. Ball, T. L. Magnanti, C. L. Monma, and G. L. Nemhauser, editors, Network Models, volume 7 of Handbooks in Operations Research and Management Science, pages 503{615. North-Holland, 1995. [NW60] C. St. J. A. Nash-Williams. On orientations, connectivity, and odd vertex pair- ings in nite graphs. Canadian Journal of Mathematics, 12:555{567, 1960. [PLG85] A. Prodon, Th. M. Liebling, and H. Gr?oflin. Steiner?s problem on two-trees. Technical Report RO850315, D epartment de Math ematiques, EPF Lausanne, Lausanne, Switzerland, 1985. [Rag95] S. Raghavan. Formulations and Algorithms for Network Design Problems with Connectivity Requirements. PhD thesis, Massachusetts Institute of Technology, Cambridge, MA 02139, 1995. [RM97] S. Raghavan and T. L. Magnanti. Network connectivity. In M. Dell?Amico, F. Ma oli, and S. Martello, editors, Annotated Bibliographies in Combinatorial Optimization, pages 335{354. John Wiley & Sons, 1997. [Sto92] M. Stoer. Design of Survivable Networks. Number 1531 in Lecture Notes in Mathematics. Springer-Verlag, 1992. [Whi32] H. Whitney. Non-separable and planar graphs. Transactions of the American Mathematical Society, 34:339{362, 1932. 44 [Won84] R. T. Wong. A dual ascent approach for Steiner tree problems on a directed graph. Mathematical Programming, 28:271{287, 1984. [Yan88] M. Yannakakis. Expressing combinatorial optimization problems by linear pro- grams. In Proceedings of the 20th Annual Symposium on the Theory of Comput- ing, pages 223{228, 1988. 45