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

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

Reinaldo Vallejos, Isabel Rosseti, 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

metaheuristicsGRASPstochastic local searchpath-relinkingrun time distributionstime-to-target plots

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27)

Related Items

A hybrid biased random key genetic algorithm for the quadratic assignment problem, A biased random-key genetic algorithm to maximize the number of accepted lightpaths in WDM optical networks, A diversified tabu search approach for the open-pit mine production scheduling problem with metal uncertainty, Extending time‐to‐target plots to multiple instances, Using sequential runtime distributions for the parallel speedup prediction of SAT local search, Effective metaheuristic algorithms for the minimum differential dispersion problem, A distributed and hierarchical strategy for autonomic grid-enabled cooperative metaheuristics with applications, \texttt{tttplots-compare}: a Perl program to compare time-to-target plots or general runtime distributions of randomized algorithms, On the problem of minimizing the cost with optical devices in Wavelength Division Multiplexing optical networks: complexity analysis, mathematical formulation and improved heuristics, Hybridizations of GRASP with path relinking for the far from most string problem, Large-scale parallelism for constraint-based local search: the costas array case study, Solving the traveling delivery person problem with limited computational time

Uses Software

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

Cites Work

• 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
• A GRASP for graph planarization
• Algorithm 754: Fortran subroutines for approximate solution of dense quadratic assignment problems using GRASP
• The 2-path network problem
• Algorithm 797