ETD

Digital archive of theses discussed at the University of Pisa

 

Thesis etd-01202022-122248


Thesis type
Tesi di dottorato di ricerca
Author
IOMMAZZO, GABRIELE
URN
etd-01202022-122248
Thesis title
Algorithmic Configuration by Learning and Optimization
Academic discipline
INF/01
Course of study
INFORMATICA
Supervisors
tutor Prof. Frangioni, Antonio
Keywords
  • machine learning
  • operations research
  • optimization solvers
  • algorithm configuration
  • parameter tuning
  • distance geometry
  • mathematical programming
  • mathematical optimization
Graduation session start date
06/02/2022
Availability
Full
Summary
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.
File