15 GRASP: AN ANNOTATED
`
`BIBLIOGRAPHY
`Paola Festal and Mauricio G.c. Resende2
`
`1 Mathematics and Computer Science Department
`University of Salerno, 84081 Baronissi (SA), Italy
`paofes@unisa.it
`
`21nformation Sciences Research Center
`AT& T Labs Research, 180 Park Avenue, Room (241
`Florham Park, NJ 07932 USA
`mgcr@research.att.com
`
`Abstract: A greedy randomized adaptive search procedure (GRASP) is a
`metaheuristic for combinatorial optimization. It is a multi-start or iterative
`process, in which each GRASP iteration consists of two phases, a construction
`phase, in which a feasible solution is produced, and a local search phase, in which
`a local optimum in the neighborhood of the constructed solution is sought. Since
`1989, numerous papers on the basic aspects of GRASP, as well as enhancements
`to the basic metaheuristic have appeared in the literature. GRASP has been
`applied to a wide range of combinatorial optimization problems, ranging from
`scheduling and routing to drawing and turbine balancing. This paper is an
`annotated bibliography of the GRASP literature from 1989 to 2001.
`
`15.1
`INTRODUCTION
`Optimization problems that involve a large finite number of alternatives often
`arise in the private and public sectors of the economy. In these problems, given
`a finite solution set X and a real-valued function f : X -t lR, one seeks a
`solution x* E X with f(x*) ::::; f(x), V x E X. Common examples include de-
`signing efficient telecommunication networks, constructing cost effective airline
`crew schedules, and producing efficient routes for waste management pickup.
`To find the optimal solution in a combinatorial optimization problem it is the-
`oretically possible to enumerate the solutions and evaluate each with respect to
`
`

`

`326
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`the stated objective. However, in practice, it is often infeasible to follow such
`a strategy of complete enumeration because the number of combinations often
`grows exponentially with the size of problem.
`Much work has been done over the last five decades to develop optimal seek-
`ing methods that do not explicitly require an examination of each alternative.
`This research has given rise to the field of combinatorial optimization (see Pa-
`padimitriou and Steiglitz [1]), and an increasing capability to solve ever larger
`real-world problems. Nevertheless, most problems found in industry and gov-
`ernment are either computationally intractable by their nature, or sufficiently
`large so as to preclude the use of exact algorithms. In such cases, heuristic
`methods are usually employed to find good, but not necessarily guaranteed
`optimal solutions. The effectiveness of these methods depends upon their abil-
`ity to adapt to a particular realization, avoid entrapment at local optima, and
`exploit the basic structure of the problem. Building on these notions, vari-
`ous heuristic search techniques have been developed that have demonstrably
`improved our ability to obtain good solutions to difficult combinatorial opti-
`mization problems. The most promising of such techniques include simulated
`annealing (Kirkpatrick [2]), tabu search (Glover [3,4], Glover and Laguna [5]),
`genetic algorithms (Goldberg [6]), variable neighborhood search (Hansen and
`Mladenovic [7]), and GRASP (Greedy Randomized Adaptive Search Proce-
`dures) (Feo and Resende [8,9]).
`A GRASP is a multi-start or iterative process (Lin and Kernighan [10]), in
`which each GRASP iteration consists of two phases, a construction phase, in
`which a feasible solution is produced, and a local search phase, in which a local
`optimum in the neighborhood of the constructed solution is sought. The best
`overall solution is kept as the result.
`In the construction phase, a feasible solution is iteratively constructed, one
`element at a time. The basic GRASP construction phase is similar to the semi-
`greedy heuristic proposed independently by Hart and Shogan [11]. At each
`construction iteration, the choice of the next element to be added is determined
`by ordering all candidate elements (i.e. those that can be added to the solution)
`in a candidate list C with respect to a greedy function 9 : C -t JR. This
`function measures the (myopic) benefit of selecting each element. The heuristic
`is adaptive because the benefits associated with every element are updated at
`each iteration of the construction phase to reflect the changes brought on by the
`selection of the previous element. The probabilistic component of a GRASP
`is characterized by randomly choosing one of the best candidates in the list,
`but not necessarily the top candidate. The list of best candidates is called
`the restricted candidate list (RCL). This choice technique allows for different
`solutions to be obtained at each GRASP iteration, but does not necessarily
`compromise the power of the adaptive greedy component of the method.
`As is the case for many deterministic methods, the solutions generated by a
`GRASP construction are not guaranteed to be locally optimal with respect to
`simple neighborhood definitions. Hence, it is almost always beneficial to apply
`a local search to attempt to improve each constructed solution. A local search
`
`

`

`GRASP : AN ANNOTATED BIBLIOGRAPHY
`
`327
`
`algorithm works in an iterative fashion by successively replacing the current
`solution by a better solution in the neighborhood of the current solution. It
`terminates when no better solution is found in the neighborhood. The neigh-
`borhood structure N for a problem P relates a solution s of the problem to a
`subset of solutions N(s). A solution s is said to be locally optimal if there is no
`better solution in N (s) . The key to success for a local search algorithm con-
`sists of the suitable choice of a neighborhood structure, efficient neighborhood
`search techniques, and the starting solution.
`While such local optimization procedures can require exponential time
`(Johnson, Papadimitriou, and Yannakakis [12]) from an arbitrary starting point,
`empirically their efficiency significantly improves as the initial solution im-
`proves. The result is that often many GRASP solutions are generated in the
`same amount of time required for the local optimization procedure to converge
`from a single random start. Furthermore, the best of these GRASP solutions is
`generally significantly better than the single solution obtained from a random
`starting point.
`It is difficult to formally analyze the quality of solution values found by using
`the GRASP methodology. However, there is an intuitive justification that views
`GRASP as a repetitive sampling technique. Each GRASP iteration produces
`a sample solution from an unknown distribution of all obtainable results. The
`mean and variance of the distribution are functions of the restrictive nature of
`the candidate list. For example, if the cardinality of the restricted candidate list
`is limited to one, then only one solution will be produced and the variance of the
`distribution will be zero. Given an effective greedy function, the mean solution
`value in this case should be good, but probably suboptimal. If a less restrictive
`cardinality limit is imposed, many different solutions will be produced implying
`a larger variance. Since the greedy function is more compromised in this case,
`the mean solution value should degrade. Intuitively, however, by order statistics
`and the fact that the samples are randomly produced, the best value found
`should outperform the mean value. Indeed, often the best solutions sampled
`are optimal.
`An especially appealing characteristic of GRASP is the ease with which it
`can be implemented. Few parameters need to be set and tuned, and there-
`fore development can focus on implementing efficient data structures to assure
`quick GRASP iterations. Finally, GRASP can be trivially implemented in par-
`allel. Each processor can be initialized with its own copy of the procedure, the
`instance data, and an independent random number sequence. The GRASP iter-
`ations are then performed in parallel with only a single global variable required
`to store the best solution found over all processors.
`In this article, we provide an annotated bibliography of the GRASP litera-
`ture up to early 2001. This document contains references related to GRASP
`that have either appeared in the literature or as technical reports. We first look
`at tutorials and surveys. Papers that propose enhancements to the basic heuris-
`tic are considered next. Following that, we examine GRASP as a component
`of a hybrid metaheuristic. Parallelization of GRASP and GRASP source code
`
`

`

`328
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`follow. The paper concludes with a literature review of operations research and
`computer science applications of GRASP as well as industrial applications.
`If the reader is aware of any unci ted reference, incorrectly cited reference, or
`update to a cited reference, please contact the authors.
`
`[1] C.H. Papadimitriou and K. Steiglitz. Combinatorial Optimization: Algo-
`rithms and Complexity. Prentice-Hall, 1982.
`
`A classic book on combinatorial optimization.
`
`[2] S. Kirkpatrick. Optimization by Simulated Annealing: Quantitative
`Studies. Journal of Statistical Physics, 34:975-986, 1984.
`
`Description of the simulated annealing metaheuristic.
`
`[3] F. Glover. Tabu search - Part I. ORSA Journal on Computing, 1:190-
`206,1989.
`
`Description of the tabu search metaheuristic.
`
`[4] F. Glover. Tabu search - Part II. ORSA Journal on Computing, 2:4-32,
`1990.
`
`Description of the tabu search metaheuristic.
`
`[5] F. Glover and M. Laguna. Tabu Search. Kluwer, 1997.
`
`Book on metaheuristics and in particular tabu search.
`
`[6] D.E Goldberg. Genetic Algorithms in Search, Optimization and Machine
`Learning. Addison-Wesley, 1989.
`
`Book on genetic algorithms.
`
`[7] P. Hansen and N. Mladenovic. An Introduction to Variable Neighborhood
`Search. In: S. Voss, S. Martello, I.H. Osman, and C. Roucairol, editors,
`Meta-Heuristics, Advances and Trends in Local Search Paradigms for
`Optimization, pages 433-458. Kluwer, 1998.
`
`Description of the variable neighborhood search metaheuristic.
`
`[8] T.A. Feo and M.G.C. Resende. A Probabilistic Heuristic for a Compu-
`tationally Difficult Set Covering Problem. Operations Research Letters,
`8:67-71, 1989.
`
`This is the first paper to explicitly describe a GRASP. See page 365.
`
`[9] T.A. Feo and M.G.C. Resende. Greedy Randomized Adaptive Search
`Procedures. Journal of Global Optimization, 6:109-133, 1995.
`
`An early survey of GRASP. See page 329.
`
`[10] S. Lin and B.W. Kernighan. An Effective Heuristic Algorithm for the
`Traveling-Salesman Problem. Operations Research, 21:498-516, 1973.
`
`

`

`GRASP: AN ANNOTATED BIBLIOGRAPHY
`
`329
`
`An early random multistart local search technique.
`
`[11] J.P. Hart and A.W. Shogan. Semi-Greedy Heuristics: An Empirical
`Study. Operations Research Letters, 6:107-114, 1987.
`
`This paper presents a randomized greedy heuristic, called semi-
`greedy heuristic.
`
`[12]D.S. Johnson, C.H. Papadimitriou, and M. Yannakakis. How Easy is
`Local Search? Journal of Computer and System Sciences, 17:79-100,
`1988.
`
`Study of the computational complexity of local search.
`
`15.2 TUTORIALS AND SURVEYS
`Since GRASP is a relatively recent optimization method, tutorials and surveys
`on this subject are limited. Below are a few examples of introductory material
`on GRASP.
`
`[13] T.A. Feo and M.G.C. Resende. Greedy Randomized Adaptive Search
`Procedures. Journal of Global Optimization, 6:109-133, 1995.
`
`In this tutorial paper, the authors define the various components
`comprising a GRASP. A general trivial implementation of GRASP
`on a parallel computer is also discussed. The GRASP literature until
`1994 is surveyed.
`
`[14] J.L. Gonzalez. GRASP. In: Heuristic Optimization and Neural Networks
`in Operations Management and Engineering, A. Diaz, editor, pages 143-
`161. Editorial Paraninfo, 1996.
`
`This is a chapter on GRASP in a book on heuristic procedures for
`optimization. In Spanish.
`
`[15] M.G.C. Resende. Greedy Randomized Adaptive Search Procedures
`(GRASP). To appear in: Encyclopedia of Optimization, Kluwer, 2001.
`
`This paper surveys greedy randomized adaptive search procedures.
`The basic GRASP is explained in detail and enhancements to the
`basic procedure are described. Several applications of GRASP are
`reported, showing how this method can find good approximate so-
`lutions to operations research problems and industrial applications.
`
`[16] C.M.D. Silveira. GRASP - A Heuristic for Solving Combinatorial Opti-
`mization Problems. Technical Report, Institute of Informatics, Federal
`University of Rio Grande do SuI, Porto Alegre, 1999.
`
`The aim of this report is to provide an exhaustive description of
`the features of GRASP as a metaheuristic method for solving hard
`combinatorial optimization problems. The various components com-
`prising a generic GRASP are defined and it is also shown through
`
`

`

`330
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`examples how to develop GRASPs for combinatorial optimization
`problems. In Portuguese.
`
`[17] L.S. Pitsoulis and M.G.C. Resende. Greedy Randomized Adaptive Search
`Procedures. In: Handbook of Applied Optimization, P.M. Pardalos and
`M.G.C. Resende, editors, Oxford University Press, 2001.
`
`This chapter surveys GRASP. Multi-start heuristics are seen as a
`way to apply local search to solve combinatorial optimization prob-
`lems. GRASP is shown to, in some ways, improve upon greedy or
`random multi-start procedures. Enhancements to GRASP, such as
`reactive GRASP, hybrid GRASP, and use of long-term memory are
`discussed. The parallelization of GRASP is also considered. The
`chapter ends with a survey of GRASP for solving problems in logic,
`assignment, and location.
`
`15.3 ENHANCEMENTS TO THE BASIC GRASP
`The standard (or basic) GRASP consists of repeated applications of GRASP
`construction (using a fixed candidate list strategy), followed by hill climbing
`local search. Enhancements to this basic GRASP are found in the following
`papers.
`
`[18] J.L. Bresina. Heuristic-Biased Stochastic Sampling. In: Proceedings of
`the Thirteenth National Conference on Artificial Intelligence, pages 271-
`278,1996.
`
`This paper presents a generalization of iterative sampling called
`Heuristic-Biased Stochastic Sampling (HBSS). The two search tech-
`niques have the same overall control structure. The difference lies
`in how a choice is made at each decision point. HBSS uses a given
`search heuristic to focus its exploration. The degree of focusing is de-
`termined by a chosen bias function that reflects the confidence one
`has in the heuristic's accuracy. This methodology can be directly
`applied in a GRASP construction phase, by biasing the selection of
`RCL elements to favor those with higher greedy function values.
`
`[19] J. Mockus, E. Eddy, A. Mockus, L. Mockus, and G.V. Reklaitis. Bayesian
`Discrete and Global Optimization. Kluwer, 1997.
`
`This book describes the Bayesian approach to discrete optimization.
`A Bayesian heuristic algorithm version of GRASP is described.
`
`[20] J.B. Atkinson. A Greedy Randomised Search Heuristic for Time-Con-
`strained Vehicle Scheduling and the Incorporation of a Learning Strategy.
`Journal of the Operational Research Society, 49:700-708, 1998.
`
`Two forms of adaptive search called local and global adaptation are
`identified. In both search techniques, the greedy function takes into
`account a quantity that measures heuristically the quality of the
`partial solution. While in local adaptation the decisions made within
`a particular run influence only the subsequent performance of the
`
`

`

`GRASP: AN ANNOTATED BIBLIOGRAPHY
`
`331
`
`heuristic, global adaptation involves making decisions that affect
`the performance of the heuristic in subsequent runs. See page 342.
`
`[21] C. Fleurent and F. Glover. Improved Constructive Multistart Strate-
`gies for the Quadratic Assignment Problem Using Adaptive Memory.
`INFORMS Journal on Computing, 11:198-204, 1999.
`
`Study of alternatives to memory less multistart approaches like
`GRASP is conducted for the quadratic assignment problem. Adap-
`tive memory strategies retain and analyze features of selected so-
`lutions in order to provide a basis for improving future executions
`of the constructive process. The authors show that the most effec-
`tive strategies are tabu search methods, which use memory in both
`improving and constructive phases. See page 354.
`
`[22] M. Laguna and R. Marti. GRASP and Path Relinking for 2-Layer
`Straight Line Crossing Minimization. INFORMS Journal on Comput-
`ing, 11:44-52, 1999.
`
`This paper incorporates to GRASP a path rei inking strategy to
`search for improved outcomes. Path relinking generates new so-
`lutions by exploring trajectories connecting high quality solutions.
`Starting from an initiating solution, path relinking generates a path
`in the neighborhood space that leads toward the other solutions,
`called guiding solutions. This is accomplished by selecting moves
`that introduce attributes contained in the guiding solutions. See
`page 363.
`
`[23] M. Prais. Parameter Variation in GRASP Procedures. Ph.D. Thesis,
`Department of Computer Sciences, Catholic University of Rio de Janeiro,
`Rio de Janeiro, 2000.
`
`This thesis describes a GRASP for a matrix decomposition problem
`in TDMA traffic assignment. It proposes Reactive GRASP, a refine-
`ment of GRASP where the RCL parameter is adjusted dynamically
`to favor values that produce good solutions. Reactive GRASP is
`compared with other RCL strategies on matrix decomposition, set
`covering, maximum satisfiability and graph planarization.
`
`[24] M. Prais and C.C. Ribeiro. Reactive GRASP: An Application to a Ma-
`trix Decomposition Problem in TDMA 'fraffic Assignment. INFORMS
`Journal on Computing, 12:164-176,2000.
`
`A refinement of GRASP, called Reactive GRASP, is proposed. In-
`stead of using a fixed value for the basic parameter that defines the
`restrictiveness of the candidate list during the construction phase,
`Reactive GRASP self-adjusts the parameter value according to the
`quality of the solutions previously found. See pages 355 and 362.
`
`[25] M. Prais and C.C. Ribeiro. Parameter Variation in GRASP Procedures.
`Investigaci6n Operativa, 9:1-20, 2000.
`
`

`

`332
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`The GRASP RCL parameter a that determines the size of the re-
`stricted candidate list can be adjusted, leading to different behavior
`of the GRASP implementation. This paper investigates four strate-
`gies for the variation of the parameter a: 1) reactive - a is self-
`adjusted along the iterations; 2) uniform - a is randomly chosen
`from a discrete uniform probability distribution; 3) hybrid - a is
`randomly chosen from a fixed probability distribution concentrated
`around the value corresponding to the purely greedy choice; 4) fixed
`- a has a fixed value close to the purely greedy choice. The reactive
`strategy is the most flexible and adherent to the characteristics of
`the specific problem to be solved. In Portuguese.
`
`[26] C.C. Ribeiro, E. Uchoa, and R.F. Werneck. A Hybrid GRASP with
`Perturbations and Adaptive Path-Relinking for the Steiner Problem in
`Graphs. Technical Report, Department of Computer Science, Catholic
`University of Rio de Janeiro, Rio de Janeiro, 2000.
`
`This paper describes a hybrid GRASP with weight perturbations
`and adaptive path-relinking heuristic (HGP-PR) for the Steiner prob-
`lem in graphs. In this multi-start approach, the greedy randomized
`construction phase of a GRASP is replaced by the combination of
`several construction heuristics with a weight perturbation strategy.
`A strategic oscillation scheme combining intensification and diversi-
`fication elements is used for the perturbation of the original weights.
`The improvement phase circularly explores two different local search
`strategies. An adaptive path-relinking technique is applied to a set of
`elite solutions as an intensification strategy. Computational experi-
`ments on a large set of benchmark problems of three different classes
`are reported. The new heuristic HGP-PR outperformed other algo-
`rithms, obtaining consistently better or comparably good solutions
`for all classes of test problems.
`
`15.4 GRASP IN HYBRID METAHEURISTICS
`GRASP has been used in conjunction with other metaheuristics. The following
`papers illustrate these hybrid techniques.
`
`[27] M. Laguna and J .L. Gonzruez-Velarde. A Search Heuristic for Just-in-
`Time Scheduling in Parallel Machines. Journal of Intelligent Manufac-
`turing, 2:253-260, 1991.
`
`The proposed hybrid metaheuristic combines elements of GRASP
`with elements of tabu search. See page 339.
`
`[28] M. Yagiura and T. Ibakari. Genetic and Local Search Algorithms as
`Robust and Simple Optimization Tools. In: Meta-Heuristics: Theory and
`Applications, LH. Osman and J.P. Kelly, editors, pages 63-82. Kluwer,
`1996.
`
`Various metaheuristics such as random multi-start local search (MLS)
`and genetic algorithm (GA) are implemented in this paper and their
`
`

