WIXLIB

22GOEMANS AND MYUNGwhere1Qwj i r{Cw,f):fk(6 (i))- fL ( 6 - ( i ) ) and k E T,uE A and kET,a E A and k E T,}.Since no Steiner arborescence contains any arc incoming to the root, we shall assume that A has no such arc.Equivalently, we could assume that w, 0 fora E 6 - ( r ) . This assumption is made throughout thepaper and turns out to be useful when dealing withbidirected graphs.Again, by the max-flow min-cut theorem, the projection of Qw,ontothe H’ variables can be expressed as[20]:Qw {w: w(6-(S)) 2 1r Z S and Sn T # 0 (4)with P,, C Q,,,. The inequalities (4) are known asSteiner dicut inequalities. This leads to the classicaldicut formulation for the Steiner arborescence problem:MinimizecowouEARelaxing the integrality on w , we obtain the linearprogramming relaxations (LP,f) and (LP,,,).These LPrelaxations are equivalent and, by the same argumentas for the Steiner tree relaxations, their common optimal value can be computed in polynomial time. Wong[301 proposed a dual ascent method to obtain goodapproximations o n this optimal value.The polyhedron Qw is equal to its integer hull whenIT1 2, when T V [lo] or when the underlying graphis series-parallel ([26], see also [13, 17, 281 for a slightgeneralization). The case T V corresponds to theminimum-cost arborescence problem.Tighter relaxations for the Steiner arborescenceproblem have been proposed. Chopra and Rao [7] derived classes of facet-defining valid inequalities thatcan be used to strengthen Qw. Myung [24] also deriveda class of facet-defining inequalities with 0-1 coefficients for the set covering formulation of the problem.Liu [18] gave a formulation for the Steiner arbores-cence problem based on an extended complete characterization of its polyhedron when (TI 3.1.3. The Bldlrected CaseAs we have previously mentioned, the Steiner treeproblem is equivalent to the bidirected Steiner arborescence problem. Therefore, any formulation or relaxation for the Steiner arborescence problem can beused for the Steiner tree problem. This gives formulations not in the space of the edge variables x but in thespace of the arc variables w (and possibly some additional variables). To obtain a formulation in the naturalset of variables, we need to use the linear transformation x, wy wji for all e {i, j}and eliminate the wvariables, i.e., project onto the x variables. In particular, for Q,,, we first define Q x w {(x. w ) :w E Q,,,andx e w y w,, for all e {i, j}E E } and then considerClearly, CPx Qx and QxS,, since,Qx projx(Qrw).forx E Qx, we have x(6(S)) w ( 6 - ( S ) ) w ( 6 ( S ) )2I by (4) and (5). Furthermore, from the results for Q,,,,we know that Qx int-hull(Q,) if IT1 2, T V , or Cis series-parallel.Little is known about Qx. Although Qx seems todepend on the choice of the root vertex r , we shallprove at the end of this paper that, in fact, it is independent of r . To the best of our knowledge, this fact,although believed by many authors, has not been established before. On the other hand, a complete description of Qxby linear inequalities is unknown. Chopra and Rao [6] described some of the linearinequalities defining Qx, namely, the class of Steinerpartition inequalities and the class of odd hole inequalities. Goemans 1121 obtained many more such inequalities and showed that Qx has a very rich and complicated structure. There is therefore no hope ofobtaining a simple description of Qx by linear inequalities. This has motivated many researchers to focustheir attention on bidirected formulations. Our maingoal in this paper is to show that simple undirecredformulations can be as tight as bidirected formulationsprovided that auxiliary variables are allowed. For thispurpose, we shall present three simple extended descriptions of ex.Two of them are new and presentedin the next section. The last one is obtained by “undirectizing” Qw/.

CATALOG OF STEINER TREE FORMULATIONS23For this purpose, consider1QX/1i r {(x, f):f k ( 6 ( i ) )- f k ( 6 - ( i ) ) oand k E T,i E \ { k r}J,e { i , j } E E and h , k E T,(6)a E A and k E T,}.The difference between Qxf and S, resides in the constraints (6). These constraints couple the flow corresponding to two commodities on arcs of opposite direction. This technique to strengthen rnulticommodityflow formulations has been used by Martin [21] andBalakrishnan et al. [2].Qd precisely constitutes an extended descriptionofex.Proposition 1. Qx/ {(x, f ): There exists (w,f ) E Qw,with x, wii wjifor all e { i , j } E E } .Proof. If ( w ,f)E Q ,and x, wii w,i for all e {i, j } E E, then (x, f )E QX,since, by (2), f swii wji x, for e { i , j } E E .On the other hand, assume that ( x , f)E ex,. By (6),descriptions. In [22], Martin derives polynomial-sizedformulations from separation algorithms. Most of thecompact formulations presented in this paper can beobtained in this way. In particular, Martin gave another compact description of the spanning tree polytope. The other technique is based upon dynamic programming algorithms for the associated combinatorialoptimization problems [23]. For example, a compactextended description of the Steiner tree polytope forseries-parallel graphs can be obtained from a dynamicprogramming algorithm based upon the decompositionof these graphs [23].ft,2maxh f maxk fj. Ix, for e { i , j } E E . Hence, wecan choose w such that maxh f 15 wii and x, wg w,ifor all e { i , j } E E [e.g., take w g f(x, rnaxh f wmaxk fj.11. Clearly, ( w , f) E Qwf.3Since Qxis integral when IT1 2, T V, or when Gis series-parallel,g Qx, gives a compact description ofthe dominant of the Steiner tree polytope for thesecases. In particular, when T V , we have a compactextended description of the dominant of the spanningtree polytope by a system of linear inequalities.'' Adescription of this dominant in the space of the x variables is given by Fulkerson (91 (see also [4]):x, 2 0e E E}2. TWO OTHER EXTENDEDFORMULATIONS FOR 9,In this section, we show that simple descriptions of QXcan be obtained by introducing some vertex variables.We present two such descriptions.The first description is obtained by keeping track ofwhich vertices are spanned by the Steiner tree. Consider additional variables yi for i E N V\T ( N is theset of Steiner vertices) with the meaning that yi 1 ifvertex i is spanned by the Steiner tree and 0 otherwise.If we know which vertices are spanned by the Steinertree, then we can use Edrnonds' complete description[8] of the spanning tree polytope to obtain a (partial)description of the Steiner tree polytope:x ( E ( S ) )5 y ( Nf lS) IT f l SI -1S f l T f 8 (8)where ( V l , . . . , Vk) is any partition of V and6(VI, . . . , V k ) denotes the set of edges whose endpoints belong to different members of the partition.Whether a linear program can be expressed in compact way is an important question (see [31]). Two general techniques have been proposed to derive compactx,z0Yk1'However editself is not integral [21].llln fact, Martin [21] showed that if we add the constraint x(E) IVI - I to Q,,, we obtain an extended description of the spanningtree polytope. This is a slightly weaker result.where S - k S\{k}. Constraints (8) and (9) are calledgeneralized subtour elimination constraints. Theseconstraints together with (7) and (10) enforce that,whenever yk E (0, 1) for all k E N, x is a convexe EE(10)k E N}(11)

24GOEMANSANDMYUNGcombination of incidence vectors of trees spanning TU {k E N :Yk 1).Relaxations based on Piy or on similar polyhedrahave been considered by Lucena [I91 and Goemans[12]. The separation problem for the constraints (8)and (9) can be solved by a sequence of IVI minimumcut problems (see [271 or Section 111.3.7. in [251).Therefore, optimizing over P i , can be done in polynomial time. P i y is integral when T V [8] or when G isseries-parallel [ 121.To relate this polytope to Q , , we consider a relaxation of P l y . It involves the same root vertex r as usedin the definition of Q, (although we shall show later onthat Q, is independent of r). LetIn the next theorem, we show that PI, constitutesan extended description of Q x .To show that P, C Q , , consider an (x, y ) E Pxy. Wewould like to prove the existence of a vector w E Q wwith x , wii wji for all { i , j } E E . Given (x, y ) E P r y ,defineTheorem 2. proj,(P,,) Q , .Proof Let P, denote proj,(PxY).We first show thatQx C P,. Let x E Q , and w E Qw be such that x, wii wjifor e {i, j } E E. Define yi w ( 6 - ( i ) )for i E V ,and y , 1. We claim that ( x , y ) E P r y , implying that xE P,. First, (x, y ) satisfies (12) since x ( E ) w ( A ) CiEv,w ( 6 - ( i ) ) y ( V , ) . To show that (x, y ) satisfies (13)for S f l T f 0, we consider two cases. If r E S, thenP y { w : w" wji x,w ( 6 - ( i ) ) yie (i, j } E Ei E V,where, as usually, DG ( V , A ) denotes the bidirectedgraph corresponding to G ( V , E ) in which the arcsincoming to r have been removed.Claim 1. P";' Q,,,.Let w E P Z . By definition, w satisfies all nonnegativity constraints (5).Consider now a set S such that r @ S and S n T # 0.We haveIf r E S, thenw ( - ( S ) )C ( 6 - ( i )-) w ( A ( S ) )IESproving that w also satisfies (4).5y(S\{r}) y ( S ) - 1Finally, it is obvious that (x, y ) satisfies (14), (IS), and(16).0Claim 2. PCy # 0.PY can be interpreted as the set of feasible flows win a transportation network (N, L ) . In this network,the set N of nodes consists of E and V,, the set L of

CATALOG OF STEINER TREE FORMULATIONSarcs is {(e,j) : e {i, j } E E}, the supply at node e E Eis x , , the demand at node i E Vr is yi and wii denotesthe flow on the arc (e, j ) , where e {i, j}.Although thearcs in L are uncapacitated, we can view this transportation problem as a capacitated transportation problemon a complete bipartite network with capacities eitherzero or infinity. Such a transportation problem is feasible if ,for any set M of nodes with no arc in L leavingM, the total supply in M is less or equal to the totaldemand in M , This version of the max-flow min-cuttheorem follows from Gale's characterization [I 1 1 ofthe feasible capacitated transportation networks. Inour case, the set M of nodes must satisfy ( M n E) CE ( ( M n V,) U { r } ) and the condition on the suppliesx,xe2e E E}.0 x ( M n E ) 5 x(E((M n V,) U {r}))(13)5y ( ( M rl Vr) U { r } ) - 1 y ( M r l Vr).Therefore, P? is nonempty.(24)Q,.Proof. Using Theorem 2, we shall instead show0This completes the proof of the theorem.The other description is obtained by introducingvertex variables zi(i E V ) whose values are functionsof the degree di of vertex i in the Steiner tree. Considerthe polyhedron(20)e E E}.Juenger and Pulleyblank [16] showed that R,, constitutes an extended description of the dominant of thespanning tree polytope when T V.Theorem 3. proj,(R,,)and demands is x ( M n E ) 5 y ( M n Vr). This lattercondition is clearly satisfied for any such M since 0The variables zk for k E T can be easily eliminatedfrom this formulation since, from (18) for S {k } and(19),we derive that z k 2 - x(6(k)) for k E T. If x isthe incidence vector of a Steiner tree whose degree atvertex i is d;,then ( x , z ) E R:, for z; 0 if dj 0 (vertexi is not spanned) and z; 2 - d; if di 2 1 . To verify that( x , z ) satisfies (18), it suffices to realize that x ( 6 ( S ) ) z(S)is equal to twice the number of connected components of the forest induced by the vertices in Sspanned by the Steiner tree.To relate R:, to Q,.we consider a relaxation of R:,involving the root vertex r :25that P, R,, where P, proj,(P,,) and R, ProjSR,,).We first show that P, C R,. Let ( x , y ) E P,, anddefine z; 2yi - x ( 6 ( i ) )for i E V . We claim that (2", z)E R,, . First, ( x , z ) satisfies z( V ) 2y( V ) - 2x(E)(L)2y,(la,- 2 and, hence, (21) holds. For a set S with S n T # 0 ,we havex(6(S)) z ( S ) x(6(S)) 2Y(S) - x ( 6 ( S ) )- 2X(E(S))(22.Thus, ( x , z ) satisfies (22). Since (23) and (24) are alsosatisfied, ( x , z) E R,,.To show that R, C P,, consider an (x, z ) E R,, anddefine y; (x(S(i)) t i )for i E V . We claim that ( x , y )E P,,. (12) holds since( x , y) satisfies also (13):Y ( S ) - 1 t x @ ( S ) ) x ( E ( S ) ) 4z(S)-1(22)1 x(E(S)).Moreover, (15) follows from (22) for S {k} and (16)follows from (23). Therefore, ( x , y ) E P,. This com8pletes the proof of the theorem.

26GOEMANS AND MYUNGFrom this relationship between R,; and P g , a polynomial time separation algorithm for the constraints(22)can be easily derived.We have presented four extended descriptions ofQ,, namely, Q,,, Q x f,P,, and Rxz.The latter two havethe advantage of requiring just [ VI additional variablesand this makes them more attractive to be used in acutting plane algorithm.Let ( x , y) E P h . Define zi 2yi- x ( 6 ( i ) )for i E V,where, by convention, yi 1 if i E T. We already knowthat (x. z ) satisfies (21)-(24), i.e., (17), (18) forS n T # 0, and (20).(18)fork E S C N also holds since3. TIGHTER RELAXATIONS Both Qx and Qw are of blocking type, i.e., their recession cones (or characteristic cones) consist of all nonnegative vectors. As a result, all relaxations mentioned in the previous sections are useful only fornonnegative cost functions. In this section, we are interested in bounded analogs to Qx and Q,,,. More precisely, we shall describe polyhedra Q: and Qk., whichare, respectively, contained within Qx and Qh, andwhose integer members are the incidence vectors ofSteiner trees and Steiner arborescences [i.e., int-hull(Q;) 9,and int-hull(QL) 9J.Qiis at least as complex as Q,. We should thereforenot expect a simple description of it in the space of thex variables. However, as for Q,, we derive simple extended descriptions of Q:. Two of these descriptionsappear to be the polyhedra P h and R:, introduced inthe previous section.Theorem 4. proj,(P:,) projx(R;z).Proof. The proof is almost identical to the proof ofTheorem 3. Let P i proj,(P:,) and R: proj,(R;z).QL, {w: w(6-(S))2Iw(6-(k)) I1w,z0Constraints (26)can be interpreted as saying that themaximum flow from r to k i n the network with capacityw, on arc a E A has value precisely w(S-(k)). Moreover, constraints (27)imply that this value is at most l.Optimizing over Q ; can be done in polynomial timesince the separation problem over (25) and (26)can besolved by a sequence of [ VI - I maximum flow problems. When the underlying path graph is series-parallel, Q is precisely the Steiner arborescence polytope9,[13].,,x(6(k)).Moreover, from ( l l ) , (x, z) satisfies (19) and, hence,belongs to R:, .On the other hand, consider an ( x , z) E R;; anddefine yi B(x(S(i)) z i ) for i E V. We already knowthat ( x , y) satisfies (l2)-(16). From (19), Yk 5 1 and,hence, ( x , y) satisfies (1 1) and yk 1 for k E T. Toshow that ( x , y) E P h (where y is restricted to itscomponents in N ) , we simply need to check (9) forkESLN:Motivated by the results of Section 2, we would liketo characterize proj,(P:,) or proj,(R:,) in the space ofthe w variables. In the following Theorem 5, we showthat, in this space, this polytope takes an especiallyattractive form:r e Sand S n T f 0(25)k E V,u E A}.Theorem 5. P i Q:, where Pi prujx(P:,) and Q: {x : x, wij wji for all e {i, j}E E for some w EQL .Proof. The proof is very similar to the proof of Theorem 2 and is therefore just outlined. First, we consider a vector w E Q ; and we let x, wij wji for e {i, j } E E. Define y i w(6-(i)) for i E N. It is easy toverify that ( x , y) E P l y . This proves that Q: C P:.To show that P: Q:, we consider an ( x , y) E Piv

CATALOG OF STEINER TREE FORMULATIONSand we definePLfY { w : w,, w,, x,Suppose that w violates the inequality (26) for someS and k. As it will be useful later, we do not assumee {i, j } E Ew(6-(i)) yiiENw(6-(i)) 1i E T,w, 027a E A}.By the same technique as in the proof of Theorem 2, itcan be shown that PZY E Q: and that P:"Y # 0. Thisrncompletes the proof of the theorem.Since P& (or Riz) is independent of the vertex r , sois Q:. Without extended undirected descriptions ofQ:,this might have been difficult to prove because Q;clearly depends on the vertex r.For the Steiner tree problem, we have seen that theintroduction of vertex variables y improves the formulation. This is typically not the case for Steiner arborescence formulations since Y k can be easily eliminatedas it must be equal to w(6-(k)).For example, introducing vertex variables y in Q:., we obtainthat S C N. Among all such inequalities, choose theone for which IS1 is minimal. If w, 0 for all a E(6-(k)\6-(S)), then w(6-(k)) w(6-(S)) and this is acontradiction. Let a ( i , k ) E (6-(k)\6-(S)) (i.e., i ES ) with w, 0. Since w, cannot be decreased withoutviolating one of the constraints defining Qw, there exists R with I @ R , R f l T # 0 , a 6 - ( R ) ,and w(6-(R)) 1. By submodularity of w(6(.)),we have w(6-(S)) w ( 6 - ( R ) )L w(6-(S U R ) ) w(6-(Sn R)). Since r ? (SU R ) and (S U R) n T # 0 , (4) says that w(6-(S U R))I1 w ( 6 - ( R ) ) .Therefore, w ( 6 - ( S ) ) Iw(6-(S r l R ) ) .This implies that w also violates (26) for S f l R and k .Since i E S\R, we have IS f l RI C IS1 and this contradicts the minimality of S.Suppose now that w violates the inequality (27) forkE V,. Let a ( i , k) E 6 - ( k ) with w, 0. Since w,cannot be decreased, there exists S with r 4 S,S f l Tf 0 , a E 6-(S) and w ( 6 - ( S ) ) 1. Hence, w ( 6 - ( S ) ) Cw(6-(k)).By the above argument, this gives a contradiction.Corollary 7 . Qx dom(Q:).Theorem 6 and Corollary 7 imply that most of therelaxations considered in this paper are equivalent forall nonnegative cost functions.This formulation for the vertex weighted Steiner arborescence problem is considered in Chopra and Gorres[5]. By the same argument as in Theorem 5 , we havethe Piy { ( x ,y ) :x, wij w,; for all e {i, j } E E andsome ( w , y ) E Q;,}. This contradicts the belief (see,e.g., [ 5 ] ) that vertex weighted bidirected relaxationsare tighter than their undirected counterparts.Corollary 8 . The LP relaxations obtained by optimizing over the following polyhedra are all equivalent forall nonnegative cost functions:From Corollary 7 and the fact that Q: is independent of r, we obtain the following previously mentioned result:Theorem 9. Qx is independent of the root r.4. 9, IS THE DOMINANT OF 9:Although Qw # Q ; , it appears that Qw and QL lead torelaxations that are equivalent for all nonnegative costfunctions. This follows from the following theorem:Theorem 6 . Qw is equal to the dominant dom(QL) ofQL, where dom(QJ { w : w L w' with w' E Q,,}.Proof. If w' E Q,, and w2Qw. Th

A Catalog of Steiner Tree Formulations Michel X. Goemansf Department of Mathematics, Room 2-372, Massachusetts Institute of Technology, Cambridge, Massachusetts 02139 Young-soo Myungt Department of Business Administration, Dan kook University, Cheonan, Chungnam 330, South Korea We present some existing and some new formulations for the Steiner tree and Steiner arborescence