Julia Handl

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.

This paper describes an approach for deriving visual insights about the joint relationship between algorithm performance, algorithm parameters, and problem instance features. This involves the combined analysis and exploration of a 2D instance space, to which instances from some problem space are projected, and a 2D configuration space, to which (algorithm) configurations are projected. Extending on the dimensionality reduction problem solved in Instance Space Analysis, we define an optimisation problem for finding projections to these two spaces, with an interpretable relationship between them. Then, we describe the tools developed for probing those spaces in an investigation of the question: What characterises the algorithm configurations that perform best on a selected group of instances (or vice versa)? We demonstrate the use of these tools on synthetic data with known ground truth.