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

When optimising under uncertainty, it is desirable that solutions are robust to unexpected disruptions and changes. A possible formalisation of robustness is given by super solutions. An assignment to a set of decision variables is an (a, b, c) super solution if any change involving at most a variables can be repaired 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 original problem, while subproblems try to find repair solutions for each possible disruption. As a case study, we consider the Kidney Exchange Problem, for which our method scales dramatically better on realistic instances than a reformulation-based approach from the literature.