Using sequential runtime distributions for the parallel speedup prediction of SAT local search

DOI10.1017/S1471068413000392zbMath1286.68405MaRDI QIDQ5398300

Charlotte Truchet, Philippe Codognet, Alejandro Arbelaez

Publication date: 27 February 2014

Published in: Theory and Practice of Logic Programming (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1017/s1471068413000392

zbMATH Keywords

local search; parallelism; statistical analysis; SAT; runtime distributions

Mathematics Subject Classification ID

68T20: Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.)

68N17: Logic programming

Related Items

Large-scale parallelism for constraint-based local search: the costas array case study, Combinatorial search from an energy perspective

Uses Software

• TTTPLOTS

Cites Work

• Unnamed Item
• An overview of parallel SAT solving
• Restart strategies in optimization: parallel and serial cases
• Learning and intelligent optimization. 5th international conference, LION 5, Rome, Italy, January 17--21, 2011. Selected papers
• Exploiting run time distributions to compare sequential and parallel stochastic local search algorithms
• On the satisfiability threshold and clustering of solutions of random 3-SAT formulas
• Towards a characterisation of the behaviour of stochastic local search algorithms for SAT
• Probability distribution of solution time in GRASP: an experimental investigation
• Parallel local search
• TTT plots: a perl program to create time-to-target plots
• Explicit expressions for moments of order statistics
• Applied parallel computing: industrial computation and optimization. Third international workshop, PARA '96, Lyngby, Denmark, August 18--21, 1996. Proceedings
• Order Statistics