A comparison of node-based and arc-based hop-indexed formulations for the Steiner tree problem with hop constraints. (English) Zbl 1535.90174
Summary: We study the relation between the linear programming relaxation of two classes of models for the Steiner tree problem with hop constraints. One class is characterized by having hop-indexed arc variables. Although such models have proved to have a very strong linear programming bound, they are not easy to use because of the huge number of variables. This has motivated some studies with models involving fewer variables that use, instead of the hop-indexed arc variables, hop-indexed node variables. In this article, we contextualize the linear programming relaxation of these node-based models in terms of the linear programming relaxation of known arc-based models. We show that the linear programming relaxation of a general node-based model is implied by the linear programming relaxation of a straightforward arc-based model.
{© 2021 Wiley Periodicals LLC.}
{© 2021 Wiley Periodicals LLC.}
Keywords:
hop constraint; hop-indexed model; integer programming; linear programming relaxation; network design; Steiner treeReferences:
| [1] | Q.Botton, B.Fortz, and L.Gouveia, On the hop‐constrained survivable network design problem with reliable edges, Comput. Oper. Res.64 (2015), 159-167. · Zbl 1349.90158 |
| [2] | Q.Botton, B.Fortz, L.Gouveia, and M.Poss, Benders decomposition for the hop‐constrained survivable network design problem, INFORMS J. Comput.25 (2013), 13-26. |
| [3] | A. M.Costa, J.‐F.Cordeau, and G.Laporte, Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints, Networks53 (2009), 141-159. · Zbl 1180.90348 |
| [4] | G.Dahl, L.Gouveia, and C.Requejo, “On formulations and methods for the hop‐constrained minimum spanning tree problem,” Handbook of optimization in telecommunications, M.Resende (ed.) and P.Pardalos (ed.) (eds.), Springer, New York, NY, 2006, pp. 493-515. · Zbl 1118.90051 |
| [5] | J.De Boeck and B.Fortz, Extended formulation for hop constrained distribution network configuration problems, Eur. J. Oper. Res.265 (2018), 488-502. · Zbl 1374.90082 |
| [6] | L.Gouveia, Multicommodity flow models for spanning trees with hop constraints, Eur. J. Oper. Res.95 (1996), 178-190. · Zbl 0947.90513 |
| [7] | L.Gouveia, Using variable redefinition for computing lower bounds for minimum spanning and Steiner trees with hop constraints, INFORMS J. Comput.10 (1998), 180-188. · Zbl 1054.90622 |
| [8] | L.Gouveia, “Using hop‐indexed models for constrained spanning and Steiner tree models,” Telecommunications network planning, B.Sansò (ed.) and P.Soriano (ed.) (eds.), Springer, New York, NY, 1999, pp. 21-32. |
| [9] | L.Gouveia, M.Leitner, and I.Ljubić, Hop constrained Steiner trees with multiple root nodes, Eur. J. Oper. Res.236 (2014), 100-112. · Zbl 1338.90266 |
| [10] | L.Gouveia, M.Leitner, and M.Ruthmair, Layered graph approaches for combinatorial optimization problems, Comput. Oper. Res.102 (2019), 22-38. · Zbl 1458.90612 |
| [11] | L.Gouveia, L.Simonetti, and E.Uchoa, Modeling hop‐constrained and diameter‐constrained minimum spanning tree problems as Steiner tree problems over layered graphs, Math. Program.128 (2011), 123-148. · Zbl 1218.90201 |
| [12] | M.Leitner, Layered graph models and exact algorithms for the generalized hop‐constrained minimum spanning tree problem, Comput. Oper. Res.65 (2016), 1-18. · Zbl 1349.90636 |
| [13] | I.Ljubić and S.Gollowitzer, Layered graph approaches to the hop constrained connected facility location problem, INFORMS J. Comput.25 (2013), 256-270. |
| [14] | A. R.Mahjoub, L.Simonetti, and E.Uchoa, Hop‐level flow formulation for the survivable network design with hop constraints problem, Networks61 (2013), 171-179. · Zbl 1269.90023 |
| [15] | M.Sinnl and I.Ljubić, A node‐based layered graph approach for the Steiner tree problem with revenues, budget and hop‐constraints, Math. Program. Comput.8 (2016), 461-490. · Zbl 1391.90421 |
| [16] | S.Voß, The Steiner tree problem with hop constraints, Ann. Oper. Res.86 (1999), 321-345. · Zbl 0921.90072 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
