.png){kind=icon}
.png){kind=icon}
Return
A branch-and-bound algorithm for the Precedence-Constrained Minimum-Cost Arborescence problem
.png){kind=icon}
OA
AI
DOI：10.1016/j.cor.2023.106248.png)
.png){kind=icon}
.png){kind=icon}
Share.png){kind=icon}
Save
Abstract
En 中文
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.
Keywords:
Precedence constrained arborescences
Mixed integer linear programming
Branch and bound
Lagrangian relaxation
Network optimization
AI Summary
Key information extracted from the uploaded paper, including a brief overview, abstract, background, key highlights, visual analysis, and future outlook.
Journal
C
IF:
4.3
Papers:
6.5K
Citations:
1.8W