Surrogate Management Strategies for Accelerating Parallel Algorithm Portfolio Construction

Many algorithms require careful parameterization, whose choice significantly impacts performance, with no single configuration excelling across all problem types. Automatic Algorithm Configuration provides a systematic approach to parameter exploration, enabling the identification of problem-specific optimal configurations. Automatic Construction of Parallel Portfolio (ACPP) extends this idea by configuring and running multiple solvers simultaneously in parallel, exploiting their complementary strengths for improved generalization. Existing ACPP approaches treat construction time as a fixed budget and make only partial use of the performance data collected during component solver evaluation. To address this limitation, our solution relies on using the data generated during portfolio construction to train surrogate models that replace costly evaluations to reduce computational overhead. Furthermore, to identify effective surrogate models, we compare various machine learning approaches, including applications of survival analysis techniques for handling censored runtime data. We evaluate these models’ predictive capabilities using data generated by the LKH solver on the Traveling Salesperson Problem instances. Finally, we propose several surrogate model management strategies and integrate them into existing portfolio construction approaches. Our results demonstrate that survival-based models achieve superior predictive performance compared to standard machine learning approaches. The proposed surrogate model management strategies offer significant savings in portfolio construction time while maintaining acceptable performance on unseen test instances.