`

`GRASP: AN ANNOTATED BIBLIOGRAPHY
`
`333
`
`performance compared. The objective of the authors is not to pro-
`pose the most powerful technique, but to compare general tendencies
`of various algorithms. From their analysis it results that a GRASP
`type modification of MLS improves its performance and that GA
`combined with local search is quite effective if long computational
`time is allowed.
`
`[29] R. Colome and D. Serra. Consumer Choice in Competitive Location
`Models: Formulations and Heuristics. To appear in: Papers in Regional
`Science.
`
`The authors propose a hybrid GRASP which uses tabu search in the
`local search phase. See page 365.
`
`J .P. Paixiio, and R. Portugal. Metaheuristics
`[30] H. Ramalhinho
`for the Bus-Driver Scheduling Problem. Technical Report, Department
`of Economics and Management, Universitat Pompeu Fabra, Barcelona,
`1998.
`
`GRASP is used in a genetic algorithm to implement a type of crossover
`called perfect offspring. See page 340.
`
`[31] H. Delmaire, J.A. Diaz, E. Fernandez, and M. Ortega. Reactive GRASP
`and Tabu Search Based Heuristics for the Single Source Capacitated Plant
`Location Problem. INFOR, 37:194-225, 1999.
`
`A hybrid heuristic is proposed. It embeds a reactive GRASP in a
`tabu search algorithm as a diversification method that provides elite
`candidate sets. Intensification is also done. See page 346.
`
`[32] R.K. Ahuja, J.B. Orlin, and A. Tiwari. A Greedy Genetic Algorithm
`for the Quadratic Assignment Problem. Computers and Operations Re-
`search, 27:917-934, 2000.
`
`In this paper a hybrid genetic algorithm for the QAP is presented.
`GRASP is used to generate the initial population. See page 355.
`
`[33] M. Armony, J .G. Klincewicz, H. Luss, and M.B. Rosenwein. Design of
`Stacked Self-Healing Rings using a Genetic Algorithm. Journal of Heuris-
`tics, 6:85-105, 2000.
`
`A genetic algorithm for design of stacked self-healing rings is pro-
`posed. The objective is to optimize the trade-off between the cost of
`connecting nodes to the ring and the cost of routing demand on mul-
`tiple rings. The initial population of the genetic algorithm is made
`up of randoml} generated solutions as well as solutions generated by
`a GRASP. Computational comparisons are made with a commercial
`integer programming package.
`
`[34] S. Abdinnour-Helm and S.W. Hadley. Tabu Search Based Heuristics for
`Multi-Floor Facility Layout.
`International Journal of Production Re-
`search, 38:365-383,2000.
`
`

`

`334
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`Two two-stage heuristics are proposed for solving the multi-floor fa-
`cility layout problem. GRASP /TS applies a GRASP to find the
`initial layout and tabu search to refine the initial layout, based
`on total inter/intra-floor costs. Computational tests indicate that
`GRASP /TS compares favorably with heuristics that do not rely on
`exact algorithms.
`
`[35] C.C. Ribeiro, E. Uchoa, and R.F. Werneck. A Hybrid GRASP with
`Perturbations and Adaptive Path-Relinking for the Steiner Problem in
`Graphs. Technical Report, Department of Computer Science, Catholic
`University of Rio de Janeiro, Rio de Janeiro, 2000.
`
`This paper propose and describes a hybrid GRASP with weight per-
`turbations and adaptive path-relinking heuristic (HGP-PR) for the
`Steiner problem in graphs. See page 332.
`
`15.5 PARALLEL GRASP
`
`GRASP can be easily implemented in parallel by dividing iterations among sev-
`eral processors. Other parallelization schemes have also been used to implement
`parallel GRASPs. The following papers exemplify parallel GRASP.
`
`[36] T.A. Feo, M.G.C. Resende, and S.H. Smith. A greedy Randomized Adap-
`tive Search Procedure for Maximum Independent Set. Operations Re-
`search, 42:860-878, 1994.
`
`A GRASP for approximately solving the maximum independent set
`problem is described. The proposed heuristic can be easily imple-
`mented in parallel by decomposing the problem into smaller sub-
`problems, each defined by conditioning on vertices being in the so-
`lution. An implementation of this algorithm was tested on a MIMD
`computer with up to eight processors. Average linear speedup is
`observed. See page 347.
`
`[37] P.M. Pardalos, L. Pitsoulis, T. Mavridou, and M.G.C. Resende. Parallel
`Search for Combinatorial Optimization: Genetic Algorithms, Simulated
`Annealing and GRASP. Lecture Notes in Computer Science, 980:317-331,
`1995.
`
`This paper summarizes some parallel search techniques for approx-
`imating the global optimal solution of combinatorial optimization
`problems. For large-scale problems, one of the main limitations of
`heuristic search is its computational complexity. Therefore, efficient
`parallel implementation of search algorithms can significantly in-
`crease the size of the problems that can be solved.
`
`[38] P.M. Pardalos, L.S. Pitsoulis, and M.G.C. Resende. A Parallel GRASP
`Implementation for the Quadratic Assignment Problem. In: Parallel Al-
`gorithms for Irregularly Structured Problems - Irregular'94, A. Ferreira
`and J. Rolim, editors, pages 115-130, Kluwer, 1995.
`
`

`

`GRASP: AN ANNOTATED BIBLIOGRAPHY
`
`335
`
`Efficient parallel techniques for large-scale sparse quadratic assign-
`ment problems are discussed. The paper provides a detailed de-
`scription of a parallel implementation on an MIMD computer of the
`sequential GRASP proposed by Li, Pardalos, and Resende (1994)
`for solving the QAP. The GRASP iterations are distributed among
`the processors. Each processor is given its own input data and ran-
`dom number sequence and are run independently. A shared global
`variable stores the value of the incumbent solution.
`
`[39) P.M. Pardalos, L.S. Pitsoulis, and M.G.C. Resende. A Parallel GRASP
`for MAX-SAT Problems. Lecture Notes in Computer Science, 1184:575-
`585, 1996.
`
`A parallel GRASP for weighted maximum satisfiability (MAX-SAT)
`problem is proposed. The GRASP is based on the serial GRASP
`presented by Resende, Pitsoulis, and Pardalos (1997). The paral-
`lel implementation distributes the GRASP iterations among several
`processors operating in parallel, avoiding that two processors have
`as input the same random number generator seed. The best solution
`found among all processors is identified and used as solution of the
`problem.
`
`[40) A.C.F. Alvim. Parallelization Strategies for the Metaheuristic GRASP.
`Master's Thesis, Department of Computer Science, Catholic University
`of Rio de Janeiro, Rio de Janeiro, 1998.
`
`Two parallelization strategies for GRASP are discussed and com-
`pared: parallelization by distributing GRASP iterations and paral-
`lelization by varying the GRASP random parameter a. Both strate-
`gies are adapted to several parallel computation models, such as MPI
`(Message Passing Interface) and PVM (Parallel Virtual Machine).
`In Portuguese.
`
`[41) A.C.F. Alvim and C.C. Ribeiro. Load Balancing in the Parallelization of
`the Metaheuristic GRASP. In: Proceedings of the X Brazilian Symposium
`on Computer Architecture, pages 279-282, Buzios, 1998.
`
`Two parallelization strategies for GRASP are compared. The differ-
`ence between the two strategies concerns the way in which data is
`partitioned: pre-scheduled (static load balancing) or self-scheduled
`(dynamic load balancing). The strategies have been tested consider-
`ing an application to optimal traffic assignment in TDMA satellite
`system. Best results have been obtained by using the self-scheduling
`strategy. In Portuguese.
`
`[42) S.L. Martins, C.C. Ribeiro, and M.C. Souza. A Parallel GRASP for
`the Steiner Problem in Graphs. Lecture Notes in Computer Science,
`1457:285-297, 1998.
`
`A parallelization of a sequential GRASP for the Steiner minimal tree
`problem is proposed. The procedure implemented is one of the pro-
`cedures described in Martins, Pardalos, Resende, and Ribeiro (1999).
`
`

`

`336
`
`ESSAYS AND SURVEYS IN METAHEURISTICS
`
`The parallelization is accomplished by distributing the GRASP it-
`erations among the processors on a demand-driven basis.
`
`[43] R.A. Murphey, P.M. Pardalos, and L.S. Pitsoulis. A Parallel GRASP for
`the Data Association Multidimensional Assignment Problem. The IMA
`Volumes in Mathematics and its Applications, 106:159-180,1998.
`
`A parallel GRASP for finding good solutions for the data association
`problem is described. See page 353.
`
`[44] P.M. Pardalos, M.G.C. Resende, and J. Rappe. An Exact Parallel Al-
`gorithm for the Maximum Clique Problem. In: High Performance Algo-
`rithms and Software in Nonlinear Optimization, R. De Leone, A. Murli,
`P.M. Pardalos, and G. Toraldo, editors, pages 279-300. Kluwer, 1998.
`
`A parallelized version of the exact algorithm of Carraghan and Parda-
`los (1990) for the unweighted maximum clique problem is described.
`A variant of the GRASP for the maximum independent set problem
`of Feo, Resende, and Smith (1994) is used for computing feasible
`solutions.
`
`[45] L.I.D. Rivera. Evaluation of Parallel Implementations of Heuristics for
`the Course Scheduling Problem. Master's Thesis, Instituto Tecnologico y
`de Estudios Superiores de Monterrey, Monterrey, 1998.
`
`This thesis presents several parallel implementations of heuristics for
`the course scheduling problem. One of the heuristics is a GRASP.
`In Spanish.
`
`[46] S.L. Martins. Parallelization Strategies for Metaheuristics in Distributed
`Memory Environments. Ph.D. Thesis, Department of Computer Sciences,
`Catholic University of Rio de Janeiro, Rio de Janeiro, 1999.
`
`This thesis considers parallelization strategies for metaheuristics in
`distributed memory environments. GRASPs for the Steiner tree
`problem in graphs are described and implemented in parallel. In
`Portuguese.
`[47] R.M. Aiex, M.G.C. Resende, and C.C. Ribeiro. Probability Distribution
`of Solution Time in GRASP: An Experimental Investigation. To appear
`in: Journal of Heuristics.
`
`The authors study the probability distributions of solution time to a
`sub-optimal target value in five GRASPs that have appeared in the
`literature and for which source code is available. The distributions
`are estimated by running 12,000 independent runs of the heuristic.
`Standard methodology for graphical analysis is used to compare the
`empirical and theoretical distributions and estimate the parameters
`of the distributions. They conclude that the solution time to a sub-
`optimal target value fits a two-parameter exponential distribution.
`Hence, it is possible to approximately achieve linear speed-up by
`implementing GRASP in parallel.
`
`

