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
Jung08
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.
M. Sc. dissertation
Jean Christoph Jung
Pedro Barahona
FCT/UNL
-
http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf
Export formats
Jean Christoph Jung, Value Orderings based on Solution Counting, Pedro Barahona (superv.), FCT/UNL (http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf), October 2008.
<b>Jean Christoph Jung</b>, <u>Value Orderings based on Solution Counting</u>, <a href="/people/members/view.php?code=7e27bc13fad97e99cd21ea6914d55659" class="supervisor">Pedro Barahona</a> (superv.), FCT/UNL (<a href="http://centria.di.fct.unl.pt/~pb/papers/JungThesis.pdf" target="_blank">url</a>), October 2008.
@mastersthesis {Jung08, author = {Jean Christoph Jung}, title = {Value Orderings based on Solution Counting}, school = {FCT/UNL}, note = {Pedro Barahona (superv.); }, 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=72094c5c03582c6150dfb696a203adbf
/publications/view.php?code=Jung08
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