Cookies Policy
The website need some cookies and similar means to function. If you permit us, we will use those means to collect data on your visits for aggregated statistics to improve our service. Find out More
Accept Reject
  • Menu
About

About

I was born in Russia in the city called Irkutsk, located in the middle of Siberia. In 2006 I graduated from the Institute of Mathematics Economics and Informatics of Irkutsk State University with the Master Degree in Applied Mathematics. Then I had started my post-graduate study at the Institute of System Dynamics and Control Theory of Siberian Branch of the Russian Academy of Sciences, Irkutsk, where in December, 2010, I have successfully defended my PhD thesis in Operations Research. In November, 2011 I have moved to Portugal and joined the research activities at INESC Porto under the project on Kidney Exchange Programs. Currently I continue research within this application of operations research under FCT post-doc grant.

My research interests are in the field of combinatorial optimization: modelling, development the methods for solving the problems such as branch and cut and price methods, cutting plane methods, column generation. As to applications I have worked on kidney exchange problem, location problems, clustering problem, PMU placement problem.

Interest
Topics
Details

Details

  • Name

    Xenia Klimentova
  • Role

    Senior Researcher
  • Since

    03rd November 2011
005
Publications

2024

Performance evaluation of national and international kidney exchange programmes with the ENCKEP simulator

Authors
Druzsin, K; Biró, P; Klimentova, X; Fleiner, R;

Publication
CENTRAL EUROPEAN JOURNAL OF OPERATIONS RESEARCH

Abstract
In this paper we present simulations for international kidney exchange programmes (KEPs). KEPs are organised in more than ten countries in Europe to facilitate the exchanges of immunologically incompatible donors. The matching runs are typically conducted in every three months for finding optimal exchanges using hierarchical optimisation with integer programming techniques. In recent years several European countries started to organise international exchanges using different collaboration policies. In this paper we conduct simulations for estimating the benefits of such collaborations with a simulator developed by the team of the ENCKEP COST Action. We conduct our simulations on generated datasets mimicking the practice of the three largest KEPs in Europe, the UK, Spanish and the Dutch programmes. Our main performance measure is the number of transplants compared to the number of registrations to the KEP pools over a 5-year period, however, as a novelty we also analyse how the optimisation criteria play a role in the lexicographic and weighted optimisation policies for these countries. Besides analysing the performances on a single instance, we also conduct large number of simulations to obtain robust findings on the performance of specific national programmes and on the possible benefits of international collaborations.

2023

Novel integer programming models for the stable kidney exchange problem

Authors
Klimentova, X; Biro, P; Viana, A; Costa, V; Pedroso, JP;

Publication
EUROPEAN JOURNAL OF OPERATIONAL RESEARCH

Abstract
Kidney exchange programs (KEPs) represent an additional possibility of transplant for patients suffering from end-stage kidney disease. If a patient has a willing living donor with whom the patient is not compatible, the pair recipient-donor can join a pool of incompatible pairs and, if compatibility between recipient and donor in two or more pairs exists, organs can be exchanged between them. The problem can be modelled as an integer program that in general aims at finding the pairs that should be selected for transplant such that maximum number of transplants is performed. In this paper, we consider that for each recipient there may exist a preference order over the organs that he/she can receive, since a recipient may be compatible with several donors but the level of compatibility with the recipient might vary for different donors. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists, i.e., there is no cycle such that all recipients prefer the donor in that cycle rather than that in the exchange. For this purpose we propose four novel integer programming models based on the well-known edge and cycle formulations, and also on the position-indexed formulation. These formulations are adjusted for both finding stable and strongly stable exchanges under strict preferences and for the case when ties in preferences may exist. Further-more, we study a situation when the stability requirement can be relaxed by addressing the trade-off between maximum cardinality versus number of blocking cycles allowed in a solution. The effectiveness of the proposed models is assessed through extensive computational experiments on a wide set of in-stances. Results show that the cycle-edge and position-indexed formulations outperform the other two formulations. Another important practical outcome is that targeting strongly stable solutions has a much higher negative impact on the number of transplants (with an average reduction of up to 20% for the bigger instances), when compared to stable solutions.

2023

Shapley-Scarf Housing Markets: Respecting Improvement, Integer Programming, and Kidney Exchange

Authors
Biró, P; Klijn, F; Klimentova, X; Viana, A;

Publication
MATHEMATICS OF OPERATIONS RESEARCH

Abstract
In a housing market of Shapley and Scarf, each agent is endowed with one indivisible object and has preferences over all objects. An allocation of the objects is in the (strong) core if there exists no (weakly) blocking coalition. We show that, for strict preferences, the unique strong core allocation respects improvement-if an agent's object becomes more desirable for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We extend this result to weak preferences for both the strong core (conditional on nonemptiness) and the set of competitive allocations (using probabilistic allocations and stochastic dominance). There are no counterparts of the latter two results in the two-sided matching literature. We provide examples to show how our results break down when there is a bound on the length of exchange cycles. Respecting improvements is an important property for applications of the housing markets model, such as kidney exchange: it incentivizes each patient to bring the best possible set of donors to the market. We conduct computer simulations using markets that resemble the pools of kidney exchange programs. We compare the game-theoretical solutions with current techniques (maximum size and maximum weight allocations) in terms of violations of the respecting improvement property. We find that game-theoretical solutions fare much better at respecting improvements even when exchange cycles are bounded, and they do so at a low efficiency cost. As a stepping stone for our simulations, we provide novel integer programming formulations for computing core, competitive, and strong core allocations.

2023

Novel integer programming models for the stable kidney exchange problem

Authors
Klimentova, X; Biró, P; Viana, A; Costa, V; Pedroso, JP;

Publication
European Journal of Operational Research

Abstract

2022

The Probabilistic Travelling Salesman Problem with Crowdsourcing

Authors
Santini, A; Viana, A; Klimentova, X; Pedroso, JP;

Publication
COMPUTERS & OPERATIONS RESEARCH

Abstract
We study a variant of the Probabilistic Travelling Salesman Problem arising when retailers crowdsource last-mile deliveries to their own customers, who can refuse or accept in exchange for a reward. A planner must identify which deliveries to offer, knowing that all deliveries need fulfilment, either via crowdsourcing or using the retailer's own vehicle. We formalise the problem and position it in both the literature about crowdsourcing and among routing problems in which not all customers need a visit. We show that to evaluate the objective function of this stochastic problem for even one solution, one needs to solve an exponential number of Travelling Salesman Problems. To address this complexity, we propose Machine Learning and Monte Carlo simulation methods to approximate the objective function, and both a branch-and-bound algorithm and heuristics to reduce the number of evaluations. We show that these approaches work well on small size instances and derive managerial insights on the economic and environmental benefits of crowdsourcing to customers.