Machine Learning for K-adaptability in Two-stage Robust Optimization
Preprint
Abstract
Two-stage robust optimization problems constitute one of the hardest optimization problem classes. One of the solution approaches to this class of problems is K-adaptability. This approach simultaneously seeks the best partitioning of the uncertainty set of scenarios into K subsets, and optimizes decisions corresponding to each of these subsets. In general case, it is solved using the K-adaptability branch-and-bound algorithm, which requires exploration of exponentially-growing solution trees. To accelerate finding high-quality solutions in such trees, we propose a machine learning-based node selection strategy. In particular, we construct a feature engineering scheme based on general two-stage robust optimization insights that allows us to train our machine learning tool on a database of resolved B&B trees, and to apply it as-is to problems of different sizes and/or types. We experimentally show that using our learned node selection strategy outperforms a vanilla, random node selection strategy when tested on problems of the same type as the training problems, also in case the K-value or the problem size differs from the training ones.Keywords
All Related Versions
This publication has 7 references indexed in Scilit:
- Monte Carlo Tree Search: a review of recent modifications and applicationsArtificial Intelligence Review, 2022
- Machine learning for combinatorial optimization: A methodological tour d’horizonEuropean Journal of Operational Research, 2021
- K-adaptability in two-stage mixed-integer robust optimizationMathematical Programming Computation, 2019
- Multistage Robust Mixed-Integer Optimization with Adaptive PartitionsOperations Research, 2016
- Min–max–min robust combinatorial optimizationMathematical Programming, 2016
- Finite Adaptability in Multistage Linear OptimizationIEEE Transactions on Automatic Control, 2010
- Adjustable robust solutions of uncertain linear programsMathematical Programming, 2004