A double-oracle, logic-based Benders decomposition approach to solve the K-adaptability problem. (July 2023)

• Record Type: Journal Article
• Authors: Ghahtarani, Alireza; Saif, Ahmed; Ghasemi, Alireza; Delage, Erick
• Is Part Of: Computers & operations research. Volume 155(2023)
• Publication Date: 2023-07
• Subjects: Combinatorial optimization -- K-adaptability problem -- Adaptive robust optimization -- Discrete recourse -- Logic-based Benders decomposition; Operations research -- Periodicals; Electronic digital computers -- Periodicals; 004.05
• DOI: 10.1016/j.cor.2023.106243
• Languages: English
• ISSNs: 0305-0548

Abstract

Abstract: 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. Highlights: A K -adaptability problem with binary first-stage variables is solved. Combinatorial Benders decomposition is applied, leading to an MMMCRO subproblem. A novel double-oracle algorithm is proposed to solve the subproblem effectively. The proposed algorithm enjoys finite convergence under mild conditions. The proposed approach can be extended to other important variants of the problem.