A method for the automated configuration of anytime portfolios of algorithms

Optimization algorithms contain parameters that greatly influence their behavior, such that finding good parameters with automated algorithm configuration tools has become a critical component in the algorithm design process. Many optimization algorithms possess the anytime property, meaning they can be stopped at any time during their execution and provide a feasible solution. Setting the parameters of anytime algorithms is difficult, as the parameters ought to provide robust performance across varying execution times. Traditional algorithm configuration methods address this challenge by finding a one-size-fits-all parameter configuration, however finding a portfolio of configurations, each targeted to a different runtime, can lead to better overall performance. We introduce a novel algorithm configuration method for configuring anytime algorithms that produces viable configuration portfolios that assign different configurations to different runtimes. Our proposed method harnesses an early termination mechanism for unpromising configurations using a cost-sensitive machine learning approach. Furthermore, it uses two novel MIP formulations to discard configurations and to create the configuration portfolio, respectively.