`

`GRASP: AN ANNOTATED BIBLIOGRAPHY
`
`337
`
`[48] R.M. Aiex, M.G.C. Resende, P.M. Pardalos, and G. Toraldo. GRASP
`with Path Relinking for the Three-Index Assignment Problem. Technical
`Report, AT&T Labs Research, Florham Park, 2000.
`
`This paper describes variants of GRASP with path relinking for
`the three index assignment problem (AP3). Computational results
`show clearly that this GRASP for AP3 benefits from path relinking
`and that the variants considered in this paper compare well with
`previously proposed heuristics for this problem. The authors also
`show that the random variable "time to target solution," for all
`proposed GRASP with path relinking variants, fits a two-parameter
`exponential distribution. To illustrate the consequence of this, one
`of the variants of GRASP with path relinking is shown to benefit
`from parallelization.
`
`[49] S.L. Martins, M.G.C. Resende, C.C. Ribeiro, and P.M. Pardalos. A Par-
`allel GRASP for the Steiner Tree Problem in Graphs using a Hybrid Local
`Search Strategy. Journal of Global Optimization, 17:267-283, 2000.
`
`A parallel GRASP for the Steiner problem in graphs is described.
`See page 351.
`
`15.6 SOURCE CODE
`
`Several papers describe computer source code implementing GRASP. The