Abstract
This paper introduces tabu search for the solution of general linear integer problems. Search is done on integer variables; if there are continuous variables, their corresponding value is determined through the solution of a linear program, which is also used to evaluate the integer solution.The complete tabu search procedure includes an intensification and diversification procedure, whose effects are analysed on a set of benchmark problems.© 2005 by Kluwer Academic Publishers.

Abstract
We propose an automated timetabling system for a typical situation in universities, where agents (usually departments or faculties) compete for a set of resources (lecture rooms) on a given number of time slots. Each agent uses its own algorithm (which might be unknown to the others). A central system decides whether some agent is granted a resource or not, based on a list of requests and on a certificate, obtained from each agent, asserting that it does not have requests with priority higher that a certain amount. Priority is measured primarily by the number of attendees and some requirements for particular features on the resources, but other criteria are proposed for ties. We describe a prototype implementation, in use at the Faculty of Sciences, University of Porto.

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.

Abstract

Abstract

Abstract