Back to first pageBack to first page Centre for Artificial Intelligence of UNL
Browse our site
You are here:

Publication details

Go back
Publication details
Main information
Using nogoods information from restarts in domain-splitting search
2012
BaptistaandAzevedo2012b
The use of restart techniques associated with learning nogoods in solving Constraint Satisfaction Problems (CSPs) is starting to be considered of major importance for backtrack search algorithms. In a backtracking search algorithm, with domain-splitting branching, nogoods can be learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named domain-splitting (ds) nogoods, is still not proven to be effective in solving CSP. However, information retained within ds-nogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose to include ds-nogood information in the heuristic decision. Experimental results show that this allows some problems to be solved more efficiently.
In proceedings
Luís Baptista, Francisco Azevedo
Thibaut Feydy, Geoffrey Chu
Proceedings of Nogood Learning and Constraint Programming Workshop (NGL 2012)
-
-
-
-
9 pages
-
-
-
-
Publication files
- click here to download - pdf 62 KB
Export formats
Luís Baptista and Francisco Azevedo, Using nogoods information from restarts in domain-splitting search, in: Thibaut Feydy and Geoffrey Chu (eds), Proceedings of Nogood Learning and Constraint Programming Workshop (NGL 2012), Pag. 9 pages, 2012.
<a href="/people/members/view.php?code=0ec710f4aed9065fb0a84758926e4bc2" class="author">Luís Baptista</a> and <a href="/people/members/view.php?code=f260a0cb31e0c92628691f7473b16e98" class="author">Francisco Azevedo</a>, <b>Using nogoods information from restarts in domain-splitting search</b>, in: Thibaut Feydy and Geoffrey Chu (eds), <u>Proceedings of Nogood Learning and Constraint Programming Workshop (NGL 2012)</u>, Pag. 9 pages, 2012.
@inproceedings {BaptistaandAzevedo2012b, author = {Lu\'{\i}s Baptista and Francisco Azevedo}, editor = {Thibaut Feydy and Geoffrey Chu}, title = {Using nogoods information from restarts in domain-splitting search}, booktitle = {Proceedings of Nogood Learning and Constraint Programming Workshop (NGL 2012)}, pages = {9 pages}, abstract = {The use of restart techniques associated with learning nogoods in solving Constraint Satisfaction Problems (CSPs) is starting to be considered of major importance for backtrack search algorithms. In a backtracking search algorithm, with domain-splitting branching, nogoods can be learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named domain-splitting (ds) nogoods, is still not proven to be effective in solving CSP. However, information retained within ds-nogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose to include ds-nogood information in the heuristic decision. Experimental results show that this allows some problems to be solved more efficiently.}, keywords = {constraint, restarts, heuristic, nogoods, domain-splitting}, year = {2012}, }
Publication's urls
/publications/view.php?code=90374e3c037c66c61e881b82a437a9ef
/publications/view.php?code=BaptistaandAzevedo2012b
Go back
Centre for Artificial Intelligence of UNL
Departamento de Informática, FCT/UNL
Quinta da Torre 2829-516 CAPARICA - Portugal
Tel. (+351) 21 294 8536 FAX (+351) 21 294 8541

Fundacao_FCT