Probability Distribution of Solution Time in GRASP: An Experimental Investigation
Journal of HeuristicsPublished 1 May 2002
Renata M. Aiex, Maurício G. C. Resende, Celso C. Ribeiro
Citations150
SJR quartileQ2
SJR score0.46
SNIP1.01
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is concluded that the solution time to a sub-optimal target value fits a two-parameter exponential distribution and it is possible to approximately achieve linear speed-up by implementing GRASP in parallel.
Abstract
A GRASP (greedy randomized adaptive search procedure) is a multi-start metaheuristic for combinatorial optimization. We 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. We 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.
Keywords
Computer ScienceEngineering
Journal of Global OptimizationGreedy Randomized Adaptive Search Procedures
2,709 Citations1995Thomas A. Feo, Maurício G. C. Resende
This paper defines the various components comprising a GRASP and demonstrates, step by step, how to develop such heuristics for combinatorial optimization problems.
Kluwer Academic Publishers eBooksGreedy Randomized Adaptive Search Procedures
2,325 Citations2006Maurício G. C. Resende, Celso C. Ribeiro
BiometricsGraphical Methods for Data Analysis.
2,013 Citations1984N. I. Fisher, John M. Chambers +3 more
Operations Research LettersA probabilistic heuristic for a computationally difficult set covering problem
1,026 Citations1989Thomas A. Feo, Maurício G. C. Resende
An efficient probabilistic set covering heuristic is presented that provides the best known solutions to all other instances attempted to solve set covering problems that arise from Steiner triple systems.
Parallel ComputingRobust taboo search for the quadratic assignment problem
827 Citations1991Éric D. Taillard
An adaptation of taboo search to the quadratic assignment problem is discussed in this paper, which is efficient and robust, requiring less complexity and fewer parameters than earlier adaptations.
Noise strategies for improving local search
761 Citations1994Bart Selman, Henry Kautz +1 more
It is shown that mixed random walk is the superior strategy for solving MAX-SAT problems, and results demonstrating the effectiveness of local search with walk for solving circuit synthesis and circuit diagnosis problems are presented.
Operations ResearchA Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
409 Citations1994Thomas A. Feo, Maurício G. C. Resende +1 more
Computational results indicate that the heuristic frequently finds the optimal or expected optimal solution in a fraction of the time required by implementations of simulated annealing, tabu search, and an exact partial enumeration method.
European Journal of Operational ResearchQAPLIB-A quadratic assignment problem library
333 Citations1991Rainer E. Burkard, Stefan E. Karisch +1 more
A library of problem instances for the quadratic assignment problem is given and the examples are listed y authors in alphabetical order.
Operations research, computer science. Interface seriesGrasp: An Annotated Bibliography
285 Citations2002Paola Festa, Maurício G. C. Resende
This paper is an annotated bibliography of the GRASP literature from 1989 to 2001, covering a wide range of combinatorial optimization problems, ranging from scheduling and routing to drawing and turbine balancing.
Operations Research LettersSemi-greedy heuristics: An empirical study
202 Citations1987Julia Hart, Andrew W. Shogan
This work empirically compares the single use of a greedy heuristic with repeated use ofA semi-greedy heuristic in the context of vehicle routing.
Journal of HeuristicsParallel local search
162 Citations1995M.G.A. Verhoeven, Emile Aarts
A survey of parallel local search algorithms is presented in which the concepts that can be used to incorporate parallelism into local search are reviewed and the concepts of hyper neighborhood structures and distributed neighborhood structures are introduced.
INFORMS journal on computingImproved Constructive Multistart Strategies for the Quadratic Assignment Problem Using Adaptive Memory
158 Citations1999Charles Fleurent, Fred Glover
It is demonstrated by showing that a simple implementation of adaptive memory search principles, even when restricted to the constructive phases, can provide more effective multistart methods.
Journal of HeuristicsComputing Approximate Solutions of the Maximum Covering Problem with GRASP
93 Citations1998Maurício G. C. Resende
A greedy randomized adaptive search procedure (GRASP) for the maximum covering problem that finds good, though not necessarily optimum, placement configurations and shows that on large instances, the GRASP can produce facility placements that are nearly optimal.
Artificial IntelligenceTowards a characterisation of the behaviour of stochastic local search algorithms for SAT
92 Citations1999Holger H. Hoos, Thomas Stützle
It is shown that on hard Random-3-SAT problems, WalkSAT's run-time behaviour can be characterised by exponential distributions, which can be generalised to various SLS algorithms for SAT and to encoded problems from other domains.
Journal of Global OptimizationA Parallel Grasp for the Steiner Tree Problem in Graphs Using a Hybrid Local Search Strategy
91 Citations2000Simone L. Martins, Maurício G. C. Resende +2 more
A parallel greedy randomized adaptive search procedure (GRASP) for the Steiner problem in graphs and the main contribution of the parallel algorithm concerns the fact that larger speedups of the same order of the number of processors are obtained exactly for the most difficult problems.
Microprocessors and MicrosystemsParallel biased search for combinatorial optimization: genetic algorithms and TABU
90 Citations1992Roberto Battiti, Giampietro Tecchiolli
This paper considers some relatively general techniques that are paradigmatic of different parallel approaches, ranging from the concurrent execution of independent searches to a fully interacting ‘population’ of candidate solutions.
DIMACS series in discrete mathematics and theoretical computer scienceApproximate solution of weighted MAX-SAT problems using GRASP
81 Citations1997Maurício G. C. Resende, Leonidas Pitsoulis +1 more
A greedy randomized adaptive search procedure (GRASP) for computing approximate solutions of weighted MAX-SAT problems and computational experience indicates the suitability of GRASP for this class of problems.
ACM Transactions on Mathematical SoftwareAlgorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
81 Citations1996Maurício G. C. Resende, Pãnos M. Pardalos +1 more
A greedy, randomized, adaptive search procedure (GRASP) is used to produce approximate solutions to dense quadratic assignment problems, having at least one symmetric flow or distance matrix.
DIMACS series in discrete mathematics and theoretical computer scienceA GRASP for satisfiability
71 Citations1996Maurício G. C. Resende, Thomas A. Feo
NetworksA GRASP for graph planarization
65 Citations1997Maurício G. C. Resende, Celso C. Ribeiro
A greedy randomized adaptive search procedure for graph planarization problem, extending the heuristic of Goldschmidt and Takvorian and reviewing the basic concepts of GRASP: construction and local search algorithms.
A Parallel Grasp Implementation for the Quadratic Assignment Problem
60 Citations1995Pãnos M. Pardalos, Leonidas Pitsoulis +1 more
A parallel implementation of a Greedy Randomized Adaptive Search Procedure (GRASP) for finding approximate solutions to the quadratic assignment problem using an MIMD parallel computer and achieves an average speedup that is almost linear in the number of processors.
Lecture notes in computer scienceA parallel GRASP for the Steiner problem in graphs
58 Citations1998Simone L. Martins, Celso C. Ribeiro +1 more
A parallel GRASP for the Steiner problem in graphs is described, which was implemented using the Message Passing Interface library on an IBM SP2 machine in order to improve load balancing.
INFORMS Journal on ComputingA Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
44 Citations1991Lawrence Osborne, Billy E. Gillett
A new approach to the directed version of this problem is made by applying the ideas of statistical mechanics through the use of the method of simulated annealing to suggest near-optimal answers appear according to an approximately exponential distribution and that they can be obtained in polynomial time.
Discrete Applied MathematicsFortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP
44 Citations2000Maurício G. C. Resende, Leonidas Pitsoulis +1 more
Fortran subroutines for computing approximate solutions to the weighted MAX-SAT problem using a greedy randomized adaptive search procedure (GRASP).
Lecture notes in computer scienceA parallel GRASP for MAX-SAT problems
44 Citations1996Pãnos M. Pardalos, Leonidas Pitsoulis +1 more
This paper presents a parallel greedy randomized adaptive search procedure (GRASP) for solving MAX-SAT problems and experimental results indicate that almost linear speedup is achieved.
The IMA volumes in mathematics and its applicationsA Parallel Grasp for the Data Association Multidimensional Assignment Problem
39 Citations1999Robert Murphey, Pãnos M. Pardalos +1 more
A Greedy Randomized Adaptive Search Procedure (GRASP) has been developed and computational results show good quality solutions can be obtained and the efficiency of the GRASP can be easily improved by parallelization of the code in the MPI environment.
ACM Transactions on Mathematical SoftwareAlgorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP
38 Citations1998Maurício G. C. Resende, Thomas A. Feo +1 more
ACM Transactions on Mathematical SoftwareAlgorithm 769
36 Citations1997Pãnos M. Pardalos, Leonidas Pitsoulis +1 more
NetworksAn efficient graph planarization two‐phase heuristic
36 Citations1994Olivier Goldschmidt, Alexan Takvorian
A two-phase heuristic for solving the planarization problem by devising a clever ordering of the vertices of the graph on a single line and the second phase tries to find the maximal number of nonintersecting edges that can be drawn above or below this line is presented.
ACM Transactions on Mathematical SoftwareAlgorithm 797
28 Citations1999Celso C. Ribeiro, Maurício G. C. Resende
Parallel ComputingSlow annealing versus multiple fast annealing runs — an empirical investigation
24 Citations1990Nigel Dodd
It is shown that, for a considerable range of parallelisation, the probability of finding the global minimum is largely unchanged.
MetaheuristicsA Probabilistic Analysis of Local Search
21 Citations1996ten Hmm Huub Eikelder, Mga Marco Verhoeven +2 more
A model which allows us to compute the required number of steps and the distribution of final solutions found by a best improvement algorithm is given and is empirically validated for a restricted version of the 2-opt neighborhood.
TU/e Research Portal (Eindhoven University of Technology)A probabilistic analysis of local search
3 Citations1996Eikelder, HMM Huub ten, Verhoeven, MGA Marco +2 more