A relax-and-cut algorithm for the prize-collecting Steiner problem in graphs

DOI10.1016/j.dam.2008.02.014zbMath1173.90573OpenAlexW2058433703MaRDI QIDQ1025987

Alexandre Salles da Cunha, Mauricio G. C. Resende, Abilio Lucena, Nelson F. Maculan

Publication date: 23 June 2009

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2008.02.014

zbMATH Keywords

Lagrangian relaxationnon delayed relax-and-cutprize-collecting Steiner problem in graphs

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05)

Related Items

Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Lagrangian and branch-and-cut approaches for upgrading spanning tree problems, A relax-and-cut framework for large-scale maximum weight connected subgraph problems, On the Exact Solution of Prize-Collecting Steiner Tree Problems, Solving Steiner trees: Recent advances, challenges, and perspectives, Polyhedral results and a branch-and-cut algorithm for the \(k\)-cardinality tree problem, Algorithmic expedients for the prize collecting Steiner tree problem, Fast heuristics for the Steiner tree problem with revenues, budget and hop constraints, A fast prize-collecting Steiner forest algorithm for functional analyses in biological networks, An efficient algorithm for the Steiner tree problem with revenue, bottleneck and hop objective functions, Lagrangian heuristics for the quadratic knapsack problem, Exact approaches for solving robust prize-collecting Steiner tree problems

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the shortest spanning subtree of a graph and the traveling salesman problem
• A note on the prize collecting traveling salesman problem
• Non delayed relax-and-cut algorithms
• Edge exchanges in the degree-constrained minimum spanning tree problem
• The symmetric traveling salesman problem and edge exchanges in minimal 1- trees
• Lagrangean heuristics for location problems
• Strong lower bounds for the prize collecting Steiner problem in graphs
• A hybrid Lagrangian genetic algorithm for the prize collecting Steiner tree problem
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• Lower and upper bounds for the degree-constrained minimum spanning tree problem
• The node-weighted steiner tree problem
• The prize collecting traveling salesman problem
• Efficient path and vertex exchange in steiner tree algorithms
• Reducibility among Combinatorial Problems
• Solution of a Large-Scale Traveling-Salesman Problem
• Steiner's problem in graphs and its implications
• An algorithm for the steiner problem in graphs