Models and heuristics for a minimum arborescence problem

The Minimum Arborescence problem (MAP) consists of finding a minimum cost arborescence in a directed graph. This problem is NP-Hard and is a generalization of two well-known problems: the Minimum Spanning Arborescence Problem (MSAP) and the Directed Node Weighted Steiner Tree Problem (DNWSTP). We start the model presentation in this paper by describing four models for the MSAP (including two new ones, using so called "connectivity" constraints which forbid disconnected components) and we then describe the changes induced on the polyhedral structure of the problem by the removal of the spanning property. Only two (the two new ones) of the four models for the MSAP remain valid when the spanning property is removed. We also describe a multicommodity flow reformulation for the MAP that differs from well-known multicommodity flow reformulations in the sense that the flow conservation constraints at source and destination are replaced by inequalities. We show that the linear programming relaxation of this formulation is equivalent to the linear programming relaxation of the best of the two previous valid formulations and we also propose two Lagrangean relaxations based on the multicommodity flow reformulation. From the upper bound perspective, we describe a constructive heuristic as well as a local search procedure involving the concept of key path developed earlier for the Steiner Tree Problem. Numerical experiments taken from instances with up to 400 nodes are used to evaluate the proposed methods. (C) 2007 Wiley Periodicals, Inc.