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
Value Orderings based on Solution Counting
October 2008
Jung09
A key issue for backtrack search in constraint satisfaction problems is the selection of a good value, but little effort has been dedicated to this topic. Another important aspect of constraint programming, besides finding them, is counting solutions either in the whole problem or in single constraints. Recent works give first ideas how to exploit the advances in solution counting in designing better value ordering heuristics. With this thesis we want to elaborate these in more depth. First, we provide a novel approach for solution counting in individual constraints, which results in a different view on counting in regular constraints and in counting algorithms for extensional and grammar constraints. Second, we consider the problem of a good value selection from different perspectives and derive several value ordering heuristics based on solution counting. We evaluate both the counting and the heuristics by solving roster problems modelled with grammar and regular constraints.
In proceedings
Jean Christoph Jung
M.Sc. Thesis
-
-
-
-
-
-
-
-
http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf
Export formats
Jean Christoph Jung, Value Orderings based on Solution Counting, , M.Sc. Thesis, (http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf), October 2008.
Jean Christoph Jung, <b>Value Orderings based on Solution Counting</b>, <u>M.Sc. Thesis</u>, (<a href="http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf" target="_blank">url</a>), October 2008.
@inproceedings {Jung09, author = {Jean Christoph Jung}, title = {Value Orderings based on Solution Counting}, booktitle = {M.Sc. Thesis}, url = {http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf}, abstract = {A key issue for backtrack search in constraint satisfaction problems is the selection of a good value, but little effort has been dedicated to this topic. Another important aspect of constraint programming, besides finding them, is counting solutions either in the whole problem or in single constraints. Recent works give first ideas how to exploit the advances in solution counting in designing better value ordering heuristics. With this thesis we want to elaborate these in more depth. First, we provide a novel approach for solution counting in individual constraints, which results in a different view on counting in regular constraints and in counting algorithms for extensional and grammar constraints. Second, we consider the problem of a good value selection from different perspectives and derive several value ordering heuristics based on solution counting. We evaluate both the counting and the heuristics by solving roster problems modelled with grammar and regular constraints.}, month = {October}, year = {2008}, }
Publication's urls
/publications/view.php?code=5ec560a6b7f679de060781396cd01cbf
/publications/view.php?code=Jung09
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