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
A heuristic based on domain-splitting nogoods from restarts
2012
BaptistaandAzevedo2012a
Inspired by Boolean Satisfiability Problems (SAT), Constraint Satisfaction Problems (CSP) are starting to use restart techniques associated with learning nogoods widely. Recent developments show how to learn nogoods from restarts and that these nogoods are of major importance when solving a CSP. Using a backtracking search algorithm, with domain-splitting branching, nogoods are learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named ds-nogoods, is still not proven to be effective in solving CSP. Nevertheless, information retained within dsnogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose and evaluate a variable selection heuristic based on ds-nogoods. Experimental results show that this allows some problems to be solved more efficiently.
In proceedings
Luís Baptista, Francisco Azevedo
Proceedings of the Second International Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012)
-
-
-
-
10 pages
-
-
-
-
Publication files
- click here to download - pdf 72 KB
Export formats
Luís Baptista and Francisco Azevedo, A heuristic based on domain-splitting nogoods from restarts, , Proceedings of the Second International Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012), Pag. 10 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>A heuristic based on domain-splitting nogoods from restarts</b>, <u>Proceedings of the Second International Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012)</u>, Pag. 10 pages, 2012.
@inproceedings {BaptistaandAzevedo2012a, author = {Lu\'{\i}s Baptista and Francisco Azevedo}, title = {A heuristic based on domain-splitting nogoods from restarts}, booktitle = {Proceedings of the Second International Workshop on the Cross-Fertilization Between CSP and SAT (CSPSAT 2012)}, pages = {10 pages}, abstract = {Inspired by Boolean Satisfiability Problems (SAT), Constraint Satisfaction Problems (CSP) are starting to use restart techniques associated with learning nogoods widely. Recent developments show how to learn nogoods from restarts and that these nogoods are of major importance when solving a CSP. Using a backtracking search algorithm, with domain-splitting branching, nogoods are learned from the last branch of the search tree, immediately before the restart occurs. This type of nogoods, named ds-nogoods, is still not proven to be effective in solving CSP. Nevertheless, information retained within dsnogoods can be used in heuristic decisions. Inspired by activity-based heuristics of SAT solvers, we propose and evaluate a variable selection heuristic based on ds-nogoods. Experimental results show that this allows some problems to be solved more efficiently.}, year = {2012}, }
Publication's urls
/publications/view.php?code=ac6e350f5b18c53d25176d4a80f4a5cb
/publications/view.php?code=BaptistaandAzevedo2012a
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