Primal and Legrangian Heuristics for Minimum Weight Rooted Arborescence Problem

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 U’s, 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 U’s, 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. The Lagrangian heuristic was tested with fifty test problems, the number of nodes in the problems varying from ten to fifty-five. The following output was collected for each test problem: the value of the best upper bound, the value of the best lower bound, iteration numbers corresponding to the best upper and lower bounds, initial upper bound given by heuristic H, total number of iterations executed when the program stopped, number of times the value of the solution given by H was improved, and the total execution time in milli-seconds. In a high percentage (86%) of the test cases, the Lagrangian heuristic yielded optimal solution. In forty per cent of the cases, the initial solution obtained by the heuristic H itself turned out to be optimal. The execution time was less than 2 seconds for most of the test problems. Thus, the proposed heuristic seems promising enough to warrant further study.