Algorithmic Configuration by Learning and Optimization

The research topics of this Ph.D. thesis lie at the intersection of Machine Learning (ML) and Mathematical Programming (MP). The main contributions concern the algorithm configuration problem and the distance geometry problem. Given a configurable algorithm A and an input P for A, the algorithm configuration problem (ACP) addresses the issue of identifying the parameter configuration of A ensuring the best algorithmic performance in solving P. We propose two novel MP-driven methodologies, where: we first train an ML predictor to approximate the behaviour of A; then, we provide an explicit description of its mathematical properties and embed the resulting encoding into an MP formulation F; finally, when we need to use A on a new input, we optimize F to retrieve the parameter configuration of A yielding the best algorithmic performance for that input. Furthermore, we consider a methodology for finding a realization of a graph in a Euclidean space of given dimension. This is known as the distance geometry problem, and we propose a new MP formulation for solving it. Our research is partly motivated by the fact that it can serve as a graph embedding methodology, in view of applying vector-based ML paradigms to graphs.