Supervised Dimensionality Reduction for the Algorithm Selection Problem

Instance space analysis extends the algorithm selection framework by enabling the visualisation of problem instances via dimensionality reduction (DR). The lower dimensional projection can also be used as input to predict algorithm performance, or to perform algorithm selection. In this paper we consider two supervised DR methods - partial least squares (PLS) and linear discriminant analysis (LDA) - both as visualisation tools and for the purpose of constructing classification models for algorithm selection. Multinomial logistic regression models are used for the classification problem. We compare PLS and LDA to DR methods previously used in this context on three combinatorial optimisation problems, and show that these methods are as competitive.