Data-driven Prediction of Relevant Scenarios for Robust Combinatorial Optimization
This work addresses robust optimization challenges for combinatorial problems, offering an incremental improvement with practical insights via feature importance analysis.
The paper tackles the problem of robust combinatorial optimization with discrete uncertainty by proposing a machine-learning-based heuristic to identify starting scenarios that yield strong lower bounds, resulting in improved solution processes for larger instances beyond the training set.
We study iterative methods for (two-stage) robust combinatorial optimization problems with discrete uncertainty. We propose a machine-learning-based heuristic to determine starting scenarios that provide strong lower bounds. To this end, we design dimension-independent features and train a Random Forest Classifier on small-dimensional instances. Experiments show that our method improves the solution process for larger instances than contained in the training set and also provides a feature importance-score which gives insights into the role of scenario properties.