SCIP-Jack: An Exact High Performance Solver for Steiner Tree Problems in Graphs and Related Problems

1. Karp, R.: Reducibility among combinatorial problems. In: Miller, R., Thatcher, J. (eds.) Complexity of Computer Computations, pp. 85–103. Plenum Press, Berlin (1972)

   Google Scholar 

2. Leitner, M., Ljubic, I., Luipersbeck, M., Prossegger, M., Resch, M.: New Real-world Instances for the Steiner Tree Problem in Graphs. Technical report, ISOR, Uni Wien (2014)

   Google Scholar 

3. Koch, T., Martin, A., Voß, S.: SteinLib: An updated library on Steiner tree problems in graphs. In: Du, D.Z., Cheng, X. (eds.) Steiner Trees in Industries, pp. 285–325. Kluwer, Dordrech (2001)

   Google Scholar 

4. Fischetti, M., Leitner, M., Ljubić, I., Luipersbeck, M., Monaci, M., Resch, M., Salvagnin, D., Sinnl, M.: Thinning out Steiner trees: A node-based model for uniform edge costs. Math. Program. Comput. 9(2), 203–229 (2017)

   Article  MathSciNet  Google Scholar 

5. Pajor, T., Uchoa, E., Werneck, R.F.: A robust and scalable algorithm for the Steiner problem in graphs. Math. Program. Comput. 10(1), 69–118 (2018)

   Article  MathSciNet  Google Scholar 

6. Gamrath, G., Koch, T., Maher, S., Rehfeldt, D., Shinano, Y.: SCIP-Jack–a solver for STP and variants with parallelization extensions. Math. Program. Comput. 9(2), 231–296 (2017)

   Article  MathSciNet  Google Scholar 

7. : PACE 2018. https://pacechallenge.wordpress.com/pace-2018 (2018)

8. Gleixner, A., Bastubbe, M., Eifler, L., Gally, T., Gamrath, G., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Lübbecke, M.E., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Schubert, C., Serrano, F., Shinano, Y., Viernickel, J.M., Walter, M., Wegscheider, F., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 6.0. Technical Report 18–26, ZIB, Takustr. 7, 14195, Berlin (2018)

   Google Scholar 

9. Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007)

   Google Scholar 

10. Rosseti, I., de Aragão, M., Ribeiro, C., Uchoa, E., Werneck, R.: New benchmark instances for the Steiner problem in graphs. In: Extended Abstracts of the 4th Metaheuristics International Conference (MIC’2001), Porto, pp. 557–561 (2001)

    Google Scholar 

11. Duin, C.: Steiner Problems in Graphs. Ph.D. thesis, University of Amsterdam (1993)

    Google Scholar 

12. Polzin, T., Daneshmand, S.V.: Improved algorithms for the Steiner problem in networks. Discrete Appl. Math. 112(1–3), 263–300 (2001)

    Article  MathSciNet  Google Scholar 

13. Daneshmand, S.V.: Algorithmic approaches to the Steiner problem in networks (2004)

    Google Scholar 

14. Rehfeldt, D., Koch, T.: Combining NP-hard reduction techniques and strong heuristics in an exact algorithm for the maximum-weight connected subgraph problem. SIAM J. Optim. 29(1), 369–398 (2019)

    Google Scholar 

15. Polzin, T., Vahdati Daneshmand, S.: A comparison of Steiner tree relaxations. Discrete Appl. Math. 112(1–3), 241–261 (2001)

    Article  MathSciNet  Google Scholar 

16. Wong, R.: A dual ascent approach for Steiner tree problems on a directed graph. Math. Program. 28, 271–287 (1984)

    Article  MathSciNet  Google Scholar 

17. Koch, T., Martin, A.: Solving Steiner tree problems in graphs to optimality. Networks 32, 207–232 (1998)

    Article  MathSciNet  Google Scholar 

18. Polzin, T., Vahdati-Daneshmand, S.: The Steiner Tree Challenge: An updated Study. http://dimacs11.zib.de/downloads.html (2014)

