A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem

DOI10.1016/J.COR.2023.106248MaRDI QIDQ6164630zbMATH OpenOpenAlexFDO

Authors Mauro Dell'Amico, Jafar Jamal, Roberto Montemanni

Publication date 4 July 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1016/j.cor.2023.106248

zbMATH Keywords

branch and boundLagrangian relaxationmixed integer linear programmingnetwork optimizationprecedence constrained arborescences

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Recommendations

• Precedence-constrained arborescences
• THE PRECEDENCE CONSTRAINED TRAVELING SALESMAN PROBLEM
• A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
• The weighted arborescence constraint
• A Lagrangean Based Branch and Bound Algorithm for Single Machine Sequencing with Precedence Constraints to Minimize Total Weighted Completion Time

Cites work

• A branch-and-cut algorithm for the resource-constrained minimum-weight arborescence problem
• A heuristic manipulation technique for the sequential ordering problem
• A Lagrangian relax-and-cut approach for the sequential ordering problem with precedence relationships
• A randomly weighted minimum arborescence with a random cost constraint
• Algorithmic aspects of the maximum colorful arborescence problem
• An exact algorithm for the capacitated shortest spanning arborescence
• An exact algorithm for the sequential ordering problem and its application to switching energy minimization in compilers
• An inexact algorithm for the sequential ordering problem
• Efficient algorithms for finding minimum spanning trees in undirected and directed graphs
• scientific article; zbMATH DE number 3285076 (Why is no real title available?)
• Minimum k arborescences with bandwidth constraints
• On the choice of step size in subgradient optimization
• Optimum branchings
• Precedence-constrained arborescences
• The p-arborescence star problem: formulations and exact solution approaches
• The capacitated minimum spanning tree problem: On improved multistar constraints
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• The weighted arborescence constraint
• TSPLIB—A Traveling Salesman Problem Library

Cited in

(4)

• An application of lagrangean decomposition to the resource-constrained minimum weighted arborescence problem
• Precedence-constrained arborescences
• A novel hyper-heuristic based on surrogate genetic programming for the three-dimensional spatial resource-constrained project scheduling problem under uncertain environments
• A three-dimensional spatial resource-constrained project scheduling problem: model and heuristic

This page was built for publication: A branch-and-bound algorithm for the precedence-constrained minimum-cost arborescence problem

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