Primal and Lagrangian heuristics for minimum weight rooted arborescence problem

Abstract

Consider a rooted acyclic graph G with weights on arcs. In this graph, a minimum weight rooted arborescence (MRC) can be defined as one whose sum of arc weights is less than or equal to that of any other rooted arborescence (RA) in that graph. We introduce a Lagrangian heuristic for this problem and present computational results. First, we formulate the MRA problem as a zero-one integer program and discuss a heuristic H to construct an RA in a G. This heuristic generates an upper bound on the value of the objective function for the MRA problem. Next, we formulate a Lagrangian problem LMRA by relaxing one set of constraint of the zero-one program. In the process of relaxation, a set of multipliers U are required, one for each constraint to be relaxed. For a given set of Uzs, LMRA can be easily solved to optimality by separating it into several independent knapsack problems. Finally, for MRA, we propose a Lagrangian heuristic that iterates between the upper bound heuristic H and the knapsack solution for LMRA. Beginning with an upper bound generated by H, and an initial set of multipliers Uzs, we solve LMRA and obtain a lower bound for MRA, at the same time generating a partial solution which can be completed by H, thus getting a new upper bound for MRA. The iterations continue till either the best upper bound and best lower bound come close enough, or a suitable stopping condition is satisfied.