University of Western Macedonia
Efficient algorithms for strong local consistencies and adaptive techniques in constraint satisfaction problems
Abstract
dc:descriptionConstraint Programming (CP) is a successful technology for solving a wide range of problemsin business and industry which require the satisfaction of a set of complex constraints.Examples include product configuration, resource allocation, transportation, andscheduling. As the simultaneous satisfaction of different constraints is intractable in general,problems can become very difficult to solve as their size increases. CP has thusdeveloped various techniques to tackle this inherent problem. Enforcing a local consistencyproperty is one of the most important such techniques.Bounds Consistency (BC) and Generalised Arc Consistency (GAC) are the two mostwidely studied and used local consistencies in CP solvers. While there exist strongerlocal consistency (SLC) properties, their usage is limited due to their prohibitive cost.Examples are max Restricted Path Consistency (maxRPC) and max Restricted PairWiseConsistency (maxRPWC).In our research, we propose efficient filtering algorithms for enforcing SLCs. In particular,we propose new algorithms for maxRPC and maxRPWC that advance the existingalgorithms (theoretically and practically). We also propose algorithms that achieve weakerconsistencies with a lower cost. In addition, we have extended the recent algorithms fromthe family of Simple Tabular Reduction (STR) to achieve a higher-order local consistencyproperty. Experiments demonstrate that these algorithms can significantly outperformvarious state-ot the-art (G)AC algorithms, even by orders of magnitude, and thus can becomevery useful additions to the propagation techniques that CP solvers currently apply.Additionally, we have introduced and defined a new strong Bounds Consistency, calledPWBC, as well as a polynomial filtering algorithm based on this consistency for the importantclass of linear inequalities. Theoretical and experimental results demonstrate thepotential of SLCs that reason on bounds.Finally, since SLCs may still be too expensive to maintain during search in manyproblems, we have suggested ways to interleave them with weaker propagation methodssuch as GAC. We have proposed fully automated heuristics that can dynamically selectthe most appropriate filtering algorithm. All algorithms are incorporated in an adaptivefiltering scheme to further tackle the inherent difficulty of constraint satisfaction, resultingin a more robust constraint solver. Overall, this research proposes filtering algorithms andadaptive techniques that exploit the filtering power offered by SLCs in an efficient way, inorder to increase the efficacy of CP solvers.
Degree
thesis:*- Grantor dc:publisher
- University of Western Macedonia
- Year dc:date
- 2013
Author and committee
dc:creator, dc:contributor.*- Authors dc:creator
-
- Paparrizou, Anastasia
- Παπαρρίζου, Αναστασία
Subjects
dc:subject × 21- Ισχυρές τοπικές συνέπειες
- Προσαρμοστικές τεχνικές
- Ισχυρή συνέπεια ορίων
- Τεχνικές διάδοσης περιορισμών
- Αλγόριθμοι φιλτραρίσματος
- Προβλήματα ικανοποίησης περιορισμών
- Strong local consistencies
- Higher-order consistencies
- Adaptive techniques
- Strong bounds consistency
- Table constraints
- Filtering algorithms
- Constraint satisfaction problems
- Φυσικές Επιστήμες
- Επιστήμη Ηλεκτρονικών Υπολογιστών και Πληροφορική
- Επιστήμες Μηχανικού και Τεχνολογία
- Επιστήμη Ηλεκτρολόγου Μηχανικού, Ηλεκτρονικού Μηχανικού, Μηχανικού Η/Υ
- 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/31791