×

Thinning out Steiner trees: a node-based model for uniform edge costs. (English) Zbl 1387.90132

Summary: The Steiner tree problem is a challenging NP-hard problem. Many hard instances of this problem are publicly available, that are still unsolved by state-of-the-art branch-and-cut codes. A typical strategy to attack these instances is to enrich the polyhedral description of the problem, and/or to implement more and more sophisticated separation procedures and branching strategies. In this paper we investigate the opposite viewpoint, and try to make the solution method as simple as possible while working on the modeling side. Our working hypothesis is that the extreme hardness of some classes of instances mainly comes from over-modeling, and that some instances can become quite easy to solve when a simpler model is considered. In other words, we aim at “thinning out” the usual models for the sake of getting a more agile framework. In particular, we focus on a model that only involves node variables, which is rather appealing for the “uniform” cases where all edges have the same cost. In our computational study, we first show that this new model allows one to quickly produce very good (sometimes proven optimal) solutions for notoriously hard instances from the literature. In some cases, our approach takes just few seconds to prove optimality for instances never solved (even after days of computation) by the standard methods. Moreover, we report improved solutions for several SteinLib instances, including the (in)famous hypercube ones. We also demonstrate how to build a unified solver on top of the new node-based model and the previous state-of-the-art model (defined in the space of arc and node variables). The solver relies on local branching, initialization heuristics, preprocessing and local search procedures. A filtering mechanism is applied to automatically select the best algorithmic ingredients for each instance individually. The presented solver is the winner of the DIMACS Challenge on Steiner trees in most of the considered categories.

MSC:

90C10 Integer programming
90C27 Combinatorial optimization

Software:

OGDF; DIMACS; SteinLib
PDF BibTeX XML Cite
Full Text: DOI

References:

