TY - JOUR A1 - Goerigk, Marc A1 - Kurtz, Jannis T1 - Data-driven prediction of relevant scenarios for robust combinatorial optimization JF - Computers & Operations Research N2 - 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. KW - Robust optimization KW - Two-stage robust optimization KW - Data-driven optimization KW - Machine learning for optimization Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-19207 SN - 1873-765X VL - 2025 IS - 174 PB - Elsevier CY - Amsterdam ER - TY - JOUR A1 - Goerigk, Marc A1 - Khosravi, Mohammad T1 - Robust combinatorial optimization problems under budgeted interdiction uncertainty JF - OR Spectrum (ISSN: 1436-6304) N2 - In robust combinatorial optimization, we would like to find a solution that performs well under all realizations of an uncertainty set of possible parameter values. How we model this uncertainty set has a decisive influence on the complexity of the corresponding robust problem. For this reason, budgeted uncertainty sets are often studied, as they enable us to decompose the robust problem into easier subproblems. We propose a variant of discrete budgeted uncertainty for cardinality-based constraints or objectives, where a weight vector is applied to the budget constraint. We show that while the adversarial problem can be solved in linear time, the robust problem becomes NP-hard and not approximable. We discuss different possibilities to model the robust problem and show experimentally that despite the hardness result, some models scale relatively well in the problem size. KW - - KW - Robust optimization KW - Combinatorial optimization KW - Budgeted uncertainty KW - Knapsack uncertainty Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:101:1-2408131120370.349068848723 SN - 0171-6468 SN - 1436-6304 VL - 47 IS - 1 SP - 255 EP - 285 PB - Springer CY - Berlin/Heidelberg ER - TY - JOUR A1 - Goerigk, Marc A1 - Khosravi, Mohammad T1 - Benchmarking problems for robust discrete optimization JF - Computers & Operations Research (Online ISSN: 1873-765X) N2 - Robust discrete optimization is a highly active field of research where a plenitude of combinations between decision criteria, uncertainty sets and underlying nominal problems are considered. Usually, a robust problem becomes harder to solve than its nominal counterpart, even if it remains in the same complexity class. For this reason, specialized solution algorithms have been developed. To further drive the development of stronger solution algorithms and to facilitate the comparison between methods, a set of benchmark instances is necessary but so far missing. In this paper we propose a further step towards this goal by proposing several instance generation procedures for combinations of min–max, min–max regret, two-stage and recoverable robustness with interval, discrete, budgeted or ellipsoidal uncertainty sets. Besides sampling methods that go beyond the simple uniform sampling method that is the de-facto standard to produce instances, also optimization models to construct hard instances are considered. Using a selection problem for the nominal ground problem, we are able to generate instances that are several orders of magnitudes harder to solve than uniformly sampled instances when solving them with a general mixed-integer programming solver. All instances and generator codes are made available online. KW - Robust optimization KW - Benchmarking KW - Instance generator KW - Combinatorial optimization Y1 - 2024 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:bvb:739-opus4-18752 VL - 2024 IS - 166 PB - Elsevier CY - Amsterdam ER -