19. Polzin, T., Daneshmand, S.V.: Extending Reduction Techniques for the Steiner Tree Problem, pp. 795–807. Springer, Berlin, Heidelberg (2002)

    MATH  Google Scholar 

20. Dittrich, M.T., Klau, G.W., Rosenwald, A., Dandekar, T., Müller, T.: Identifying functional modules in protein-protein interaction networks: an integrated exact approach. In: ISMB, pp. 223–231 (2008)

    Google Scholar 

21. Loboda, A.A., Artyomov, M.N., Sergushichev, A.A.: Solving Generalized Maximum-Weight Connected Subgraph Problem for Network Enrichment Analysis, pp. 210–221. Springer International Publishing, Cham (2016)

    MATH  Google Scholar 

22. Dilkina, B., Gomes, C.P.: Solving connected subgraph problems in wildlife conservation. In: Proceedings of the 7th International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems, CPAIOR’10, pp. 102–116. Springer, Berlin, Heidelberg (2010)

    Google Scholar 

23. Chen, C., Grauman, K.: Efficient activity detection with max-subgraph search. In: 2012 IEEE Conference on Computer Vision and Pattern Recognition, Providence, RI, USA, June 16–21, 2012, pp. 1274–1281 (2012)

    Google Scholar 

24. Rehfeldt, D., Koch, T.: Transformations for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to SAP. J. Comput. Math. 36(3), 459–468 (2018)

    Article  MathSciNet  Google Scholar 

25. Álvarez-Miranda, E., Ljubić, I., Mutzel, P.: The Rooted Maximum Node-Weight Connected Subgraph Problem, pp. 300–315. Springer, Berlin, Heidelberg (2013)

    MATH  Google Scholar 

26. Rehfeldt, D., Koch, T., Maher, S.: Reduction techniques for the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem. Networks 73, 206–233 (2019)

    Article  MathSciNet  Google Scholar 

27. 11th DIMACS Challenge.: http://dimacs11.zib.de/ (2018)

28. Leitner, M., Ljubi, I., Luipersbeck, M., Sinnl, M.: A dual ascent-based branch-and-bound framework for the prize-collecting Steiner tree and related problems. INFORMS J. Comput. 30(2), 402–420 (2018)

    Google Scholar 

29. Burdakov, O., Doherty, P., Kvarnström, J.: Local search for hop-constrained directed Steiner tree problem with application to uav-based multi-target surveillance. In: Examining Robustness and Vulnerability of Networked Systems,pp. 26–50 (2014)

    Google Scholar 

30. Pugliese, L.D.P., Gaudioso, M., Guerriero, F., Miglionico, G.: A lagrangean-based decomposition approach for the link constrained Steiner tree problem. Optim. Meth. Softw. 33(3), 650–670 (2018)

    Article  MathSciNet  Google Scholar 

31. Gamrath, G., Fischer, T., Gally, T., Gleixner, A.M., Hendel, G., Koch, T., Maher, S.J., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Vigerske, S., Weninger, D., Winkler, M., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 3.2. Technical Report 15–60, ZIB, Takustr.7, 14195, Berlin (2016)

    Google Scholar 

32. Canuto, S.A., Resende, M.G.C., Ribeiro, C.C.: Local search with perturbations for the prize-collecting Steiner tree problem in graphs. Networks (2001)

    Google Scholar 

33. Bienstock, D., Goemans, M.X., Simchi-Levi, D., Williamson, D.P.: A note on the prize collecting traveling salesman problem. Math. Program. 59, 413–420 (1993)

    Article  MathSciNet  Google Scholar 

34. Johnson, D.S., Minkoff, M., Phillips, S.: The prize collecting steiner tree problem: theory and practice. In: Proceedings of the Eleventh Annual ACM-SIAM Symposium on Discrete Algorithms. SODA ’00, Philadelphia, PA, USA, Society for Industrial and Applied Mathematics, pp. 760–769 (2000)

    Google Scholar 

35. Ljubi, I.: Exact and Memetic Algorithms for Two Network Design Problems. Ph.D. thesis, Vienna University of Technology (2004)

    Google Scholar 

