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 or budgeted 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.
翻译:强有力的离散优化是一个非常活跃的研究领域,考虑决策标准、不确定性和基本名义问题之间的广泛结合。通常,一个强大的问题比其名义对应方更难解决,即使它仍然属于同一复杂类别。为此原因,已经开发了专门的解决办法算法。为了进一步推动开发更强的解决方案算法并促进方法之间的比较,有必要制定一套基准实例,但迄今为止还远远没有。在本文件中,我们提议进一步为实现这一目标而采取进一步的步骤,提议若干实例生成程序,将微量、微量迟缓遗憾、两阶段和可回收的不确定性组合结合在一起。除了超出简单统一抽样方法的取样方法外(即用于生成实例的脱法式标准),还考虑优化模型以构建硬实例。我们利用名义地面问题的选择问题,在用一般混合式编程求解器解决这些问题时,我们可以产生比统一抽样实例更难解决的若干数量级。所有实例和发电机代码都是在线提供的。