Explore the vast range of titles available.

Kidney exchange programs (KEP) allow an incompatible patient–donor pair, whose donor cannot provide a kidney to the respective patient, to have a transplant exchange with another in a similar situation if there is compatibility. Exchanges can be performed via cycles or chains initiated by non-directed donors (NDD), i.e., donors that do not have an associated patient. The objective for optimization in KEP is generally to maximize the number of possible transplants. Following the course of recent approaches that consider a dynamic matching (exchanges are decided every time a pair or a NDD joins the pool), in this paper we explore two matching policies to find feasible exchanges: periodic, where the algorithm runs within some period (e.g each 3 month); and greedy, in which a matching run is done as soon as the pool is updated with a new pair or NDD. For each policy, we propose a matching algorithm that addresses the waiting times of pairs in a pool. We conduct computational experiments with the proposed algorithms and compare the results with those obtained when periodic and greedy matching aim at maximizing the number of transplants.

In this paper, we propose a branch-and-price approach for solving the problem of maximizing the expected number of transplants in Kidney Exchange Programs (KEPs). In these programs, the decision on which transplants will be conducted is usually made with the support of optimization models with the assumption that all operations will take place. However, after a plan of transplants is defined, a pair may leave the KEP or a more accurate compatibility evaluation exam may invalidate a transplant. To model these possible events we consider probabilities of failure of vertices and of arcs and the objective of maximizing the expected number of transplants. The proposed approach is based on the so-called cycle formulation, where decision variables are associated with cycles. Built on the concept of type of cycle a branch-and-price algorithm is conceived. One subproblem is defined for each type of cycle. We present computational results of the proposed branch-and-price algorithm and compare them with solving directly the cycle formulation (with a general purpose mixed integer programming solver—CPLEX) showing that the proposed approach is the only one suitable for larger instances.

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.

Kidney exchange programs (KEPs) allow the exchange of kidneys between incompatible donor-recipient pairs. Optimization approaches can help KEPs in defining which transplants should be made among all incompatible pairs according to some objective. The most common objective is to maximize the number of transplants. In this paper, we propose an integer programming model which addresses the objective of maximizing the expected number of transplants, given that there are equal probabilities of failure associated with vertices and arcs. The model is compact, i.e. has a polynomial number of decision variables and constraints, and therefore can be solved directly by a general purpose integer programming solver (e.g. Cplex).

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. In this paper we show that in the case of strict preferences the unique strong core allocation (or competitive allocation) respects improvement: if an agent's object becomes more attractive for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We obtain a general result in case of ties in the preferences and provide new integer programming formulations for computing (strong) core and competitive allocations. Finally, we conduct computer simulations to compare the game-theoretical solutions with maximum size and maximum weight exchanges for markets that resemble the pools of kidney exchange programmes.

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. In this paper we show that in the case of strict preferences the unique strong core allocation (or competitive allocation) respects improvement: if an agent's object becomes more attractive for some other agents, then the agent's allotment in the unique strong core allocation weakly improves. We obtain a general result in case of ties in the preferences and provide new integer programming formulations for computing (strong) core and competitive allocations. Finally, we conduct computer simulations to compare the game-theoretical solutions with maximum size and maximum weight exchanges for markets that resemble the pools of kidney exchange programmes.

Kidney exchange programs (KEP's) 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 patient--donor can join a pool of incompatible pairs and, if compatibility between patient and donor in two our more pairs exists, organs can be exchanged between them. The problem can be modeled 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 patient there may exist a preference order over the organs that he/she can receive, since a patient may be compatible with several donors but may have a better fit over some than over others. Under this setting, the aim is to find the maximum cardinality stable exchange, a solution where no blocking cycle exists. For this purpose we propose three novel integer programming models based on the well-known edge and cycle formulations. 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. Furthermore, 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 instances.