Solving minimum-cost shared arborescence problems. (English) Zbl 1394.90429

Summary: In this work, we consider the minimum-cost shared Steiner arborescence problem (SStA). In this problem, the goal is to find a minimum-cost subgraph, which is shared among multiple entities and each entity is able to establish a cost-efficient Steiner arborescence. The SStA has been recently used in the literature to establish shared functional modules in protein-protein interaction networks. We propose a cut-based formulation for the problem, and design two exact algorithmic approaches: one based on the separation of connectivity cut inequalities, and the other corresponding to a Benders decomposition of the former model. Both approaches are enhanced by various techniques, including (i) preprocessing, (ii) stabilized cut generation, (iii) primal heuristics, and (iv) cut management. These two algorithmic alternatives are computationally evaluated and compared with a previously proposed flow-based formulation. We illustrate the effectiveness of the algorithms on two types of instances derived from protein-protein interaction networks (available from the previous literature) and from telecommunication access networks.


90C10 Integer programming
90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut


SteinLib; OGDF
Full Text: DOI


[1] Álvarez-Miranda, E.; Ljubić, I.; Fernández, E., The recoverable robust facility location problem, Transportation Research Part B, 79, 93-120, (2015)
[2] Backes, C.; Rurainski, A.; Klau, G.; Müller, O.; Stöckel, D.; Gerasch, A.; Lenhof, H., An integer linear programming approach for finding deregulated subgraphs in regulatory networks, Nucleic Acids Research, 1, 1-13, (2011)
[3] Battiti, R.; Cigno, R. L.; Orava, F.; Pehrson, B., Global growth of open access networks: from war chalking and connection sharing to sustainable business, Proceedings of the 1st ACM international workshop on wireless mobile applications and services on WLAN hotspots, WMASH, 19-28, (2003)
[4] Ben-Ameur, W.; Neto, J., Acceleration of cutting-plane and column generation algorithms: applications to network design, Networks, 49, 1, 3-17, (2007) · Zbl 1131.90047
[5] Bomze, I.; Chimani, M.; Jünger, M.; Ljubić, I.; Mutzel, P.; Zey, B., Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut, (Cheong, O.; Chwa, K.; Park, K., Proceedings of ISAAC 2010, LNCS, vol. 6506, (2010), Springer), 427-439 · Zbl 1311.90085
[6] Cherkassky, B.; Goldberg, A., On implementing push-relabel method for the maximum flow problem, (Balas, E.; Clausen, J., Proceedings of IPCO IV, LNCS, vol. 920, (1995), Springer), 157-171
[7] Chimani, M.; Gutwenger, C.; Jünger, M.; Klau, G.; Klein, K.; Mutzel, P., The open graph drawing framework (OGDF), Handbook of graph drawing and visualization, 543-569, (2011)
[8] Costa, A., A survey on benders decomposition applied to fixed-charge network design problems, Computers & Operations Research, 32, 6, 1429-1450, (2005) · Zbl 1071.90009
[9] 11th DIMACS Challenge: Steiner tree problems. http://dimacs11.zib.de/. Last accessed: 15 November 2016.
[10] Dittrich, M.; Klau, G.; Rosenwald, A.; Dandekar, T.; Muller, T., Identifying functional modules in protein-protein interaction networks: an integrated exact approach, Bioinformatics, 24, 13, i223-i231, (2008)
[11] Duin, C., Steiner problem in graphs, (1993), University of Amsterdam, (Ph.D. thesis)
[12] Duin, C.; Volgenant, A., Reduction tests for the Steiner problem in graphs, Networks, 19, 5, 549-567, (1989) · Zbl 0673.05088
[13] Fischetti, M.; Leitner, M.; Ljubić, I.; Luipersbeck, M.; Monaci, M.; Resch, M.; Savagnin, D.; Sinnl, M., Thinning out Steiner trees: a node-based model for uniform edge costs, Mathematical Programming Computation, (2016), . http://dx.doi.org/10.1007/s12532-016-0111-0
[14] Fischetti, M.; Ljubić, I.; Sinnl, M., Redesigning benders decomposition for large scale facility location, Management Science, (2016)
[15] Fischetti, M.; Ljubić, I.; Sinnl, M., Benders decomposition without separability: A computational study for capacitated facility location problems, European Journal of Operational Research, 253, 3, 557-569, (2016) · Zbl 1346.90490
[16] Fischetti, M.; Salvagnin, D., An in-out approach to disjunctive optimization, (Lodi, A.; Milano, M.; Toth, P., Integration of AI and OR techniques in constraint programming for combinatorial optimization problems, Lecture Notes in Computer Science, vol. 6140, (2010), Springer Berlin, Heidelberg), 136-140 · Zbl 1285.90018
[17] Forzati, M.; Larsen, C.; Mattsson, C., Open access networks, the swedish experience, Proceedings of the 12th IEEE international conference on transparent optical networks, 1-4, (2010)
[18] Kepaptsoglou, K.; Karlaftis, M., Transit route network design problem: review, Journal of Transportation Engineering, 135, 8, 491-505, (2009)
[19] Koch, T.; Martin, A., Solving Steiner tree problems in graphs to optimality, Networks, 32, 3, 207-232, (1998) · Zbl 1002.90078
[20] Laporte, G.; Louveaux, F., The integer l-shaped method for stochastic integer programs with complete recourse, Operations Research Letters, 13, 3, 133-142, (1993) · Zbl 0793.90043
[21] Leitner, M.; Ljubić, I.; Luipersbeck, M.; Prossegger, M.; Resch, M., New real-world instances for the Steiner tree problem in graphs, Technical report, Technical report, ISOR, (2014), University of Vienna
[22] Ljubić, I.; Mutzel, P.; Zey, B., Stochastic survivable network design problems, Electronic Notes in Discrete Mathematics, 41, 245-252, (2013)
[23] Ljubić, I.; Weiskircher, R.; Pferschy, U.; Klau, G.; Mutzel, P.; Fischetti, M., An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Mathematical Programming, Series B, 105, 427-449, (2006) · Zbl 1085.90061
[24] Magnanti, T.; Mireault, P.; Wong, R., Tailoring benders decomposition for uncapacitated network design, Mathematical Programming Study, 26, 112-154, (1986) · Zbl 0596.90098
[25] Mazza, A.; Gat-Viks, I.; Farhan, H.; Sharan, R., A minimum-labeling approach for reconstructing protein networks across multiple conditions, Algorithms for Molecular Biology, 9, 1, 1-8, (2014)
[26] McDaniel, D.; Devine, M., A modified benders’ partitioning algorithm for mixed integer programming, Management Science, 24, 3, 312-319, (1977) · Zbl 0371.90102
[27] Poggi de Aragão, M.; Uchoa, E.; Werneck, R., Dual heuristics on the exact solution of large Steiner problems, Electronic Notes in Discrete Mathematics, 7, 150-153, (2001) · Zbl 0983.68010
[28] Poggi de Aragão, M.; Werneck, R., On the implementation of MST-based heuristics for the Steiner problem in graphs, (Mount, D.; Stein, C., Proceedings of ALENEX 2002, LNCS, vol. 2409, (2002), Springer), 1-15 · Zbl 1014.68771
[29] Polzin, T.; Daneshmand, S., Improved algorithms for the Steiner problem in networks, Discrete Applied Mathematics, 112, 1, 263-300, (2001) · Zbl 0994.90135
[30] Quilliot, A., Network design problems: fundamental methods, (Paschos, V., Applications of combinatorial optimization, (2013), John Wiley & Sons), 253-289 · Zbl 1206.90018
[31] Takahashi, H.; Matsuyama, A., An approximate solution for the Steiner problem in graphs, Mathematica Japonica, 24, 6, 573-577, (1980) · Zbl 0435.05036
[32] Wong, R., A dual ascent approach for Steiner tree problems on a directed graph, Mathematical Programming, 28, 3, 271-287, (1984) · Zbl 0532.90092
[33] Yamamoto, T.; Bannai, H.; Nagasaki, M.; Miyano, S., Better decomposition heuristics for the maximum-weight connected graph problem using betweenness centrality, (Gama, J.; Costa, V.; Jorge, A.; Brazdil, P., Discovery science, LNCS, vol. 5808, (2009), Springer), 465-472
[34] Yosef, N.; Zalckvar, E.; Rubinstein, A.; Homilius, M.; Atias, N.; Vardi, L.; Sharan, R., ANAT: A tool for constructing and analyzing functional protein networks, Science Signaling, 4, 196, pl1, (2011)
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.