A parallel GRASP for the Steiner problem in graphs

Abstract. A greedy randomized adaptive search procedure (GRASP) is a metaheuristic for combinatorial optimization. Given an undirected graph with weights associated with its nodes, the Steiner tree problem consists in finding a minimum weight subgraph span

A Parallel GRASP for the Steiner Problem in Graphs Simone L. Martins, Celso C. Ribeiro, and Mauricio C. Souza Department of Computer Science, Catholic University of Rio de Janeiro, Rio de Janeiro, RJ 22453-900, Brazil. E-mail: fsimone,celso,souzag@inf.puc-rio.br.

is a metaheuristic for combinatorial optimization. Given an undirected graph with weights associated with its nodes, the Steiner tree problem consists in nding a minimum weight subgraph spanning a given subset of (terminal) nodes of the original graph. In this paper, we describe a parallel GRASP for the Steiner problem in graphs. We review basic concepts of GRASP: construction and local search algorithms. The implementation of a sequential GRASP for the Steiner problem in graphs is described in detail. Feasible solutions are characterized by their nonterminal nodes. A randomized version of Kruskal's algorithm for the minimum spanning tree problem is used in the construction phase. Local search is based on insertions and eliminations of nodes to/from the current solution. Parallelization is done through the distribution of the GRASP iterations among the processors on a demand-driven basis, in order to improve load balancing. The parallel procedure was implemented using the Message Passing Interface library on an IBM SP2 machine. Computational experiments on benchmark problems are reported.

Abstract. A greedy randomized adaptive search procedure (GRASP)

1 Introduction Let G= (V; E ) be a connected undirected graph, where V is the set of nodes and E denotes the set of edges. Given a non-negative weight function w: E ! IR+ associated with its edges and a subset X V of terminal nodes, the Steiner problem SPG(V; E; w; X ) consists in nding a minimum weighted connected subgraph of G spanning all terminal nodes in X . The solution of SPG(V; E; w; X ) is a Steiner minimal tree (SMT). The non-terminal nodes that end up in the SMT are called Steiner nodes. The Steiner problem in graphs is a classic NP-complete (Karp 13]) combinatorial optimization problem, see e.g. Hwang, Richards and Winter 10], Maculan 16], and Winter 27] for surveys on formulations, special cases, exact algorithms, and heuristics. Applications can be found in many areas, such as telecommunication network design, VLSI design, and computational biology, among others. Due to its NP-hardness, several heuristics have been developed

第1页下一页