[1] 11th DIMACS Implementation Challenge in Collaboration with ICERM: Steiner tree problems (2014). http://dimacs11.zib.de/home.html. Accessed 20 Sept 2016 · Zbl 1085.90061
[2] Álvarez-Miranda, E., Ljubić, I., Mutzel, P.: The maximum weight connected subgraph problem. In: Facets of Combinatorial Optimization: Festschrift for Martin Grötschel, pp. 245-270. Springer, Berlin (2013) · Zbl 1317.90299
[3] Andreello, G; Caprara, A; Fischetti, M, Embedding \(\{\)0, 1/2\(\}\)-cuts in a branch-and-cut framework: a computational study, INFORMS J. Comput., 19, 229-238, (2007) · Zbl 1241.90181
[4] Aragão, MP; Werneck, RFF; Mount, DM (ed.); Stein, C (ed.), On the implementation of MST-based heuristics for the Steiner problem in graphs, No. 2409, 1-15, (2002), London · Zbl 1014.68771
[5] Backes, C; Rurainski, A; Klau, GW; Müller, O; Stöckel, D; Gerasch, A; Küntzer, J; Maisel, D; Ludwig, N; Hein, M; Keller, A; Burtscher, H; Kaufmann, M; Meese, E; Lenhof, HP, An integer linear programming approach for finding deregulated subgraphs in regulatory networks, Nucleic Acids Res., 40, 1-13, (2012)
[6] Caprara, A; Fischetti, M, \(\{\)0, 1/2\(\}\)-chvátal-Gomory cuts, Math. Program., 74, 221-235, (1996) · Zbl 0855.90088
[7] Caprara, A., Fischetti, M., Toth, P.: A heuristic algorithm for the set covering problem. In: Integer Programming and Combinatorial Optimization, pp. 72-84. Springer, Berlin Heidelberg (1996) · Zbl 1415.90097
[8] Caprara, A; Fischetti, M; Toth, P, A heuristic method for the set covering problem, Oper. Res., 47, 730-743, (1999) · Zbl 0976.90086
[9] Cherkassky, B.V., Goldberg, A.V.: On implementing push-relabel method for the maximum flow problem. Algorithmica. 19, 390-410 (1997) · Zbl 0898.68029
[10] Chimani, M., Gutwenger, C., Jünger, M., Klau, G.W., Klein, K., Mutzel, P.: The open graph drawing framework (OGDF). In: Tamassia, R. (ed.) Handbook of Graph Drawing and Visualization, Chapter 17. CRC Press, Boca Raton (2014) · Zbl 1056.90119
[11] Best bounds as of August 1, 2014 for SteinLib instances (2014). http://dimacs11.zib.de/instances/bounds20140801.txt. Accessed 20 Sept 2016
[12] Results of the 11th DIMACS Competition on Steiner Tree Problems (2015). http://dimacs11.zib.de/contest/results/results.html. Accessed 20 Sept 2016 · Zbl 0976.90086
[13] Duin, C.: Preprocessing the Steiner problem in graphs. In: Du, D.Z., Smith, J., Rubinstein, J. (eds.) Advances in Steiner Trees, Combinatorial Optimization, vol. 6, pp. 175-233. Springer, US (2000) · Zbl 0945.90029
[14] Eisenstat, D.: dtree: dynamic trees à la carte (2014). http://www.davideisenstat.com/dtree/. Accessed 20 Sept 2016 · Zbl 1060.90056
[15] Fischetti, M; Lodi, A, Local branching, Math. Progr., 98, 23-47, (2003) · Zbl 1060.90056
[16] Fischetti, M; Monaci, M, Cutting plane versus compact formulations for uncertain (integer) linear programs, Math. Progr. Comput., 4, 239-273, (2012) · Zbl 1275.90046
[17] Fischetti, M; Monaci, M, Proximity search for 0-1 mixed-integer convex programming, J. Heuristics, 20, 709-731, (2014) · Zbl 1360.90173
[18] Golumbic, M.C.: Algorithmic Graph Theory and Perfect Graphs (Annals of Discrete Mathematics), vol. 57. North-Holland Publishing Co., Amsterdam (2004) · Zbl 1050.05002
[19] Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32(3), 207-232 (1998) · Zbl 1002.90078
[20] Koch, T., Martin, A., Voß, S.: SteinLib: an updated library on Steiner tree problems in graphs. Tech. Rep. ZIB-Report 00-37, Konrad-Zuse-Zentrum für Informationstechnik Berlin, Takustr. 7, Berlin (2000). http://elib.zib.de/steinlib · Zbl 1085.90061
[21] Leitner, M., Ljubić, I., Luipersbeck, M., Resch, M.: A partition-based heuristic for the Steiner tree problem in large graphs. In: Blesa, M.J., Blum, C., Voß, S. (eds.) Hybrid Metaheuristics—Proceedings. Lecture Notes in Computer Science, vol. 8457, pp. 56-70. Springer, UK (2014) · Zbl 0976.90086
[22] Ljubić, I; Weiskircher, R; Pferschy, U; Klau, GW; Mutzel, P; Fischetti, M, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Math. Program., 105, 427-449, (2006) · Zbl 1085.90061
[23] Lucena, A; Resende, MG, Strong lower bounds for the prize collecting Steiner problem in graphs, Discrete Appl. Math., 141, 277-294, (2004) · Zbl 1056.90119
[24] OGDF: The Open Graph Drawing Framework (2015). http://www.ogdf.net/. Accessed 20 Sept 2016
[25] Uchoa, E., Werneck, R.F.: Fast local search for Steiner trees in graphs. In: Blelloch, G.E., Halperin, D. (eds.) ALENEX’10 Proceedings of the Meeting on Algorithm Engineering & Expermiments, pp. 1-10. SIAM (2010) · Zbl 1241.90181
[26] Wang, Y., Buchanan, A., Butenko, S.: On imposing connectivity constraints in integer programs (2015). Submitted. Available at http://www.optimization-online.org/DB_HTML/2015/02/4768.html · Zbl 1386.90023
[27] Wong, RT, A dual ascent approach for Steiner tree problems on a directed graph, Math. Program., 28, 271-287, (1984) · Zbl 0532.90092
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.