Chisca, Danuta Sorina
(2019)

*Investigation of Matching Problems using Constraint Programming and Optimisation Methods*, [Dissertation thesis], Alma Mater Studiorum Università di Bologna.
Dottorato di ricerca in

Computer science and engineering, 32 Ciclo. DOI 10.6092/unibo/amsdottorato/9177.

Documenti full-text disponibili:

## Abstract

This thesis focuses on matching under ordinal preferences, i.e. problems where agents may be required to list other agents that they find acceptable in order of preference. In particular, we focus on two main cases: the popular matching and the kidney exchange problem. These problems are important in practice and in this thesis we develop novel algorithms and techniques to solve them as combinatorial optimisation problems. The first part of the thesis focuses on one-sided matching on a bipartite graph, specifically the popular matching. When the participants express their preferences in an ordinal order, one might want to guarantee that no two applicants are inclined to form a coalition in order to maximise their welfare, thus finding a stable matching is needed. Popularity is a concept that offers an attractive trade- off between these two notions. In particular, we examine the popular matching in the context of constraint programming using global constraints. We discuss the possibility to find a popular matching even for the instances that does not admit one.
The second part of the thesis focuses on non-bipartite graphs, i.e. the kidney exchange problem. Kidney transplant is the most effective treatment to cure end-stage renal disease, affecting one in every thousand European citizen. Motivated by the observation that the kidney exchange is inherently a stochastic online problem, first, we give a stochastic online method, which provides an expected value estimation that is correct within the limit of sampling errors. Second, we show that by taking into consideration a probabilistic model of future arrivals and drop-offs, we can get reduce sampling scenarios, and we can even construct a sampling-free probabilistic model, called the Abstract Exchange Graph (AEG). A final contribution of this thesis is related to finding robust solutions when uncertainty occurs. Uncertainty is inherent to most real world problems.

Abstract

This thesis focuses on matching under ordinal preferences, i.e. problems where agents may be required to list other agents that they find acceptable in order of preference. In particular, we focus on two main cases: the popular matching and the kidney exchange problem. These problems are important in practice and in this thesis we develop novel algorithms and techniques to solve them as combinatorial optimisation problems. The first part of the thesis focuses on one-sided matching on a bipartite graph, specifically the popular matching. When the participants express their preferences in an ordinal order, one might want to guarantee that no two applicants are inclined to form a coalition in order to maximise their welfare, thus finding a stable matching is needed. Popularity is a concept that offers an attractive trade- off between these two notions. In particular, we examine the popular matching in the context of constraint programming using global constraints. We discuss the possibility to find a popular matching even for the instances that does not admit one.
The second part of the thesis focuses on non-bipartite graphs, i.e. the kidney exchange problem. Kidney transplant is the most effective treatment to cure end-stage renal disease, affecting one in every thousand European citizen. Motivated by the observation that the kidney exchange is inherently a stochastic online problem, first, we give a stochastic online method, which provides an expected value estimation that is correct within the limit of sampling errors. Second, we show that by taking into consideration a probabilistic model of future arrivals and drop-offs, we can get reduce sampling scenarios, and we can even construct a sampling-free probabilistic model, called the Abstract Exchange Graph (AEG). A final contribution of this thesis is related to finding robust solutions when uncertainty occurs. Uncertainty is inherent to most real world problems.

Tipologia del documento

Tesi di dottorato

Autore

Chisca, Danuta Sorina

Supervisore

Dottorato di ricerca

Ciclo

32

Coordinatore

Settore disciplinare

Settore concorsuale

Parole chiave

Kidneu Echange Problem, Stochastic Problems, Optimisation Problems, Constraint Programming

URN:NBN

DOI

10.6092/unibo/amsdottorato/9177

Data di discussione

10 Dicembre 2019

URI

## Altri metadati

Tipologia del documento

Tesi di dottorato

Autore

Chisca, Danuta Sorina

Supervisore

Dottorato di ricerca

Ciclo

32

Coordinatore

Settore disciplinare

Settore concorsuale

Parole chiave

Kidneu Echange Problem, Stochastic Problems, Optimisation Problems, Constraint Programming

URN:NBN

DOI

10.6092/unibo/amsdottorato/9177

Data di discussione

10 Dicembre 2019

URI

## Statistica sui download

Gestione del documento: