Back to search

National and Kapodistrian University of Athens

Constraint programming: algorithms and systems

Abstract

dc:description

Constraint Programming aims at the easy declaration and fast resolution of Constraint Satisfaction Problems (CSPs) like course scheduling, radio link frequency assignment, etc. To solve the problems, Constraint Programming is based on search methods and constraint propagation. This dissertation contributes on both. Specifically: (i) We develop novel search methods that are based on new heuristics. These new heuristics implement the gradual randomization of deterministic heuristics. We create hybrid heuristics that exploit the advantages of both deterministic and random heuristics. (ii) We demonstrate how the MapReduce framework can be used for speeding up and distributing the search of a CSP solution to all the available solvers-workers. (iii) We highlight the advantages of relaxed constraint propagation levels like bounds consistency in comparison to higher levels like arc consistency. We propose new relaxed constraint propagation levels, and we compare their performance to higher propagation levels, both in theory and practice. We answer the question about when it is worth to employ relaxed constraint propagation levels. Our contributions were tested using mostly CSPs that occur in the real world and a wide range of CSPs included in official Constraint Programming solvers competitions. We used Naxos Solver as a practical open-source Constraint Programming solver to conduct our experiments.

Degree

thesis:*
Grantor dc:publisher
National and Kapodistrian University of Athens
Year dc:date
2022

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Pothitos, Nikolaos
  • Ποθητός, Νικόλαος

Subjects

dc:subject × 19

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/52375

Chain of custody

source
Harvested from
Greek National Archive of PhD Theses
Base URL
phdtheses.ekt.gr/eadd_oai/request
Last updated
2026-11-18
Source record
OAI-PMH GetRecord
citation

Pothitos, Nikolaos; Ποθητός, Νικόλαος. Constraint programming: algorithms and systems. National and Kapodistrian University of Athens, 2022. http://hdl.handle.net/10442/hedi/52375