Solving minimum-cost shared arborescence problems

DOI10.1016/J.EJOR.2016.11.004MaRDI QIDQ1751722zbMATH OpenOpenAlexFDO

Authors Eduardo Álvarez-Miranda, Ivana Ljubić, Martin Luipersbeck, Markus Sinnl

Publication date 25 May 2018

Published in European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.ejor.2016.11.004

zbMATH Keywords

Benders decompositionbioinformaticscombinatorial optimizationinteger programmingtelecommunications

Mathematics Subject Classification ID

Deterministic network models in operations research (90B10) Integer programming (90C10) Mixed integer programming (90C11) Programming involving graphs or networks (90C35) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57)

Recommendations

• Models and heuristics for a minimum arborescence problem
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• The p-arborescence star problem: formulations and exact solution approaches
• A branch and cut algorithm for the Steiner problem in graphs
• An SST-based algorithm for the steiner problem in graphs

Cites work

• A dual ascent approach for steiner tree problems on a directed graph
• A Modified Benders' Partitioning Algorithm for Mixed Integer Programming
• A survey on Benders decomposition applied to fixed-charge network design problems
• Acceleration of cutting-plane and column generation algorithms: Applications to network design
• An algorithmic framework for the exact solution of the prize-collecting Steiner tree problem
• An in-out approach to disjunctive optimization
• Benders decomposition without separability: a computational study for capacitated facility location problems
• Dual heuristics on the exact solution of large Steiner problems
• scientific article; zbMATH DE number 5831321 (Why is no real title available?)
• scientific article; zbMATH DE number 3677874 (Why is no real title available?)
• scientific article; zbMATH DE number 1926656 (Why is no real title available?)
• Improved algorithms for the Steiner problem in networks
• On implementing push-relabel method for the maximum flow problem
• Reduction tests for the steiner problem in grapsh
• Solving Steiner tree problems in graphs to optimality
• Solving two-stage stochastic Steiner tree problems by two-stage branch-and-cut
• Tailoring Benders decomposition for uncapacitated network design
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• Thinning out Steiner trees: a node-based model for uniform edge costs

Cited in

(4)

• The p-arborescence star problem: formulations and exact solution approaches
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• Minimum cost spanning tree problems as value sharing problems
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem

Describes a project that uses

Uses Software

• SteinLib
• OGDF

This page was built for publication: Solving minimum-cost shared arborescence problems

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