A branch-and-bound algorithm for the Precedence-Constrained Minimum-Cost Arborescence problem
针对带优先约束的最小费用有向生成树问题，提出一种基于拉格朗日松弛的分支定界算法，平均求解速度比现有最优方法快74.6%。
The Precedence-Constrained Minimum-Cost Arborescence problem, in which precedence constraints are enforced on pairs of vertices, has been recently proposed. The purpose of the constraints is to prevent the formation of directed paths along the tree that violate a precedence relationship. The problem has been shown to be NP-hard, and formulations for the problem have been proposed in the literature. This work introduces a branch-and-bound algorithm based on a Lagrangian relaxation for solving the problem. The results show that the newly proposed method is 74.6% faster, on average, compared to the state-of-the-art methods recently available in the literature.