The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm

DOI10.1002/net.10105zbMath1069.68114OpenAlexW2167459401MaRDI QIDQ4458720

Martine Labbé, Gilbert Laporte, Corinne Feremans

Publication date: 15 March 2004

Published in: Networks (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/net.10105

zbMATH Keywords

branch-and-cut algorithmnetwork designtelecommunicationstabu search heuristicpolyhedral analysisgeneralized minimum spanning tree

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Graph theory (including graph drawing) in computer science (68R10) Approximation methods and heuristics in mathematical programming (90C59)

Related Items (13)

A two-level metaheuristic for the all colors shortest path problem ⋮ Integer programming models and branch-and-cut approaches to generalized \(\{0,1,2\}\)-survivable network design problems ⋮ Layered graph models and exact algorithms for the generalized hop-constrained minimum spanning tree problem ⋮ 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 ⋮ A tabu search heuristic for the generalized minimum spanning tree problem ⋮ Combining variable neighborhood search with integer linear programming for the generalized minimum spanning tree problem ⋮ The prize-collecting generalized minimum spanning tree problem ⋮ The generalized minimum branch vertices problem: properties and polyhedral analysis ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances ⋮ Generalized network design polyhedra

Uses Software

• TSPLIB
• ABACUS

Cites Work

• Unnamed Item
• On the spanning tree polyhedron
• Class Steiner trees and VLSI-design
• Generalized spanning trees
• The class Steiner minimal tree problem: A lower bound and test problem generation
• A note on the generalized Steiner tree polytope
• A comparative analysis of several formulations for the generalized minimum spanning tree problem
• A new approach to the maximum-flow problem
• TSPLIB—A Traveling Salesman Problem Library
• A Branch-and-Cut Algorithm for the Symmetric Generalized Traveling Salesman Problem
• On the generalized minimum spanning tree problem
• The symmetric generalized traveling salesman polytope
• On the facial structure of set packing polyhedra
• Matroids and the greedy algorithm
• On generalized minimum spanning trees

This page was built for publication: The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm