Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms

DOI10.1007/s10898-011-9769-zzbMath1259.90115MaRDI QIDQ693145

Isabel Rosseti, Reinaldo Vallejos, Celso Carneiro Ribeiro

Publication date: 7 December 2012

Published in: Journal of Global Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10898-011-9769-z

zbMATH Keywords

metaheuristics; GRASP; stochastic local search; path-relinking; run time distributions; time-to-target plots

Mathematics Subject Classification ID

90C59: Approximation methods and heuristics in mathematical programming

90C27: Combinatorial optimization

Related Items

A distributed and hierarchical strategy for autonomic grid-enabled cooperative metaheuristics with applications, Using sequential runtime distributions for the parallel speedup prediction of SAT local search, A diversified tabu search approach for the open-pit mine production scheduling problem with metal uncertainty

Uses Software

• PERL
• GRASP_QAP
• TTTPLOTS
• Algorithm 797
• Algorithm 787

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Routing and wavelength assignment by partition colouring
• Computing approximate solutions of the maximum covering problem with GRASP
• Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
• Greedy randomized adaptive search procedures
• Probability distribution of solution time in GRASP: an experimental investigation
• Parallel local search
• Fortran subroutines for computing approximate solutions of weighted MAX-SAT problems using GRASP
• A hybrid heuristic for the diameter constrained minimum spanning tree problem
• TTT plots: a perl program to create time-to-target plots
• Slow annealing versus multiple fast annealing runs - an empirical investigation
• Local search with perturbations for the prize-collecting Steiner tree problem in graphs
• GRASP with Path Relinking for Three-Index Assignment
• Applications of the DM‐GRASP heuristic: a survey
• Algorithm 787: Fortran subroutines for approximate solution of maximum independent set problems using GRASP
• An Algorithmic Approach to Network Location Problems. I: Thep-Centers
• A Comparison of Two Simulated Annealing Algorithms Applied to the Directed Steiner Problem on Networks
• A Greedy Randomized Adaptive Search Procedure for Maximum Independent Set
• Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
• The 2-path network problem
• Algorithm 797