Data-driven prediction of relevant scenarios for robust combinatorial optimization
针对离散不确定性的两阶段鲁棒组合优化问题，提出相关场景识别问题并证明其计算复杂性，设计基于随机森林的启发式方法预测初始场景，实验表明能加速求解过程并缩小最优性差距。
We study iterative constraint and variable generation methods for (two-stage) robust combinatorial optimization problems with discrete uncertainty. The goal of this work is to find a set of starting scenarios that provides strong lower bounds early in the process. To this end we define the Relevant Scenario Recognition Problem (RSRP) which finds the optimal choice of scenarios which maximizes the corresponding objective value. We show for classical and two-stage robust optimization that this problem can be solved in polynomial time if the number of selected scenarios is constant and NP-hard if it is part of the input. Furthermore, we derive a linear mixed-integer programming formulation for the problem in both cases. Since solving the RSRP is not possible in reasonable time, we propose a machine-learning-based heuristic to determine a good set of starting scenarios. To this end, we design a set of dimension-independent features, and train a Random Forest Classifier on already solved small-dimensional instances of the problem. Our experiments show that our method is able to improve the solution process even for larger instances than contained in the training set, and that predicting even a small number of good starting scenarios can considerably reduce the optimality gap. Additionally, our method provides a feature importance score which can give new insights into the role of scenario properties in robust optimization. • We consider robust one- and two-stage robust problems with discrete uncertainty. • The scenario recognition problem is to identify the most relevant scenarios. • We derive scenario features to train a machine learning model for this problem. • The model us used to speed up column-and-constraint generation method. • Experiments show improved performance and allow identification of important features.