Constructing Streams of Optimization Instances for Benchmarking Algorithm Selection and Configuration Approaches in Streaming Scenarios

Abstract

In many real-world applications, optimization problems do not appear in isolation but as streams of instances that need to be solved in sequence. Moreover, the features of the instances that compose a stream may change over time, influencing the performance of optimization algorithms. However, most work in automatic algorithm selection and configuration still focuses on static or offline settings, with only a few studies addressing the streaming case. Progress in this area may be hindered by the absence of a general, flexible benchmark that would allow researchers to evaluate new methods under controlled and reproducible settings. This paper presents a methodology for constructing benchmark streams of optimization problem instances, applicable to any domain equipped with a problem generator that allows generating intermediate instances between known classes. The approach enables fine-grained control over key stream characteristics, including the frequency and speed of transitions between different problem classes, and whether these changes affect instance features, algorithmic performance, or both. This flexibility allows the creation of diverse benchmarks, which can be used to stress-test existing and future algorithm selection and configuration approaches, revealing their performance under different stream types.