Help
Cart
Skip main navigation

Available Issues

April 12, 2013 - April 13, 2026

Available Issues

April 12, 2013 - April 13, 2026

A Computational Study of Exact Approaches for the Bi-Objective Prize-Collecting Steiner Tree Problem

Published Online:23 Dec 2014https://doi.org/10.1287/ijoc.2014.0614

References

  • Álvarez ME, Ljubić I, Toth P (2013) Exact approaches for solving robust prize-collecting Steiner tree problems. Eur. J. Oper. Res. 229:599–612.Crossref, Google Scholar
  • Aneja YP, Nair KPK (1979) Bicriteria transportation problem. Management Sci. 25:73–78.Link, Google Scholar
  • Archer A, Bateni MH, Hajiaghayi MT, Karloff HJ (2011) Improved approximation algorithms for prize-collecting Steiner tree and TSP. SIAM J. Comput. 40:309–332.Crossref, Google Scholar
  • Balas E, Zemel E (1978) Facets of the knapsack polytope from minimal covers. SIAM J. Appl. Math. 34:119–148.Crossref, Google Scholar
  • Bérubé JF, Gendreau M, Potvin JY (2009) An exact ε-constraint method for bi-objective combinatorial optimization problems: Application to the traveling salesman problem with profits. Eur. J. Oper. Res. 194:39–50.Crossref, Google Scholar
  • Bienstock D, Goemans MX, Simchi-Levi D, Williamson DP (1993) A note on the prize collecting traveling salesman problem. Math. Programming 59:413–420.Crossref, Google Scholar
  • Boland N, Charkhgard H, Savelsbergh M (2013) Criterion space search for algorithms for biobjective mixed integer programming–Part I: Integer programs. Accessed September 22, 2014, http://www.optimization-online.org/DB_FILE/2013/08/3987.pdf.Google Scholar
  • Bozkurt B, Fowler JW, Gel ES, Kim B, Köksalan M, Wallenius J (2010) Quantitative comparison of approximate solution sets for multicriteria optimization problems with weighted Tchebycheff preference function. Oper. Res. 58:650–659.Link, Google Scholar
  • Cherkassky BV, Goldberg AV (1997) On implementing the push-relabel method for the maximum flow problem. Algorithmica 19:390–410.Crossref, Google Scholar
  • Cohon JL (1978) Multiobjective Programming and Planning (Academic Press, New York).Google Scholar
  • da Cunha AS, Lucena A, Maculan N, Resenden MGC (2009) A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs. Discrete Appl. Math. 157:1198–1217.Crossref, Google Scholar
  • Dilkina B, Gomes C (2010) Solving connected subgraph problems in wildlife conservation. CPAIOR 2010, Lecture Notes in Computer Science, Vol. 6140 (Springer, Berlin), 102–116.Crossref, Google Scholar
  • Ehrgott M, Tenfelde-Podehl D (2003) Computation of ideal and nadir values and implications for their use in MCDM methods. Eur. J. Oper. Res. 151:119–139.Crossref, Google Scholar
  • Ehrgott M, Wiecek MM (2005) Mutiobjective Programming. Hillier FS, ed. Multiple Criteria Decision Analysis: State of the Art Surveys, International Series in Operations Research and Management Science, Vol. 78 (Springer, New York),667–708.Crossref, Google Scholar
  • Eswaran PK, Ravindran A, Moskowitz H (1989) Algorithms for nonlinear integer bicriterion problems. J. Optim. Theory Appl. 63:261–279.Crossref, Google Scholar
  • Feofiloff P, Fernandes CG, Ferreira CE, de Pina JC (2007) Primal-dual approximation algorithms for the prize-collecting Steiner tree problem. Inf. Process. Lett. 103:195–202.Crossref, Google Scholar
  • Fischetti M (1991) Facets of two Steiner arborescence polyhedra. Math. Programming 51:401–419.Crossref, Google Scholar
  • Goemans MX, Williamson DP (1997) The primal-dual method for approximation algorithms and its application to network design problems. Hochbaum DS, ed. Approximation Algorithms for NP-Hard Problems (PWS Publishing, Boston), 144–191.Google Scholar
  • Gollowitzer S, Gendron B, Ljubić I (2013) A cutting plane algorithm for the capacitated connected facility location problem. Comp. Opt. Appl., 55:647–674.Crossref, Google Scholar
  • Hamacher HW, Ruhe G (1994) On spanning tree problems with multiple objectives. Amer. Oper. Res. 52:209–230.Crossref, Google Scholar
  • Haouari M, Layeb SB, Sherali HD (2008) The prize collecting Steiner tree problem: Models and Lagrangian dual optimization approaches. Comp. Opt. Appl. 40:13–39.Crossref, Google Scholar
  • Haouari M, Layeb SB, Sherali HD (2010) Algorithmic expedients for the prize collecting Steiner tree problem. Discrete Optim. 7:32–47.Crossref, Google Scholar
  • Haouari M, Layeb SB, Sherali HD (2013) Tight compact models and comparative analysis for the prize collecting Steiner tree problem. Discrete App. Math. 161:618–632.Crossref, Google Scholar
  • Johnson DS, Minkoff M, Phillips S (2000) The prize collecting Steiner tree problem: theory and practice. Shmoys DB, ed. SODA (ACM/SIAM, Philadelphia), 760–769.Google Scholar
  • Jozefowiez N, Laporte G, Semet F (2012) A generic branch-and-cut algorithm for multiobjective optimization problems: Application to the multilabel traveling salesman problem. INFORMS J. Comp. 24:554–564.Link, Google Scholar
  • Kaparis K, Letchford A (2010) Separation algorithms for 0-1 knapsack polytopes. Math. Programming 124:69–91.Crossref, Google Scholar
  • Koch T, Martin A (1998) Solving Steiner tree problems in graphs to optimality. Networks 32:207–232.Crossref, Google Scholar
  • Leitner M, Ljubić I, Sinnl M (2013) Solving the bi-objective prize-collecting Steiner tree problem with the ε-constraint method. Electronic Notes Discrete Math. 41:181–188.Crossref, Google Scholar
  • Lemesre J, Dhaenens C, Talbi EG (2007) Parallel partitioning method (PPM): A new exact method to solve bi-objective problems. Comput. Oper. Res. 34:2450–2462.Crossref, Google Scholar
  • Levin MS, Nuiriakhmetov RI (2009) Multicriteria Steiner tree problem for communication network. Inform. Tech. Engrg. Systems 3:199–209.Google Scholar
  • Ljubić I, Weiskircher R, Pferschy U, Klau GW, Mutzel P, Fischetti M (2006) An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem. Math. Programming 105:427–449.Crossref, Google Scholar
  • Lucena A, Resende MGC (2001) Generating lower bounds for the prize collecting Steiner problem in graph. Electronic Notes Discrete Math. 7:70–73.Crossref, Google Scholar
  • Martins L, Ferreira NG (2011) A bi-criteria approach for Steiner’s tree problems in communication networks. Krieger U, Van Mieghem P, eds. Proc. 2011 Internat. Workshop on Modeling, Anal. Control of Complex Networks, ITCP (International Teletraffic Congress, San Francisco), 37–44.Google Scholar
  • Mavrotas G, Diakoulaki D (1998) A branch and bound algorithm for mixed zero-one multiple objective linear programming. Eur. J. Oper. Res. 107:530–541.Crossref, Google Scholar
  • Neumayer P, Schweigert D (1994) Three algorithms for bicriteria integer linear programs. OR Spectrum 16:267–276.Crossref, Google Scholar
  • Przybylski A, Gandibleux X, Ehrgott M (2008) Two phase algorithms for the bi-objective assignment problem. Eur. J. Oper. Res. 185:509–533.Crossref, Google Scholar
  • Raith A, Ehrgott M (2009) A two-phase algorithm for the biobjective integer minimum cost flow problem. Comput. Oper. Res. 36:1945–1954.Crossref, Google Scholar
  • Ralphs TK, Saltzman MJ, Wiecek MM (2006) An improved algorithm for biobjective integer programming and its application to network routing problems. Amer. Oper. Res. 147:43–70.Crossref, Google Scholar
  • Ramos RM, Alonso S, Sicilia J, González C (1998) The problem of the optimal biobjective spanning tree. Eur. J. Oper. Res. 111:617–628.Crossref, Google Scholar
  • Riera-Ledesma J, Salazar-González JJ (2005) The biobjective travelling purchaser problem. Eur. J. Oper. Res. 160:599–613.Crossref, Google Scholar
  • Ruzika S, Hamacher HW (2009) A survey on multiple objective minimum spanning tree problems. Lerner J, Wagner D, Zweig KA, eds. Algorithmics of Large and Complex Networks, Lecture Notes in Computer Science, Vol. 5515 (Springer, Berlin),104–116.Crossref, Google Scholar
  • Schweigert D, Neumayer P (1997) A reduction algorithm for integer multiple objective linear programs. Eur. J. Oper. Res. 99:459–462.Crossref, Google Scholar
  • Segev A (1987) The node-weighted Steiner tree problem. Networks 17:1–17.Crossref, Google Scholar
  • Sourd F, Spanjaard O (2008) A multiobjective branch-and-bound framework: Application to the biobjective spanning tree problem. INFORMS J. Comput. 20:472–484.Link, Google Scholar
  • Steiner S, Radzik T (2003) Solving the biobjective minimum spanning tree problem using a k-best algorithm. Technical report, King’s College, London.Google Scholar
  • Steuer RE (1989) Multiple Criteria Optimization: Theory, Computation, and Application (Krieger, Malabar, FL).Google Scholar
  • Steuer RE, Choo EU (1983) An interactive weighted Tchebycheff procedure for multiple objective programming. Math. Programming 26:326–344.Crossref, Google Scholar
  • Sylva J, Crema A (2004) A method for finding the set of non-dominated vectors for multiple objective integer linear programs. Eur. J. Oper. Res. 158:46–55.Crossref, Google Scholar
  • Ulungu EL, Teghem J (1995) The two phases method: An efficient procedure to solve bi-objective combinatorial optimization problems. Foundations Comput. Decision Sci. 20:149–165.Google Scholar
  • Visée M, Teghem J, Pirlot M, Ulungu EL (1998) Two-phases method and branch and bound procedures to solve the bi-objective knapsack problem. J. Global Optim. 12:139–155.Crossref, Google Scholar
  • Vujošević M, Stanojević M (2003) A bicriterion Steiner tree problem on graph. Yugoslav J. Oper. Res. 13:25–33.Crossref, Google Scholar
Previous
Back to Top
Next
INFORMS site uses cookies to store information on your computer. Some are essential to make our site work; Others help us improve the user experience. By using this site, you consent to the placement of these cookies. Please read our Privacy Statement to learn more.
Agree