University of the Aegean
Adaptive strategies for solving contraint satisfaction problems
Abstract
dc:descriptionA major challenge in constraint programming is to develop efficient generic approaches to solve instances of the constraint satisfaction problem (CSP). In recent years adaptive approaches for solving CSPs have attracted the interest of many researchers. General speaking a strategy that uses the results of its own search experience to modify its subsequent behavior does adaptive search In this dissertation we explore adaptive strategies for backtracking search on various levels. First, we investigate adaptive search guiding heuristics for ordering variables in CSPs. These adaptive heuristics learn and use information from every node explored in the search tree whereas traditional static and dynamic heuristics only use information about the initial and current nodes. We then perform a wide empirical evaluation of the proposed variable ordering heuristics and compare them with the current state of the art variable ordering strategies. Concerning constraint propagation which is used as an inference mechanism in order to simplify a problem so as to make it easier to solve we explore adaptive strategies for ordering the different revisions performed when enforcing arc consistency algorithms. Next we propose adaptive branching heuristics for splitting the search tree. The application of these heuristics results in an adaptive branching scheme. Experiments with instantiations of the proposed generic heuristics confirm that search with adaptive branching outperforms search with a fixed branching scheme on a wide range of problem. Finally we propose a new a generic approach for branching where the variable’s domains are grouped into sets by using the scores assigned to values by a value ordering heuristic and a clustering algorithm from machine learning. In general this dissertation contributes to the design and implementation of adaptive and autonomous constraint solvers that have the ability to advantageously modify modelers decisions that typically in mainstream CP solvers are taken prior to search.
Degree
thesis:*- Grantor dc:publisher
- University of the Aegean
- Year dc:date
- 2011
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Balafoutis, Thanasis
- Μπαλαφούτης, Αθανάσιος
Subjects
dc:subject × 22- Προβλήματα ικανοποίησης περιορισμών
- Προσαρμοστικές στρατηγικές
- Ευρετικές τεχνικές ταξινόμησης μεταβλητών
- Συνέπεια τόξου
- Τεχνικές διακλάδωσης δέντρου αναζήτησης
- Αυτόνομοι επιλυτές προβλημάτων ικανοποίησης περιορισμών
- Constrain satisfaction problems
- Adaptive strategies
- Variable ordering heuristics
- Arc consistency
- Revision ordering
- Branching schemes
- Set branching
- Autonomous and adaptive constrain solvers
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- Natural Sciences
- Computer and Information Sciences
- Engineering and Technology
- Electrical Engineering, Electronic Engineering, Information Engineering
Rights
- Language dc:language
- eng
Identifiers
dc:identifier.*- Identifier
- 10.12681/eadd/26336