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

DOI10.1016/J.COR.2023.106243MaRDI QIDQ6164623zbMATH OpenFDO

Authors Alireza Ghahtarani, Ahmed Saif, Alireza Ghasemi, Erick Delage

Publication date 4 July 2023

Published in Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2209.02936

zbMATH Keywords

\(K\)-adaptability problemadaptive robust optimizationcombinatorial optimizationdiscrete recourselogic-based Benders decomposition

Mathematics Subject Classification ID

Operations research and management science (90Bxx)

Abstract: We propose a novel approach to solve K-adaptability problems with convex objective and constraints and integer first-stage decisions. A logic-based Benders decomposition is applied to handle the first-stage decisions in a master problem, thus the sub-problem becomes a min-max-min robust combinatorial optimization problem that is solved via 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. Extensions of the proposed approach to handle parameter uncertainty in both the first-stage objective and the second-stage constraints are also provided. We show that the proposed algorithm converges to an optimal solution and terminates in finite number of iterations. Numerical results obtained from experiments on benchmark instances of the adaptive shortest path problem, the regular knapsack 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.

Recommendations

• K-adaptability in stochastic optimization
• \(K\)-adaptability in two-stage mixed-integer robust optimization
• K-adaptability in two-stage robust binary programming
• \(K\)-adaptability in stochastic combinatorial optimization under objective uncertainty
• Min-max-min robust combinatorial optimization

Cites work

• \(K\)-adaptability in two-stage mixed-integer robust optimization
• K-adaptability in two-stage robust binary programming
• Adjustable robust solutions of uncertain linear programs
• Binary decision rules for multistage adaptive mixed-integer optimization
• Design of near optimal decision rules in multistage adaptive mixed-integer optimization
• Faster algorithms for min-max-min robustness for combinatorial problems with budgeted uncertainty
• Finite Adaptability in Multistage Linear Optimization
• Generalized decision rule approximations for stochastic programming via liftings
• Min-max-min robust combinatorial optimization
• Min-max-min robustness for combinatorial problems with discrete budgeted uncertainty
• Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions
• Primal and dual linear decision rules in stochastic and robust optimization
• Supermodularity and affine policies in dynamic robust optimization
• The integer \(L\)-shaped method for stochastic integer programs with complete recourse
• Theory and applications of robust optimization
• Uncertain linear programs: extended affinely adjustable robust counterparts

Cited in

(7)

• Decomposition-Based Approaches for a Class of Two-Stage Robust Binary Optimization Problems
• Min-Sup-Min Robust Combinatorial Optimization with Few Recourse Solutions
• Algorithms for a risk-averse Stackelberg game with multiple adversaries
• Approximation guarantees for min-max-min robust optimization and \(k\)-adaptability under objective uncertainty
• A distributionally robust optimization approach for the potassium fertilizer product transportation considering transshipment through crossdocks
• Streamlining emergency response: a K-adaptable model and a column-and-constraint-generation algorithm
• Worst-case conditional value at risk for asset liability management: a framework for general loss functions

This page was built for publication: A double-oracle, logic-based Benders decomposition approach to solve the \(K\)-adaptability problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6164623)