A Branch-and-Cut Algorithm for the Resource-Constrained Minimum-Weight Arborescence Problem

In this paper, we present a branch-and-cut algorithm for the exact solution of an NP-hard extension of the well-known Minimum-Weight Arborescence (MWA) problem, in which resource constraints for each node are considered. This Resource-Constrained Minimum-Weight Arborescence (RMWA) problem arises, e.g., in the design of distribution networks in which finite resources are available at each node. Some main classes of cuts are described, and the corresponding separation algorithms are presented. Also, we outline a procedure to extend to RMWA some known classes of valid inequalities for the asymmetric traveling salesman problem. New heuristic procedures to compute near-optimal feasible solutions are proposed, which proved to be very effective to reduce the overall computing time spent by the branch-and-cut algorithm. Computational experience on three classes of test problems involving up to 500 vertices is reported, showing that the proposed approach outperforms other published methods. © 1997 John Wiley & Sons, Inc.