A double-oracle, logic-based Benders decomposition approach to solve the K-adaptability problem

摘要

The K-adaptability problem is a special case of adaptive robust optimization with discrete recourse that aims to prepare K solutions under uncertainty, and select among them upon full knowledge of the realized scenario. We propose a novel approach to solve K-adaptability problems with linear objective and constraints, binary first -stage decision variables, second-stage objective uncertainty, and a polyhedral uncertainty set. A logic-based Benders decomposition is applied to handle the first-stage decisions in a master problem, thus the Benders subproblem becomes a min-max-min robust combinatorial optimization problem. To solve the subproblem, a double-oracle algorithm that iteratively generates adverse scenarios and recourse decisions and assigns scenarios to K-subsets of the decisions by solving p-center problems is devised. Extensions of the proposed approach to handle parameter uncertainty in both the first-stage objective and the second-stage constraints, and for integer first-stage decision variables and nonlinear functions, are also provided. We show that, under mild conditions, the proposed algorithm converges to an optimal solution and terminates in a finite number of iterations. Numerical results obtained from experiments on benchmark instances of the adaptive shortest path problem, the regular knapsack problem, the asset liability-management problem, and a generic K-adaptability problem demonstrate the performance advantage of the proposed approach when compared to state-of-the-art methods in the literature.