You are here

Logic-Based Benders Decomposition for Super Solutions: an Application to the Kidney Exchange Problem


Sorina Chisca, Michele Lombardi, Michela Milano, Barry O'Sullivan

Publication Type: 
Refereed Conference Meeting Proceeding
When optimising under uncertainty, it is desirable that solutions are robust to unexpected disruptions and changes. A possible formalisation of robust-ness is given by super solutions. An assignment to a set of decision variables isan(a,b,c)super solution if any change involving at most a variables can be re-paired by changing at most b other variables; the repair solution should have a cost of at most c units worse than a non-robust optimum. We propose a method exploiting Logic Based Benders Decomposition to find super solutions to an optimisation problem for generic disruptions. The master deals with the origina lproblem, while subproblems try to find repair solutions for each possible disruption. As a case study, we consider the Kidney Exchange Problem, for whichour method scales dramatically better on realistic instances than a reformulation-based approach from the literature.
Conference Name: 
The 25th International Conference on Principles and Practice of Constraint Programming
Digital Object Identifer (DOI): 
Publication Date: 
Conference Location: 
United States of America
National University of Ireland, Cork (UCC)
Open access repository: