The prize-collecting generalized minimum spanning tree problem

DOI10.1007/s10732-007-9027-1zbMath1170.90466OpenAlexW2160886201MaRDI QIDQ2476612

S. Raghu Raghavan, Daliborka Stanojević, Bruce L. Golden

Publication date: 12 March 2008

Published in: Journal of Heuristics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10732-007-9027-1

zbMATH Keywords

Genetic algorithmsHeuristicsBranch-and-cutNetworksLocal search

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

Exact algorithms for budgeted prize-collecting covering subgraph problems ⋮ A two-level solution approach for solving the generalized minimum spanning tree problem ⋮ An effective two‐level solution approach for the prize‐collecting generalized minimum spanning tree problem by iterated local search ⋮ Continuous approximation formulas for location problems ⋮ A GRASP with path‐relinking and restarts heuristic for the prize‐collecting generalized minimum spanning tree problem ⋮ Models and branch‐and‐cut algorithms for the Steiner tree problem with revenues, budget and hop constraints ⋮ The generalized minimum edge-biconnected network problem: Efficient neighborhood structures for variable neighborhood search ⋮ Capacitated ring arborescence problems with profits ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances

Uses Software

• Genocop

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• New models of the generalized minimum spanning tree problem
• Using separation algorithms to generate mixed integer model reformulations
• Solving group Steiner problems as Steiner problems.
• Generalized spanning trees
• A new relaxation method for the generalized minimum spanning tree problem
• The pilot method: A strategy for heuristic repetition with application to the Steiner problem in graphs
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• Heuristic Search for the Generalized Minimum Spanning Tree Problem
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• A simple min-cut algorithm
• Ant-Tree: an ant colony optimization approach to the generalized minimum spanning tree problem
• The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
• Solving the generalized minimum spanning tree problem by a branch-and-bound algorithm
• On the generalized minimum spanning tree problem
• Steiner’s problem for set-terminals
• On generalized minimum spanning trees