36. El-Kebir, M., Klau, G.W.: Solving the Maximum-Weight Connected Subgraph Problem to Optimality. Comput. Res. Repos. abs/1409.5308 (2014)

    Google Scholar 

37. Ljubic, I., Weiskircher, R., Pferschy, U., Klau, G.W., Mutzel, P., Fischetti, M.: An algorithmic framework for the exact solution of the prize-collecting steiner tree problem. Math. Program. 105(2–3), 427–449 (2006)

    Article  MathSciNet  Google Scholar 

38. Lucena, A., Resende, M.G.C.: Strong lower bounds for the prize collecting Steiner problem in graphs. Discrete Appl. Math. 141(1–3), 277–294 (2004)

    Article  MathSciNet  Google Scholar 

39. Ideker, T., Ozier, O., Schwikowski, B., Siegel, A.F.: Discovering regulatory and signalling circuits in molecular interaction networks. In: ISMB, pp. 233–240 (2002)

    Google Scholar 

40. Rehfeldt, D., Koch, T.: Reduction-based exact solution of prize-collecting Steiner tree problems. Technical Report 18–55, ZIB, Takustr. 7, 14195, Berlin (2018)

    Google Scholar 

41. Hwang, F., Richards, D., Winter, P.: The Steiner Tree Problem. Annals of Discrete Mathematics. Elsevier Science, Amsterdam (1992)

    Google Scholar 

42. Vo, S.: A survey on some generalizations of Steiner’s problem. In: 1st Balkan Conference on Operational Research Proceedings, 1, pp. 41–51 (1988)

    Google Scholar 

43. Ferreira, C.E., de Oliveira Filho, F.M.: New reduction techniques for the group Steiner tree problem. SIAM J. Optim. 17(4), 1176–1188 (2006)

    Article  MathSciNet  Google Scholar 

44. Garey, M., Johnson, D.: The rectilinear Steiner tree problem is NP-complete. SIAM J. Appl. Math. 32, 826–834 (1977)

    Article  MathSciNet  Google Scholar 

45. Warme, D., Winter, P., Zachariasen, M.: Exact algorithms for plane Steiner tree problems: A computational study. In: Du, D.Z., Smith, J., Rubinstein, J., (eds.) Advances in Steiner Trees. Kluwer, New York, pp. 81–116 (2000)

    Google Scholar 

46. Zachariasen, M., Rohe, A.: Rectilinear group Steiner trees and applications in VLSI design. Technical Report 00906, Institute for Discrete Mathematics (2000)

    Google Scholar 

47. Emanet, N.: The Rectilinear Steiner Tree Problem. Lambert Academic Publishing (2010)

    Google Scholar 

48. Hanan, M.: On Steiner’s problem with rectilinear distance. SIAM J. Appl. Math. 14(2), 255–265 (1966)

    Article  MathSciNet  Google Scholar 

49. Snyder, T.L.: On the exact location of Steiner points in general dimension. SIAM J. Appl. Math. 21(1), 163–180 (1992)

    MathSciNet  MATH  Google Scholar 

50. Chowdhury, S.A., Shackney, S., Heselmeyer-Haddad, K., Ried, T., Schffer, A.A., Schwartz, R.: Phylogenetic analysis of multiprobe fluorescence in situ hybridization data from tumor cell populations. Bioinformatics 29(13), 189–198 (2013)

    Article  Google Scholar 

51. Liers, F., Martin, A., Pape, S.: Binary Steiner trees. Discrete Optim. 21(C), 85–117 (2016)

    Google Scholar 

52. Shinano, Y., Achterberg, T., Berthold, T., Heinz, S., Koch, T., Winkler, M.: Solving Open MIP Instances with ParaSCIP on Supercomputers Using up to 80,000 Cores. In: 2016 IEEE International Parallel and Distributed Processing Symposium (IPDPS), pp. 770–779 (2016)

    Google Scholar 

53. Rehfeldt, D., Koch, T.: Generalized preprocessing techniques for Steiner tree and maximum-weight connected subgraph problems. Technical Report 17–57, ZIB, Takustr. 7, 14195, Berlin (2017)

    Google Scholar 

Download references