An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem

DOI10.1007/s10107-005-0660-xzbMath1085.90061OpenAlexW2074613642WikidataQ56977277 ScholiaQ56977277MaRDI QIDQ2583134

Matteo Fischetti, Ulrich Pferschy, Gunnar W. Klau, Ivana Ljubić, René Weiskircher, Petra Mutzel

Publication date: 13 January 2006

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-005-0660-x

zbMATH Keywords

network design branch-and-cut prize collecting Steiner arborescence

Mathematics Subject Classification ID

Trees (05C05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Deterministic network models in operations research (90B10)

Related Items

Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Lagrangian heuristic for simultaneous subsidization and penalization: implementations on rooted travelling salesman games, Exact approaches to the single-source network loading problem, Spanning trees with variable degree bounds, Hop constrained Steiner trees with multiple root nodes, Exact algorithms for budgeted prize-collecting covering subgraph problems, Computing the metric dimension of graphs by genetic algorithms, Locating leak detecting sensors in a water distribution network by solving prize-collecting Steiner arborescence problems, Orientation-based models for \(\{0,1,2\}\)-survivable network design: theory and practice, Min-degree constrained minimum spanning tree problem: complexity, properties, and formulations, On exact solutions for the minmax regret spanning tree problem, A divide and conquer matheuristic algorithm for the prize-collecting Steiner tree problem, Lagrangian and branch-and-cut approaches for upgrading spanning tree problems, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, The Influence of Preprocessing on Steiner Tree Approximations, ILP heuristics and a new exact method for bi-objective 0/1 ILPs: application to fttx-network design, Comparison of formulations for the inventory routing problem, Chvátal-Gomory cuts for the Steiner tree problem, Stabilizing branch‐and‐price for constrained tree problems, Combinatorial Heuristics for Inventory Routing Problems, On the Exact Solution of Prize-Collecting Steiner Tree Problems, New formulations and branch-and-cut procedures for the longest induced path problem, On imposing connectivity constraints in integer programs, The coastal seaspace patrol sector design and allocation problem, Risk models for the prize collecting Steiner tree problems with interval data, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, Maximum weighted induced forests and trees: new formulations and a computational comparative review, Heuristic and exact algorithms for minimum-weight non-spanning arborescences, Solving Steiner trees: Recent advances, challenges, and perspectives, A node-based layered graph approach for the Steiner tree problem with revenues, budget and hop-constraints, The prize collecting Steiner tree problem: models and Lagrangian dual optimization approaches, Vertex covering with capacitated trees, Thinning out Steiner trees: a node-based model for uniform edge costs, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, Algorithmic expedients for the prize collecting Steiner tree problem, A Dual Ascent-Based Branch-and-Bound Framework for the Prize-Collecting Steiner Tree and Related Problems, Exact Approaches for Network Design Problems with Relays, Mathematical Programming Algorithms for Spatial Cloaking, Interdiction Games and Monotonicity, with Application to Knapsack Problems, Solving the quorumcast routing problem by constraint programming, A column generation approach for multicast routing and wavelength assignment with delay constraints in heterogeneous WDM networks, The cavity approach for Steiner trees packing problems, A Lagrangean-based decomposition approach for the link constrained Steiner tree problem, A Layered Graph Model and an Adaptive Layers Framework to Solve Delay-Constrained Minimum Tree Problems, Exact methods for solving the elementary shortest and longest path problems, Solving minimum-cost shared arborescence problems, An algorithmic framework for the exact solution of tree-star problems, A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks, Prize collecting Steiner trees with node degree dependent costs, MIP models for connected facility location: a theoretical and computational study, A branch-and-cut-and-price algorithm for vertex-biconnectivity augmentation, Solving the family traveling salesman problem, Capacitated ring arborescence problems with profits, Towards optimizing the deployment of optical access networks, An exact solution framework for the minimum cost dominating tree problem, Bumblebee visitation problem, Lagrangian decompositions for the two-level FTTx network design problem, Travelling on graphs with small highway dimension, A branch-and-price procedure for clustering data that are graph connected, A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs, Combinatorial optimization in system configuration design, A tailored Benders decomposition approach for last-mile delivery with autonomous robots, Strong Formulations for 2-Node-Connected Steiner Network Problems, The two-level diameter constrained spanning tree problem, Primal-dual based distributed approximation algorithm for Prize-collecting Steiner tree, An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem, Exact approaches for solving robust prize-collecting Steiner tree problems

Uses Software

SteinLib

Cites Work