Statistical Regimes Across Constrainedness Regions

Carla Gomes 1 Cèsar Fernández 2 Bart Selman 1 Christian Bessière 3
3 COCONUT - Agents, Apprentissage, Contraintes
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
Abstract : Much progress has been made in terms of boosting the effectiveness of backtrack style search methods. In addition, during the last decade, a much better understanding of problem hardness, typical case complexity, and backtrack search behavior has been obtained. One example of a recent insight into backtrack search concerns so-called heavy-tailed behavior in randomized versions of backtrack search. Such heavy-tails explain the large variations in runtime often observed in practice. However, heavy-tailed behavior does certainly not occur on all instances. This has led to a need for a more precise characterization of when heavy-tailedness does and when it does not occur in backtrack search. In this paper, we provide such a characterization. We identify different statistical regimes of the tail of the runtime distributions of random-ized backtrack search methods and show how they are correlated with the "sophistication" of the search procedure combined with the inherent hardness of the instances. We also show that the runtime distribution regime is highly correlated with the distribution of the depth of inconsistent subtrees discovered during the search. In particular, we show that an exponential distribution of the depth of inconsistent subtrees combined with a search space that grows exponentially with the depth of the inconsistent subtrees implies heavy-tailed behavior.
Document type :
Conference papers
Complete list of metadatas

Cited literature [17 references]  Display  Hide  Download

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00108914
Contributor : Christine Carvalho de Matos <>
Submitted on : Wednesday, August 28, 2019 - 3:14:53 PM
Last modification on : Friday, September 20, 2019 - 11:32:00 AM

File

cp04-stat.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Carla Gomes, Cèsar Fernández, Bart Selman, Christian Bessière. Statistical Regimes Across Constrainedness Regions. CP: Principles and Practice of Constraint Programming, Sep 2004, Toronto, Canada. pp.32-46, ⟨10.1007/978-3-540-30201-8_6⟩. ⟨lirmm-00108914⟩

Share

Metrics

Record views

92

Files downloads

13