The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms

DOI10.1016/J.COMGEO.2021.101771MaRDI QIDQ2230399zbMATH OpenOpenAlexFDO

Authors Dilson Almeida Guimarães, Alexandre Salles da Cunha

Publication date 17 September 2021

Published in Computational Geometry (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.comgeo.2021.101771

zbMATH Keywords

arrangementscombinatorial optimizationdiscrete geometryinteger programmingspanning trees

Mathematics Subject Classification ID

Integer programming (90C10) Combinatorial optimization (90C27)

Recommendations

• Algorithms and Data Structures
• The minimum-area spanning tree problem
• Exact and heuristic solutions for the minimum number of branch vertices spanning tree problem
• The generalized minimum spanning tree problem: Polyhedral analysis and branch-and-cut algorithm
• Improved formulations and branch-and-cut algorithms for the angular constrained minimum spanning tree problem

Cites work

• A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems
• A survey on Benders decomposition applied to fixed-charge network design problems
• Accelerating Benders Decomposition: Algorithmic Enhancement and Model Selection Criteria
• Algorithmic aspects of proportional symbol maps
• Arc-based integer programming formulations for three variants of proportional symbol maps
• Benchmarking optimization software with performance profiles.
• Benders decomposition, branch-and-cut, and hybrid algorithms for the minimum connected dominating set problem
• Combinatorial Benders' Cuts for Mixed-Integer Linear Programming
• Matroids and the greedy algorithm
• On a linear-programming, combinatorial approach to the traveling-salesman problem
• Partitioning procedures for solving mixed-variables programming problems
• Practical enhancements to the Magnanti-Wong method
• The minimum-area spanning tree problem
• Trees and Cuts
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(1)

• Algorithms and Data Structures

Describes a project that uses

Uses Software

• CGAL
• TSPLIB

This page was built for publication: The minimum area spanning tree problem: formulations, Benders decomposition and branch-and-cut algorithms

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2230399)