Back to search

University of Western Macedonia

Techniques for learning constraint satisfaction problems with applications in telecommunications

Abstract

dc:description

Constraint Programming (CP) is considered as one of the foremost paradigms for solving combinatorial problems in Artificial Intelligence. However, there are still challenges to be faced in order to make CP technology even more widely used, with the main bottleneck being the expertise required for the modelling of the problem. Constraint acquisition systems can assist non-expert users to model their problems as constraint networks by classifying examples as positive or negative. Two important bottlenecks of the acquisition process, where the state-of-the-art algorithms encounter problems, are the large number of queries required, and the high cpu times needed to generate queries, especially near convergence. This problem is even bigger when the problem contains certain classes of constraints, like linear constraints, as there are no methods to handle specific classes of constraints efficiently. In addition, there are some significant shortcomings regarding the applicability of constraint acquisition systems in real problems, such as the assumption that the user can answer all queries posted with absolute certainty and the fact that there is no active constraint acquisition method for learning soft constraints, to capture preferences of the user in optimization problems. In this dissertation, we propose algorithmic and heuristic methods to deal with the above issues. We first propose an algorithm, called MQuAcq, blending ideas from state-of-the-art algorithms, alleviating to a large extent the above issues regarding the number of queries and cpu time. We also present a technique that boosts the performance of constraint acquisition by reducing the number of queries significantly. Then, we turn our attention to query generation, which is a significant but rather overlooked part of the acquisition process. We describe query generation in detail and we propose heuristics for improving its efficiency, alleviating some important problems of constraint acquisition systems, like premature convergence. Next, we improve MQuaAcq by proposing MQuAcq-2, a new algorithm that exploits the structure of the learned problem in the learning process and is by far faster in large problems than MQuAcq. We then focus on the important class of linear inequality constraints and propose a method to learn them efficiently, showing that specific handling of certain constraints can speed up the acquisition process significantly. We also present two algorithms for handling cases where the user cannot answer all queries posted with absolute certainty. We focus on the case where the user is uncertain whether some assignments are solutions or not of the problem, and we give methods that allow the user to omit some queries. Importantly, our second algorithm can not only learn (a part of) the target network, but also the constraints that cause the user’s uncertainty. Finally, we deal with the problem of learning soft constraints in the context of Max-CSPs via active constraint acquisition, for the first time. We first introduce a new type of queries in Constraint Acquisition, namely (partial) preference queries, and then we propose a novel algorithm that can find the soft constraints that represent the preferences of the user, driven by the user’s answers. We present experimental results and detailed theoretical analysis of all the proposed algorithms. Our proposed methods are shown to boost the performance of active constraint acquisition systems significantly in the most important metrics. Importantly, in this dissertation we have also alleviated a lot of the issues regarding the applicability of constraint acquisition systems in real problems. It is now not assumed that the user is able to answer all the queries posted, and also possible preferences can be captured and modelled by constraint acquisition. Dealing with cases that can appear in real world applications for the first time, our work brings closer the utilization of active constraint acquisition in practice, which is now the next step.

Degree

thesis:*
Grantor dc:publisher
University of Western Macedonia
Year dc:date
2021

Author and committee

dc:creator, dc:contributor.*
Authors dc:creator
  • Tsouros, Dimosthenis
  • Τσούρος, Δημοσθένης

Subjects

dc:subject × 18

Rights

Language dc:language
eng

Identifiers

dc:identifier.*
Identifier
10.12681/eadd/51616

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

Tsouros, Dimosthenis; Τσούρος, Δημοσθένης. Techniques for learning constraint satisfaction problems with applications in telecommunications. University of Western Macedonia, 2021. http://hdl.handle.net/10442/hedi/51616