Machine Learning for K -Adaptability in Two-Stage Robust Optimization

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 a 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, which allows us to train our machine learning tool on a database of resolved branch-and-bound 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 as well as in cases when the K -value or the problem size differs from the training ones.