Nogood Recording from Restarts

Lecoutre, Christophe; Sais, Lakhdar; Tabary, Sébastien; Vidal, Vincent

Nogood Recording from Restarts

Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary, Vincent Vidal

Download BibTeX Cite

Proceedings of the Twentieth International Joint Conference on Artificial Intelligence. Pages 131-135.

Abstract

In this paper, nogood recording is investigated within the randomization and restart framework. Our goal is to avoid the same situations to occur from one run to the next one. More precisely, nogoods are recorded when the current cutoff value is reached, i.e. before restarting the search algorithm. Such a set of nogoods is extracted from the last branch of the current search tree. Interestingly, the number of nogoods recorded before each new run is bounded by the length of the last branch of the search tree. As a consequence, the total number of recorded nogoods is polynomial in the number of restarts. Experiments over a wide range of CSP instances demonstrate the effectiveness of our approach.

Christophe Lecoutre, Lakhdar Sais, Sébastien Tabary, and Vincent Vidal. 2007. Nogood Recording from Restarts. In Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07. IJCAI, 131–135. https://ijcai.org/proceedings/2007/19

@inproceedings{ijcai2007p19,
  title     = {Nogood Recording from Restarts},
  author    = {Lecoutre, Christophe and Sais, Lakhdar and Tabary, Sébastien and Vidal, Vincent},
  booktitle = {Proceedings of the Twentieth International Joint Conference on
               Artificial Intelligence, {IJCAI-07}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Ramon López de Mántaras},
  pages     = {131--135},
  year      = {2007},
  url       = {https://ijcai.org/proceedings/2007/19},
}

TY  - CPAPER
TI  - Nogood Recording from Restarts
AU  - Lecoutre, Christophe
AU  - Sais, Lakhdar
AU  - Tabary, Sébastien
AU  - Vidal, Vincent
T2  - Proceedings of the Twentieth International Joint Conference on Artificial Intelligence, IJCAI-07
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2007
SP  - 131
EP  - 135
UR  - https://ijcai.org/proceedings/2007/19
ER  -