Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit

Postgraduate Thesis uoadl:3232625 63 Read counter

Unit:
Κατεύθυνση Υπολογιστικά Συστήματα: Λογισμικό και Υλικό
Πληροφορική
Deposit date:
2022-10-05
Year:
2022
Author:
Papatsoris Ioannis
Supervisors info:
Παναγιώτης Σταματόπουλος, Επίκουρος Καθηγητής, Τμήμα Πληροφορικής και Τηλεπικοινωνιών, Εθνικό και Καποδιστριακό Πανεπιστήμιο Αθηνών
Original Title:
Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit
Languages:
English
Translated title:
Extension and evaluation of the global cardinality constraints functionality of the Gecode open source toolkit
Summary:
Constraint Programming is an Artificial Intelligence methodology that aims to solve real
world problems in an efficient way. In this work, we extend the open source constraint solver Gecode by expanding its features concerning Global Constraints, specifically Global Cardinality Constraints. A Global Cardinality Constraint restricts the value occurrences among a collection of variables, to be between certain bounds. We develop the Global Cardinality Constraint With Costs, which is similar to the Global Cardinality Constraint and additionally associates a cost with each variable-value assignment, while further restricting the sum of the costs related to the assigned variable-value pairs to not exceed a given cost bound. Moreover, we add the Symmetric Global Cardinality Constraint, which is defined on Set variables and introduces additional restrictions on the cardinality of each set, aside from the value occurrences. We attempt to optimize their performance by experimenting with various different implementation choices, and finally we evaluate our constraints to discover under which conditions they are beneficial compared to decomposing them to multiple simpler ones.
Main subject category:
Technology - Computer science
Keywords:
constraint solver, open source, gecode, global constraint, global cardinality
Index:
Yes
Number of index pages:
4
Contains images:
Yes
Number of references:
38
Number of pages:
79
thesis.pdf (555 KB) Open in new window