Back to search

University of the Aegean

Adaptive strategies for solving contraint satisfaction problems

Abstract

dc:description

A 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

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/26336

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

Balafoutis, Thanasis; Μπαλαφούτης, Αθανάσιος. Adaptive strategies for solving contraint satisfaction problems. University of the Aegean, 2011. http://hdl.handle.net/10442/hedi/26336