Towards a White Box Approach to Automated Algorithm Design

Abstract

To date, algorithms for real-world problems are most commonly designed following a manual, ad-hoc, trial and error approach, making algorithm design a tedious, time-consuming and costly process. Recently, Programming by Optimization (PbO) has been proposed as an alternative design paradigm in which algorithmic choices are left open by design and algorithm configuration methods (e.g. ParamILS) are used to automatically generate the best algorithm for a specific use-case. We argue that, while powerful, contemporary configurators limit themselves by abstracting information that can otherwise be exploited to speed up the optimization process as well as improve the quality of the resulting design. In this work, we propose an alternative white box approach, reformulating the algorithm design problem as a Markov Decision Process, capturing the intrinsic relationships between design decisions and their respective contribution to overall algorithm performance. Subsequently, we discuss and illustrate the benefits of this formulation experimentally. PDF