Formulations for the Nonbifurcated Hop-Constrained Multicommodity Capacitated Fixed-Charge Network Design Problem Babacar Thionganea,b,∗ , Jean-Fran¸cois Cordeaub,c , Bernard Gendronb,d a b Kronos, 3535 Queen-Mary Road, Suite 650, Montr´eal, H3V 1H8, Canada Interuniversity Research Centre on Enterprise Networks, Logistics and Transportation (CIRRELT) c d HEC Montr´eal, 3000 Cˆ ote-Sainte-Catherine, Montr´eal, H3T 2A7, Canada Universit´e de Montr´eal, P.O. Box 6128, Station Centre-Ville, Montr´eal, H3C 3J7, Canada April 29, 2014 Abstract This paper addresses the multicommodity capacitated fixed-charge network design problem with nonbifurcated flows and hop constraints. We present and compare mathematical programming formulations for this problem and we study different relaxations: Lagrangean relaxations, linear programming relaxations, and partial relaxations of the integrality constraints. In particular, we show that the Lagrangean bound obtained by relaxing the flow conservation equations is tighter than the linear programming relaxation bound. We present computational results on a large set of randomly generated instances. Keywords: Nonbifurcated Hop-Constrained Multicommodity Network Design Problem; Formulations; Relaxations; Lagrangean Relaxation ∗ Corresponding author: [email protected] 1 Introduction Let G = (V, E) be a directed graph, where V is the set of nodes and E is the set of arcs. Let also K be a set of commodities, where each commodity k ∈ K is defined by an origin node sk , a destination node tk , and a demandP dk to be routed from sk to tk . Each arc k e ∈ E has a capacity ue that satisfies ue ≤ k∈K d . For each unit of commodity k k going through arc e, a nonnegative routing cost ce has to be paid. Moreover, a nonnegative design cost fe applies if there is a positive flow of any commodity on arc e. We consider the multicommodity capacitated fixed-charge network design problem with nonbifurcated flows and hop constraints (MCFDH) in which we want to minimize the sum of routing and design costs, while satisfying the demands and the capacity constraints. In addition, each commodity k has to be routed on a single path (nonbifurcated or unsplittable flows) whose length must not exceed lk . These hop constraints are useful in the context of reliability and quality of service in telecommunication and transportation networks, where limiting the number of arcs can reduce the probability of information loss or avoid unacceptable delays. When fe = 0, e ∈ E, and lk = |E|, k ∈ K, the MCFDH reduces to the multicommodity integral flow problem, which is NP-hard even if the number of commodities is two (Even, Itai and Shamir 1976). Thus, the MCFDH is itself NP-hard. Network design problems with bifurcated (or splittable) flows have been well studied (see Frangioni and Gendron 2009, and the references therein). Problems in which demands cannot be split arise in several applications in the areas of telecommunication and transportation. Brockm¨ uller, G¨ unl¨ uk and Wolsey (1999) studies a capacitated network design problem with non-linear costs arising in the design of private line networks; a similar problem is treated in Dahl, Martin and Stoer (1995). In Gavish and Altinkemer (1990) a non-linear network design problem is studied, while in Balakrishnan, Magnanti and Wong (1995) the authors present a decomposition algorithm for trees. Barhnart, Hane and Vance (2000) presents a column generation model and a branch-and-price-and-cut algorithm for the integer multicommodity flow problem. Problems involving hop constraints have been studied for minimum spanning tree problems in Gouveia, Simonetti and Uchoa (2011), Dahl, Gouveia and Requejo (2003), Gouveia and Requejo (2001), Gouveia (1995, 1996) and for Steiner tree problems in Costa, Cordeau and Laporte (2009) and Voß (1999), which both model the design of centralized telecommunication networks with minimum cost, as well as in Balakrishnan and Altinkemer (1992) for more general telecommunication network design problems. Survivability in network design problems, which deals with the design of networks that can survive arc or node failures, is investigated in Botton et al. (2013), Gouveia, Patr´ıcio and De Sousa (2008), Gouveia, Patr´ıcio and De Sousa (2006), Alevras, Gr¨otschel and Wess¨aly (1996, 1997). The effect of hop limits on the optimal cost is studied in Orlowski and Wess¨aly (2004) for a telecommunication network design problem. The convex hull of hop-constrained st-paths in a graph is studied in Dahl (1999) and Dahl and Gouveia (2004), which give a complete linear description when the number of hops is not larger than three, and propose classes of facet-defining inequalities for the general case. In this paper, we present three mathematical programming formulations for the MCFDH: the classical arc-based and path-based formulations, as well as the hop-indexed model. Different relaxations of these formulations are studied: Lagrangean relaxations, linear programming (LP) relaxations, and partial relaxations of the integrality constraints. We first focus on the hop-indexed model and study two Lagrangean relaxations, one obtained by relaxing the capacity constraints and the other by relaxing the flow conservation constraints. The first Lagrangean relaxation can be decomposed into |K| hop-constrained shortest path problems. We show that the hop-indexed formulation for that problem has the integrality property, which implies that its associated Lagrangean dual has the same value as the LP relaxation value of the hop-indexed model. The second Lagrangean relaxation can be decomposed into |E| 0-1 knapsack problems, which do not have the integrality property. Thus, the value of the 1 Lagrangean dual associated with this relaxation is greater than, or equal to, the LP relaxation value (this is a major difference with the bifurcated case, where a similar Lagrangean relaxation provides the same bound as the LP relaxation). A theoretical comparison of the LP relaxations of the formulations is then performed, showing that the path-based formulation and the hop-indexed formulation have the same LP relaxation value, which is not worse (and typically better) than the LP relaxation of the arc-based formulation. We also compare these relaxations with those obtained by relaxing the integrality of either the design variables or the flow variables. The paper is organized as follows. Mathematical programming formulations of the problem are presented Section 2. In Section 3, we present the Lagrangean relaxations and compare them to the LP relaxations and to the partial relaxations of the integrality constraints. Computational results are presented and analyzed in Section 4. Section 5 concludes the paper. 2 Problem formulations This section presents three mathematical programming formulations for the MCFDH, namely, the classical arc-based and path-based models, as well as the hop-indexed formulation. 2.1 Classical arc-based formulation This formulation is obtained by adding the hop constraints to the classical arc-based formulation of the multicommodity capacitated fixed-charge network design problem. It uses binary variables xke taking value 1 if the path of commodity k goes through arc e, and 0 otherwise, as well as binary variables ye taking value 1 if arc e carries flow for at least one commodity, and 0, otherwise. Given v ∈ V , we denote by ω + (v) the set of outgoing arcs from v and by ω − (v) the set of incoming arcs to v. XX X (C) min dk cke xke + fe ye k∈K e∈E e∈E v = sk 1 X X k k xe = −1 v = tk xe − e∈ω − (v) e∈ω + (v) 0 v ∈ V \ {sk , tk } X dk xke ≤ ue ye k∈K xke ≤ X ye xke ≤ lk e∈E xke ∈ {0, 1} ye ∈ {0, 1} k∈K (1) e∈E (2) e ∈ E, k ∈ K (3) k∈K (4) e ∈ E, k ∈ K (5) e ∈ E. (6) Constraints (1) are the flow conservation constraints, while (2) are the capacity constraints. Constraints (3) are redundant strong linking inequalities, which significantly improve the LP relaxation of the model. Inequalities (4) represent the hop constraints, which are valid because the flows are nonbifurcated. 2.2 Path-based formulation For every k ∈ K, let P k be the set of paths from sk to tk whose length is less than or equal to lk . The formulation uses binary variables ye as in the classical arc-based model, as well 2 as binary variables xp taking value 1 if p ∈ P k is used to satisfy the demand for commodity k, and 0 otherwise. Given a path p, we define aep = 1 if arc e P belongs to path p, and 0 otherwise. The cost per unit of flow on path p ∈ P k is then cp = e∈E aep cke . X X X dk cp xp + (P ) min fe ye e∈E k∈K p∈P k X xp = 1 k∈K (7) e∈E (8) e ∈ E, k ∈ K (9) p ∈ P k, k ∈ K e ∈ E. (10) (11) p∈P k X X k∈K aep dk xp ≤ ue ye p∈P k X aep xp ≤ ye p∈P k xp ∈ {0, 1} ye ∈ {0, 1} Constraints (7) ensure that a single path is selected for each commodity. Capacity and strong linking constraints are represented by (8) and (9), respectively. Finally, as a feasible path p ∈ P k has a length smaller than or equal to lk , the hop constraints are satisfied by any solution to this formulation. 2.3 Hop-indexed formulation For every commodity k, every arc e and every possible position q with 1 ≤ q ≤ lk , we define variable xkeq equal to 1 if arc e appears in position q in the path from sk to tk and 0, otherwise. k (I) min l X XX dk cke xkeq + k∈K e∈E q=1 k l X X k xkeq e∈ω + (v) q=1 X xkeq − e∈ω + (v) − X l X xkeq e∈ω − (v) q=1 X ( 1 = −1 v = sk v = tk xkeq−1 = 0 X fe ye e∈E k∈K (12) k ∈ K, v ∈ V \ {sk , tk }, q = 2, . . . , lk e∈ω − (v) (13) k l XX dk xkeq ≤ ue ye e∈E (14) e ∈ E, k ∈ K (15) xkeq ∈ {0, 1} k ∈ K, e ∈ E, q = 1, . . . , lk (16) ye ∈ {0, 1} e ∈ E. (17) k∈K q=1 lk X xkeq ≤ ye q=1 Constraints (14) and (15) are capacity and strong linking constraints, respectively. Constraints (12) and (13) are the flow conservation constraints at the origin/destination nodes and at intermediate nodes, respectively. Moreover, (13) guarantee the increasing positions of the arcs on any path. These two constraints, along with the integrality constraints (16), define the so-called hop-constrained shortest path subproblem (see Section 3.1). 3 In order to simplify the formulation and to avoid multiple solutions with the same objective function value, variables involved in the following constraints are removed: k ∈ K, e ∈ ω + (sk ), q = 2, ..., lk xkeq = 0 xkelk = 0 xkeq = 0 (18) − k k ∈ K, v ∈ V \ {t }, e ∈ ω (v) − + k k (19) k k ∈ K, e ∈ ω (s ) ∪ ω (t ), q = 1, ..., l . (20) Constraints (18) state that the outgoing flow from sk goes through one arc that has to be in position 1. Constraints (19) state that the destination of an arc in position lk has to be node tk . Constraints (20) eliminate loops involving the origin and the destination of any commodity. Similar hop-indexed formulations, which capture the hop constraints inside the definition of the variables, have already been used in Gouveia (1998), Voß (1999), Gouveia, Patr´ıcio and De Sousa (2006, 2008) and Costa, Cordeau and Laporte (2009). In Gouveia (1998) and Gouveia, Patr´ıcio and De Sousa (2006, 2008), the hop-constrained shortest path subproblem is defined in a layered graph where the length of any optimal path is equal to the hop constraint value, using self-loops with zero cost at the destination node if needed. The only difference between this formulation of the hop-constrained shortest path subproblem and ours is that in the latter, the subproblem is defined in the original graph and the length of an optimal path is not necessarily equal to the hop limit. The two formulations are nonetheless equivalent. 3 Relaxations We consider two Lagrangean relaxations for the hop-indexed formulation: the relaxation of the capacity and strong linking constraints, which we call the hop-constrained shortest path relaxation, and the relaxation of the flow conservation constraints, which we call the 0-1 knapsack relaxation. In addition, we study the relationships between these Lagrangean relaxations, the LP relaxations and the partial relaxations of the integrality constraints either on the design variables or on the flow variables. For any model (X), we denote its optimal value as v(X) and its LP relaxation as (X). 3.1 Hop-constrained shortest path relaxation m2 1 Let us associate Lagrange multipliers γ ∈ Rm + , m1 = |E| and δ ∈ R+ , m2 = |E||K|, respectively, to the capacity constraints (14) and to the strong linking constraints (15). When relaxing these constraints, the Lagrangean subproblem is defined as: k (LRIHSP (γ, δ)) min l X XX k (cke + γe + δek )dk xkeq k∈K e∈E q=1 + X e∈E (fe − γe ue − l XX bke δek )ye k∈K q=1 subject to (12)-(13) and (16)-(17). Problem (LRIHSP (γ, δ)) can be decomposed into two parts: a subproblem in x variables that separates into |K| hop-constrained shortest path problems with nonnegative costs (solvable in polynomial time, see Dahl and Gouveia 2004) and a subproblem in y variables that can be solved by looking at the sign of the cost of each variable. Hence, it is trivial to see that the subproblem in y variables can be solved by relaxing the integrality constraints. The subproblem in x variables can also be solved by relaxing the integrality constraints, as shown in the following proposition. 4 Proposition 1 The polytope defined by the following constraints, for each k ∈ K, is integral: k l X X k xkeq − e∈ω + (v) q=1 X xkeq − e∈ω + (v) xkeq ≥ 0 l X X xkeq = e∈ω − (v) q=1 X ( 1 −1 v = sk v = tk xkeq−1 = 0 (21) v ∈ V \ {sk , tk }, q = 2, . . . , lk (22) e ∈ E, q = 1, . . . , lk . (23) e∈ω − (v) Proof. The constraints are of the form Ax = b, where b is a vector of integers and A is a matrix containing coefficients of -1, 0 and +1. If each column of A has at most two non-zero entries, one +1 and one -1, then the matrix A is totally unimodular (Nemhauser and Wolsey 1999). We now show that each column of A satisfies this property. 1. Let q ∈ {2, ..., lk }, e = (u, v) 6= (sk , tk ). By (22), the column associated with xkeq contains exactly one +1, one -1 and rest are zeros; 2. Let q ∈ {1, ..., lk }, e = (sk , v), v 6= tk . The column associated with xkeq contains exactly one +1, by (21), at most one -1, by (22), and rest are zeros, by (22); 3. Let q ∈ {1, ..., lk }, e = (u, tk ), u 6= sk . The column associated with xkeq contains exactly one -1, by (21), at most one +1, by (22), and rest are zeros, by (22); 4. Let q ∈ {1, ..., lk }, e = (sk , tk ). The column associated with xkeq contains exactly one +1 and one -1, by (21), and rest are zeros, by (22). Since the right-hand side of each constraint is an integer, the polytope defined by constraints (21)-(23) is integral (Nemhauser and Wolsey 1999). This proposition implies that the Lagrangean subproblem can be solved by relaxing the integrality constraints on all variables, i.e., (LRIHSP (γ, δ)) has the integrality property. Using the following notation for the Lagrangean dual: 1 +m2 (LDIHSP ) max{v(LRIHSP (γ, δ)) | (γ, δ) ∈ Rm )}. + we thus have, by Lagrangean duality theory: Proposition 2 v(LDIHSP ) = v(I). 3.2 0-1 knapsack relaxation Let us associate Lagrange multipliers α ∈ Rn1 , n1 = 2|K|, to (12), and β ∈ Rn2 , n2 = P (|V |−2) k∈K (lk −1), to (13). When relaxing these constraints, the Lagrangean subproblem is defined as: (LRI01K (α, β)) min lk X XX c˜keq (α, β)xkeq + k∈K e∈E q=1 X e∈E fe ye + X (−αksk + αktk ) k∈K subject to (14)-(17), where c˜keq (α, β) is defined as: c˜keq (α, β) k k sk k tk k tk k d ceq + ζu αsk − ζv αtk − (1 − ζv )βvq+1 k k k k k = dk ckeq + (1 − ζus )βuq − ζvt αktk − (1 − ζvt )βvq+1 k k sk k tk k d ceq + (1 − ζu )βuq − ζv αtk q=1 q = 2, ..., lk − 1 q = lk with e = (u, v), and ζuw = 1 if u = w and 0 otherwise. (LRI01K (α, β)) decomposes by arc. For each arc e, we consider two cases: ye = 0: We then have xkeq = 0 for all k ∈ K, q = 1, . . . , lk with an objective function value 5 of 0. ye = 1: In this case, the objective function value and the values of the x variables can be obtained as follows. First, for each k ∈ K, we determine q k = arg minq=1...lk {˜ ckeq (α, β)} to P lk ensure that constraint q=1 xkeq ≤ 1 is satisfied. Then, we solve the following 0-1 knapsack problem: X X (Qe ) min{ c˜keqk (α, β)xkeqk s.t. dk xkeqk ≤ ue , xkeqk ∈ {0, 1}, k ∈ K}. k∈K k∈K Thus, for each arc e, we pick the cheapest of the two alternatives, ye = 0 or ye = 1, and derive an optimal solution out of it. Note that if we relax the integrality of the y variables, the Lagrangean subproblem would be solved in the same way, since it is easy to show then that the optimal solution for each arc e must satisfy ye = 0 or ye = 1. However, because the Lagrangean subproblem decomposes into |E| 0-1 knapsack problems, (LRI01K (α, β)) does not have the integrality property. If bifurcated flows were allowed instead of nonbifurcated flows, the Lagrangean subproblem would be solved in the same way by considering for each arc e the two alternatives ye = 0 and ye = 1 (whether or not the integrality of the y variables is relaxed). The subproblem solved for the case ye = 1 would then be a continuous knapsack problem and the Lagrangean subproblem would have the integrality property (Crainic, Frangioni and Gendron 2001). The Lagrangean dual associated with this relaxation is defined as: (LDI01K ) max{v(LRI01K (α, β)) | (α, β) ∈ Rn1 +n2 )}. Since (LRI01K (α, β)) does not have the integrality property, by Lagrangean duality theory, we have: Proposition 3 v(LDI01K ) ≥ v(I) and there exist instances for which the inequality is strict. Proof. Figure 1 shows a capacitated instance with no design costs and no hop constraints. There are two commodities, each with a demand of 2, that share the same origin, but have different destinations. Arcs leaving the origin of each commodity have a capacity of 3. One of these two arcs has a flow cost of 1, while all other arcs have no flow costs. The optimal solution to (I) sends 3 units of flow on the arc with no cost leaving the origin and 1 unit of flow on the arc with flow cost bequal to 1. This means that one of the two commodities has its demand split between two paths, which implies values of 1/2 for the corresponding x variables. The optimal value is v(I) = 1. By standard Lagrangean duality, v(LDI01K ) can be computed by optimizing over the polytope defined by the intersection of the flow conservation equations and the convex hulls of the 0-1 knapsack set for each arc. Clearly, the optimal solution to (I) is not feasible for this polytope. The optimal solution is in fact obtained by sending two units of flow of each commodity on each of the arcs from the origin, which is also the optimal solution to I. The optimal value is v(LD01K ) = 2. Thus, in this case, v(I) = 1 < 2 = v(LDI01K ). 3.3 Linear programming relaxations The following proposition establishes a comparison between the LP relaxations of the three formulations presented in Section 2. Proposition 4 v(C) ≤ v(P ) = v(I) and there exist instances for which the inequality is strict. Proof. v(C) ≤ v(P ) To prove this inequality, we consider the Lagrangean relaxation of constraints (2) and (3) HSP in formulation (C). By Lagrangean duality theory, we have v(C) ≤ v(LDC ), where 6 d1 = 2 d2 = 2 ue = 3, ce = 1 ue = 3 d1 = 2 d2 = 2 Figure 1: Instance showing that v(I) = 1 < 2 = v(LD 01K ). HSP (LDC ) is the Lagrangean dual derived from this relaxation. In the same way as for the hop-constrained shortest path relaxation presented in Section 3.1, the Lagrangean subproblem decomposes into two parts: a subproblem in x variables that separates into |K| hop-constrained shortest path problems with nonnegative costs and a subproblem in y variables that can be solved by looking at the sign of the cost of each variable. Thus, using the HSP classical Dantzig-Wolfe reformulation approach for the Lagrangean dual (LDC ), we can express any point in the convex hull of solutions to the Lagrangean subproblem using |K| convex combinations of the extreme points of the convex hull of solutions to the following constraints, for each k ∈ K: v = sk 1 X X k k xe − xe = −1 v = tk (24) + − k k e∈ω (v) e∈ω (v) 0 v ∈ V \ {s , t } X (25) xke ≤ lk e∈E xke ∈ {0, 1} e ∈ E. (26) Each of these extreme points corresponds to a hop-constrained path p ∈ P k . Thus, if we denote any such extreme point as ξ(p) and its convex combination weight as the variable θ(p), p ∈ P k ,Pwe can express each solution xk to the convex hull of (24)-(26) with the HSP ) can then be formula xke = p∈P k θ(p)ξe (p). The Dantzig-Wolfe reformulation of (LDC written as follows: XX X X HSP (LDC ) min dk cke θ(p)ξe (p) + fe ye k∈K e∈E p∈P k 7 e∈E e3 v1 e4 v3 v2 e5 e2 sk tk e1 Figure 2: Instance showing that v(C) < v(P ). X dk X e∈E (27) θ(p)ξe (p) ≤ ye e ∈ E, k ∈ K (28) θ(p) = 1 k∈K (29) θ(p) ≥ 0 k ∈ K, p ∈ P k (30) ye ∈ [0, 1] e ∈ E. (31) k∈K X θ(p)ξe (p) ≤ ue ye p∈P k p∈P k X p∈P k We remark that ξe (p) = aep , for each arc e ∈ E, commodity k ∈ K and path p ∈ P k . If we HSP let xp = θ(p), this reformulation of (LDC ) is precisely (P ). Thus, we have HSP ) = v(P ). v(C) ≤ v(LDC Now, consider the graph defined in Figure 2 with K = {k}, flow costs ce1 = c > 0, cei = c/4 for i = 2, .., 5, and design costs fe1 = f > 0, fei = f /4 − ǫ where ǫ > 0. Suppose that uei = dk = 1 and lk = 3. Thus, an optimal solution to (P ) sends one unit of flow on the path defined by arc e1 and v(I) = c + f. However, an optimal solution to (C) is xke1 = ye1 = 1/3, xkei = yei = 2/3, i = 2, .., 5 and its optimal value is v(C) = c + f − 8ǫ/3 = v(I) − 8ǫ/3. v(P ) = v(I) To prove this result, we follow a similar approach as above, by considering the Lagrangean relaxation of (14) and (15) in formulation (I). By Proposition 2, we have v(LDIHSP ) = v(I). Using again the classical Dantzig-Wolfe reformulation approach for the Lagrangean dual (LDIHSP ), we can express any point in the convex hull of solutions to the Lagrangean subproblem using |K| convex combinations of the extreme points of the integral polytope defined by constraints (21), (22) and (23). Each of these extreme points corresponds to a hop-constrained path p ∈ P k . Thus, if we denote any such extreme point as ξ(p) and its convex combination weight as the variable θ(p), p ∈ P k , we can express each solution xk P k to (21)-(23) with the formula xeq = p∈P k θ(p)ξeq (p). The Dantzig-Wolfe reformulation of (LDIHSP ) can then be written as follows: lk X X XX X θ(p)ξeq (p) + (LDIHSP ) min dk cke fe ye k∈K e∈E q=1 p∈P k 8 e∈E k l XX X dk θ(p)ξeq (p) ≤ ue ye e∈E (32) e ∈ E, k ∈ K (33) k∈K (34) θ(p) ≥ 0 k ∈ K, p ∈ P k (35) ye ∈ [0, 1] e ∈ E. (36) k∈K q=1 lk X X p∈P k θ(p)ξeq (p) ≤ ye q=1 p∈P k X θ(p) = 1 p∈P k Pk We remark that lq=1 ξeq (p) = aep , for each arc e ∈ E, commodity k ∈ K and path p ∈ P k . If we let xp = θ(p), this reformulation of (LDIHSP ) is precisely (P ). Thus, we have v(I) = v(LDIHSP ) = v(P ). Note that, without hop constraints, it is easy to show that v(C) = v(P ). This follows from the same proof technique as above, by observing that, without constraints (25), the shortest path subproblem for each k ∈ K, defined by (24) and (26), has the integrality HSP ). The equivalence between the LP relaxations of the property, and thus, v(C) = v(LDC path-based and hop-indexed formulations has been proved for the hop-constrained minimum spanning tree problem in Dahl, Gouveia and Requejo (2003), where the authors mention that the arguments of the proof can be used to prove the same result for more general problems. The next section focuses on improving the lower bound v(I) by studying partial relaxations of the integrality constraints. 3.4 Partial relaxations of integrality constraints In the LP relaxation of (I), both P the x and y variables can be fractional, i.e., (x, y) ∈ [0, 1]M × [0, 1]|E|, where M = |E| k∈K lk . When x is fractional, the flows can be bifurcated, i.e., several paths can be used to satisfy the demand for any commodity. When y is fractional, it is possible that only a fraction of the design cost associated with any arc is taken into account in an optimal solution in which there is flow on that arc. One possibility to improve the lower bound v(I) is to relax the integrality constraints only on a subset of the variables, either the x variables or the y variables, but not on both, as in (I). First, we consider the relaxation of the integrality of the y variables, denoted (Iy ). We then have the following result: Proposition 5 v(Iy ) = v(I). Proof. Since the design costs are nonnegative and the y variables appear only in the capacity and strong linking constraints, there is an optimal solution to (Iy ) that satisfies, for each arc e: lk lk n XX nX oo ye = max ( dk xkeq )/ue , max xkeq . k∈K k∈K q=1 q=1 P lk xkeq ∈ {0, 1}. ≤ 1, we must have q=1 Now, since the x variables are binary and k k P Pl P Pl Moreover, since ( k∈K q=1 dk xkeq )/ue ≤ 1 and ( k∈K q=1 dk xkeq )/ue = 0 if and only if Plk maxk∈K { q=1 xkeq } = 0, it follows that ye ∈ {0, 1}, i.e., there is an optimal solution to (Iy ) that is also an optimal solution to I. P lk k q=1 xeq 9 Thus, when relaxing the integrality of the y variables, we obtain, in fact, a model that solves the MCFDH. It is easy to see that the same result applies not only to the hop-indexed formulation (I), but also to the other models (C) and (P ). Second, we consider the relaxation of the integrality of the x variables, denoted (Ix ). We then have the following result: P Proposition 6 v(Ix ) = v(I) for any uncapacitated instance (i.e., ue = k∈K dk , e ∈ E). Proof. Let y be the values assigned to the y variables in an optimal solution to (Ix ). We can obtain the optimal values x to the x variables by solving the LP relaxation of the hop-indexed formulation of |K| hop-constrained shortest path problems. As a consequence of Proposition 1, this LP relaxation provides, for each commodity k, a set of paths from sk to tk with a length not exceeding lk . Hence, (x, y) is also an optimal solution to (I). When there are capacities, we have in general v(I) ≤ v(Ix ) ≤ v(I). It is interesting to know how the Lagrangean bound v(LDI01K ) compares with v(Ix ), since both are never worse that v(I). Proposition 7 There is no dominance between v(Ix ) and v(LDI01K ). Proof. Figure 3 shows an uncapacitated instance with no hop constraints and no flow costs. There are three commodities, each with a demand of 1, that share the same origin, but have different destinations. Arcs leaving the origin of each commodity have a design cost equal to 1, while all other arcs have no design costs. Since the instance is uncapacitated, (LRI01K ) has the integrality property and v(LDI01K ) = v(I). In addition, by Proposition 6, v(Ix ) = v(I). The optimal solution to (I) assigns the value 1/2 to all (possibly non-zero) variables with an optimal value v(I) = 3/2. The optimal solution to (I) consists in choosing two of the three arcs leaving the origin of each commodity and to send three units of flow on these arcs, one for each commodity. The optimal value is v(I) = 2. Thus, for this instance, we have v(LDI01K ) = v(I) = 3/2 < 2 = v(I) = v(Ix ). This example is an adaptation of Gomory’s example (reported in Krarup and Pruzan 1983) of a fractional instance to the so-called strong formulation of the uncapacitated facility location problem. Consider now the instance illustrated in Figure 1 (see proof of Proposition 3). Since there are no design costs, (Ix ) is the same as (I) for this instance. Hence, we have v(Ix ) = v(I) = 1 < 2 = v(LDI01K ). 3.5 Summary of bound relationships The following propositions summarize the relationships between the different lower bounds derived so far, including the LP relaxation bounds of the different formulations of the MCFDH, but with an emphasis on the stronger lower bounds derived from the hop-indexed model. Proposition 8 In the capacitated and nonbifurcated case, v(I) = ≥ ≥ ≥ = = ≥ v(Iy ) max{v(Ix ), v(LDI01K )} min{v(Ix ), v(LDI01K )} v(LDIHSP ) v(I) v(P ) v(C). Proof. Immediate from Propositions 2, 3, 4, 5 and 7. 10 d2 = 1 d1 = 1 d3 = 1 fe = 1 fe = 1 d1 = 1 d2 = 1 fe = 1 d3 = 1 Figure 3: Instance showing that v(LD 01K ) = v(I) = 3/2 < 2 = v(I) = v(Ix ). Proposition 9 In the uncapacitated and nonbifurcated case, v(I) = = ≥ = = = ≥ v(Iy ) v(Ix ) v(LDI01K ) v(LDIHSP ) v(I) v(P ) v(C). Proof. v(I) = v(Ix ) from Proposition 6. Moreover, Propositions 2, 4 and 5 hold. Finally, as the Lagrangean subproblem associated to (LD01K ) has the integrality property, we have v(LDI01K ) = (I). Proposition 10 In the bifurcated (capacitated or uncapacitated) case, v(I) ≥ = = = v(LDI01K ) v(LDIHSP ) v(I) v(P ). Proof. The LP relaxations of (I) and (P ) are the same whether the flows are bifurcated or not, so Proposition 4 holds for these formulations. We have removed (C) from this comparison, as it is no more a valid model in the presence of hop constraints if the flows are bifurcated. Also, Proposition 2 obviously holds when the flows are bifurcated. As discussed in Section 3.2, v(LDI01K ) = v(I) is verified in the bifurcated and capacitated case, and the relation remains obviously valid in the bifurcated and uncapacitated case. This picture of lower bound comparisons among the different relaxations is completed by the observation made at the end of Section 3.3: without hop constraints, we have v(C) = v(P ) (and (C) is then a valid model, whether the flows are bifurcated or not). Thus, in the case where hop constraints are not active, all the bound comparisons established in the three propositions above hold with this single modification. 11 4 Computational results The purpose of our computational experiments is to compare in practice 1) the LP relaxation values of the hop-indexed and classical arc-based formulations, v(I) and v(C); 2) the LP relaxation and the Lagrangean dual bounds, v(I) and v(LDI01K ); 3) the Lagrangean dual bound and the value of the partial relaxation of the integrality constraints on the flow variables, v(LDI01K ) and v(Ix ). We have performed a series of experiments on 137 instances among those used by Crainic, Frangioni and Gendron (2001). The hop constraint parameter lk of a commodity k has been according to κk + 1 + rk , where rk is uniformly h generated i |V | k distributed over the interval 0, 4 and κ denotes the length of a shortest path from sk to tk . The characteristics of the instances are described in Table 1. Problem R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 R11 R12 R13 R14 R15 R16 R17 C1 C2 C3 C4 C5 C6 C7 C8 #Instances 6 2 6 3 7 6 6 6 5 6 5 6 9 6 9 9 9 3 4 4 4 4 4 4 4 #Nodes 10 10 10 10 10 10 10 10 20 20 20 20 20 20 20 20 20 20 20 20 20 30 30 30 30 #Arcs 35 35 60 60 60 82 83 83 120 120 120 220 220 220 314 318 315 230 230 300 300 520 520 700 700 #Commodities 10 25 10 25 50 10 25 50 40 100 200 40 100 200 40 100 200 40 200 40 200 100 400 100 400 Table 1: Characteristics of the 137 instances used All bounds are computed with CPLEX 12.3, except v(LDI01K ), which is obtained with the following subgradient method. Starting from an initial multiplier u0 , the method generates a sequence of multipliers using the formula: ul+1 = ul − λl dl . ||dl || Here, λl is the step size and dl is the step direction. We consider the modified CameriniFratta-Maffioli rule (Camerini, Fratta and Maffioli 1975): dl = σ l + µl dl−1 , 12 l where µl = ||d||σl−1|||| if the scalar product < σ l , dl−1 > is negative, and µl = 0 otherwise. The step size is computed as: v l − v(LRI01K (ul )) , λl = τ l ||dl || where 0 < τ l < 2, v l is an estimation of the optimal value of the MCFDH and v(LRI01K (ul )) denotes the value of the Lagrangean relaxation problem with the current Lagrange multipliers ul . In our experimentation, v l is set to 2 v ∗ , where v ∗ is the best Lagrangean bound obtained so far. The value of τ l is adjusted as follows: it is multiplied by a factor ρ < 1 if, after 10 iterations, there is no improvement, but its minimum value is set to 10−3 . The algorithm stops after 1000 iterations or when the relative distance between ul+1 and ul is lower than 10−7 . The 0-1 knapsack problem arising in the Lagrangean subproblem is solved using the hybrid code of Bourgeois and Plateau (1992), which combines dynamic programming and enumeration, shown to be efficient for difficult instances. The maximum size of the subproblem being solved by dynamic programming has been set to 50. The code has been implemented in C++, using the g++ compiler and all experiments have been performed on a Linux machine, operating at 3.07 GHz. The computational results are presented in Table 2, which displays: - T(X), the average computing time in seconds for model X, where X represents one of the five formulations: (C), (I), (LDI01K ), (Ix ) and (I); note that formulation (I) has been used instead of (Iy ), as it gave slightly faster computing times - G(X), the average relative gap (in percentage) between model X (X different from C) and formulation C; a positive value means that (X) is better than (C). From the results shown in Table 2, we can draw the following observations: • When comparing (I) and (C), we observe that the average gap G(I) obtained, although always positive, is never greater than 2.26% (problem C2), and that the computing time for (C) is up to three times better. • The Lagrangean bound v(LDI01K ) is consistently better than v(I), the lower bound obtained from the hop-indexed LP relaxation. In particular, we observe that G(I) is lower than or equal to 2.26%, while G(LD01K ) is always greater than this percentage, except for the last three sets of instances, C6, C7 and C8. The average gap difference between (LDI01K ) and (I) reaches up to 13% (for R1 instances), although the average gap difference is less than or equal to 10%. • The average computing time for the hop-indexed LP relaxation (I) is most of the time smaller than that for the subgradient method to compute v(LDI01K ). Indeed, it takes less than one second for (I) to solve 11 of the sets of problems, while the subgradient method took up to 18 seconds for the same sets. For larger problems such as R17 and C8, however, the Lagrangean dual solution time dominates that of (I), performing better, with relative improvements of 39% and 55%, respectively. • For 17 problems out of the 25, (LDI01K ) generated lower bound values that are greater than or equal to the bound values obtained by solving the mixed-integer relaxation (Ix ). • Solving the mixed-integer formulations takes much more time than solving the Lagrangean dual formulation, except for small instances. The subgradient method never took more than 9 minutes to solve any of the sets of problems, while the computing times have been restricted to 2 hours, and sometimes to 12 hours, for both (Ix ) and (I). Note that these time limits have been reached for both formulations in many instances. We also observe that no formulation between (Ix ) and (I) is clearly faster than the other. 13 Problem T(C) G(I) T(I) G(LDI01K ) R1 0.00 0.05 0.00 13.60 R2 0.00 0.03 0.00 9.53 R3 0.00 1.28 0.00 10.44 R4 0.01 0.73 0.01 2.95 R5 0.07 0.76 0.08 6.05 0.00 0.19 0.01 10.10 R6 R7 0.01 0.67 0.02 3.60 R8 0.12 1.74 0.12 8.19 0.17 1.49 0.21 8.77 R9 R10 2.04 1.51 3.32 5.32 6.65 0.38 14.27 3.42 R11 R12 0.57 2.01 0.83 3.77 R13 6.58 1.27 9.41 10.87 R14 46.36 1.77 99.12 2.58 R15 1.13 0.64 1.69 9.55 14.41 1.68 22.67 6.84 R16 99.72 1.34 203.31 5.59 R17 C1 0.04 0.25 0.10 5.49 36.84 2.26 53.23 2.28 C2 C3 10.61 0.54 16.77 3.51 C4 23.18 0.55 49.68 2.73 16.84 0.93 42.64 2.63 C5 C6 187.85 0.45 582.68 1.38 C7 90.36 0.46 252.05 2.20 486.68 0.39 1245.42 1.44 C8 * : computing time limited to 2 hours **: computing time limited to 12 hours T(LDI01K ) 0.47 1.30 0.50 2.00 4.25 0.71 2.05 5.23 10.75 27.40 57.90 17.66 42.63 90.29 22.38 58.39 123.60 18.77 100.85 41.00 94.79 124.21 443.71 253.19 550.73 G(Ix ) 3.47 1.00 3.64 2.22 3.57 4.11 2.28 4.38 5.58 4.65 2.84 5.64 5.42 7.21 4.68 6.36 11.35 1.12 6.63 2.22 3.39 3.56 2.63 2.15 4.07 T(Ix ) 0.04* 0.06* 0.04* 0.15* 8.75* 0.06* 0.33* 8.65* 56.05* 2096.03* 2992.89* 935.11* 5027.53* 5018.21* 2637.46* 5302.25* 6477.25* 6.15* 7179.99* 1801.73* 5385.87* 5562.18* 34105.48** 32398.15** 42723.62** G(I) 14.21 9.61 10.50 3.42 8.27 10.22 3.85 10.35 10.94 9.30 9.66 6.27 14.89 13.70 11.16 13.69 15.19 5.53 9.07 6.27 7.41 6.36 5.35 4.50 6.58 T(I) 0.03* 0.06* 0.04* 0.13* 7.58* 0.06* 0.18* 25.93* 19.54* 5065.66* 7178.70* 395.69* 4162.07* 6218.10* 67.90* 5649.41* 7179.23* 2.13* 7178.90* 1797.15* 5385.17* 4150.08* 34099.42** 22458.45** 40886.88** Table 2: Comparison between the different lower bounds over 137 instances 5 Conclusion In this paper, we have presented several formulations for the MCFDH. We have established relationships between different lower bounds in the bifurcated or nonbifurcated cases and in the capacitated or uncapacitated cases. The mixed-integer formulation obtained by relaxing the integrality of the design variables is equivalent to solving the MCFDH. There is no dominance between the mixed-integer relaxation derived from the problem with bifurcated flows and the Lagrangean relaxation of the flow constraints of the hop-indexed formulation. However, our computational experiments have shown that the Lagrangean bound is better for most instances, while also being faster to compute. The Lagrangean bound is also better in theory and in practice than the hop-indexed LP relaxation bound, although it generally takes more time to compute. Overall, the Lagrangean relaxation method seems to offer a good tradeoff between computing time and bound quality. Further investigations involving combinations of this Lagrangean relaxation with primal heuristics would be of interest. Acknowledgments Funding for this project has been provided by the Natural Sciences and Engineering Council of Canada (NSERC). This support is gratefully acknowledged. We thank two anonymous referees whose comments have helped us to improve our paper. 14 References Alevras D., Gr¨otschel M., Wess¨aly R. “A network dimensioning tool”, Technical Report SC 96-49, Konrad-Zuse-Zentrum fur Informationstechnik, Germany, 1996. Alevras D., Gr¨otschel M., Wess¨aly R. “Capacity and survivability models for telecommunication netoworks”, Technical Report SC 97-24, Konrad-Zuse-Zentrum fur Informationstechnik, Germany, 1997. Balakrishnan A., Altinkemer K. “Using a hop-constrained model to generate alternative communication network design”, INFORMS Journal on Computing 4 (1992) 195-205. Balakrishnan A., Magnanti T.L., Wong R.T. “A decomposition algorithm for local access telecommunications network expansion planning”, Operations Research 43 (1995) 58-76. Barnhart C., Hane C.A., Vance P. “Using branch-and-price-and-cut to solve origindestination integer multicommodity flow problems”, Operations Research 48 (2000) 318-326. Botton Q., Fortz B., Gouveia L., Poss M. “Benders decomposition for the hopconstrained survivable network design problem”, INFORMS Journal on Computing 25 (2013) 13-26. Brockm¨ uller B., G¨ unl¨ uk O., Wolsey L.A. “Designing private line networks - Polyhedral analysis and computation”, CORE DP9647, Universit´e Catholique de Louvain, 1999. Camerini P.M., Fratta L., Maffioli F. “On improving relaxation methods by modified gradient techniques”, Mathematical Programming Study 3 (1975) 26-34. Costa A., Cordeau J.-F., Laporte G. “Models and branch-and-cut algorithms for the Steiner tree problem with revenues, budget and hop constraints”, Networks 53 (2009) 141-159. Crainic T.G, Frangioni A., Gendron B. “Bundle-based relaxation methods for multicommodity capacitated fixed-charge network design problems”, Discrete Applied Mathematics 112 (2001) 73-99. Dahl G. “Notes on polyhedra associated with hop-constrained paths”, Operations Research Letters 25 (1999) 97-100. Dahl G., Gouveia L. “On the directed hop-constrained shortest path problem”, Operations Research Letters 32 (2004) 15-22. Dahl G., Gouveia L., Requejo C. “On formulations and methods for the hop-constrained minimum spanning tree problem”, In: Handbook of Optimization in Telecommunications, ed. M.G.C. Resende and P.M. Pardalos, Springer Science + Business Media, 2006. Dahl G., Martin A., Stoer M. “Routing through virtual paths in layered telecommunication networks”, Operations Research 47 (1999) 693-702. 15 Desrochers M., Laporte G. “Improvements and extensions to the Miller-TuckerZemlin subtour elimination constraints”, Operations Research Letters 10 (1991) 27-36. Even S., Itai A., Shamir A. “On the complexity of timetable and multicommodity flow problems”, SIAM Journal of Computing 5 (1976) 184-183. Frangioni A., Gendron B. “0-1 reformulations of the multicommodity capacitated network design problem”, Discrete Applied Mathematics, 157 (2009) 1229-1241. Gavish B., Altinkemer K. “Backbone network design tools with economic tradeoffs”, ORSA Journal on Computing 2 (1990) 58-76. Gouveia L. “Using the Miller-Tucker-Zemlin constraints to formulate a minimal spanning tree problem with hop constraints”, Computers and Operations Research 22 (1995) 959-970. Gouveia L. “Multicommodity flow models for spanning trees with hop constraints”, European Journal of Operational Research 95 (1996) 178-190. Gouveia L. “Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints”, INFORMS Journal on Computing 10 (1998) 180-188. Gouveia L., Patr´ıcio P.F., De Sousa A.F. “Compact models for hop-constrained node survivable network design”, In: Telecommunications Network Planning: Innovations in Pricing, Network Design and Management, ed. G. Anandaligam and S. Raghavan, Springer, (2006) 167-180. Gouveia L., Patr´ıcio P.F., De Sousa A.F. “Hop-constrained node survivable network design: an application to MPLS over WDM”, Networks and Spatial Economics 8 (2008) 3-21. Gouveia L., Simonetti L., Uchoa E. “Modeling hop-constrained and diameter-constrained minimum spanning tree problems as Steiner tree problems over layered graphs”, Mathematical Programming 128 (2011) 123-148. Gouveia L., Requejo C. “A new Lagrangean relaxation approach for the hop-constrained minimum spanning tree problem”, European Journal of Operational Research 132 (2001) 539-552. Krarup J., Pruzan P.M. “The simple plant location problem: sis”, European Journal of Operational Research 12 (1983) 36-81. survey and synthe- Magnanti T.L., Wong R.T. “Network Design and Transportation Planning: Models and Algorithms”, Transportation Science 18 (1980) 1-55. Nemhauser G.L., Wolsey L.A. Integer and Combinatorial Optimization, Wiley (1999). Orlowsky S., Wess¨aly R. “The effect of hop limits on optimal cost in survivable network design”, In: Telecommunications Network Planning: Innovations in Pricing, Network Design and Management, ed. G. Anandaligam and S. Raghavan, Springer (2006) 167-180. Plateau G., Elkihel M. “A hybrid method for the 0-1 knapsack problem”, Methods of Operations Research 49 (1985) 277-293. 16 Voß S. “The Steiner tree problem with hop constraints”, Annals of Operations Research 86 (1999) 321-345. 17

© Copyright 2018 ExploreDoc