TY - CHAP
T1 - Logic-Based Benders Decomposition for Super Solutions
T2 - 25th International Conference on Principles and Practice of Constraint Programming, CP 2019
AU - Chisca, Danuta Sorina
AU - Lombardi, Michele
AU - Milano, Michela
AU - O’Sullivan, Barry
N1 - Publisher Copyright:
© 2019, Springer Nature Switzerland AG.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - https://www.scopus.com/pages/publications/85075745213
U2 - 10.1007/978-3-030-30048-7_7
DO - 10.1007/978-3-030-30048-7_7
M3 - Chapter
AN - SCOPUS:85075745213
SN - 9783030300470
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 108
EP - 125
BT - Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Proceedings
A2 - Schiex, Thomas
A2 - de Givry, Simon
PB - Springer
Y2 - 30 September 2019 through 4 October 2019
ER -