A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem

DOI10.1002/(SICI)1097-0037(199701)29:1%3C55::AID-NET6%3E3.0.CO;2-BMaRDI QIDQ4345574zbMATH OpenOpenAlexFDO

Authors Matteo Fischetti, Daniele Vigo

Publication date 23 July 1997

Full work available at URL https://doi.org/10.1002/(sici)1097-0037(199701)29:1%3C55::aid-net6%3E3.0.co;2-b

zbMATH Keywords

branch-and-cutdesign of distribution networkheuristicminimum-weight arborescenceNP-hard extensionresource-constrained minimum-weight arborescence

Mathematics Subject Classification ID

Linear programming (90C05) Integer programming (90C10) Programming involving graphs or networks (90C35)

Recommendations

• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• The weighted arborescence constraint
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• A branch and cut method for the degree-constrained minimum spanning tree problem
• Models and heuristics for a minimum arborescence problem

Cited in

(8)

• The weighted arborescence constraint
• Heuristic and exact algorithms for minimum-weight non-spanning arborescences
• Optimality cuts and a branch-and-cut algorithm for the k-rooted mini-max spanning forest problem
• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Minimum‐weight rooted not‐necessarily‐spanning arborescence problem
• Column generation for extended formulations
• Precedence-constrained arborescences
• A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem

This page was built for publication: A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem

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