Premium
A branch‐and‐cut algorithm for the resource‐constrained minimum‐weight arborescence problem
Author(s) -
Fischetti Matteo,
Vigo Daniele
Publication year - 1997
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199701)29:1<55::aid-net6>3.0.co;2-b
Subject(s) - branch and cut , travelling salesman problem , minimum weight , node (physics) , mathematical optimization , heuristic , mathematics , algorithm , extension (predicate logic) , computer science , minimum cut , integer programming , combinatorics , structural engineering , engineering , programming language
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.