Learning Boltzmann Distributions for Combinatorial Optimization – ComBo

This project is at the interface of statistical learning (mainly deep learning) and combinatorial optimization (mainly stochastic and evolutionary). Its originality is to propose a coupling between the two types of approaches, based on 3 modules:
i/ the search for a continuous embedding of the combinatorial space, respecting the regularities of the domain and/or the objective function (e.g., invariance or equivariance properties);
ii/ the use of this embedding to found a continuous relaxation of the combinatorial problem, supporting efficient local searches based on the gradient (on the objective function and/or on the associated Boltzmann distribution);
iii/ the use of distribution representation and estimation in discrete form (particles), and of particle transport operators realizing the convergence of this distribution to the target distribution (Boltzmann).
This project aims at designing and justifying an efficient coupling between representation learning and evolutionary modeling for combinatorial optimization. Such a coupling will favor algorithmic and fundamental advances. In particular, the convergence analysis and the justification of the proposed transport mechanism will be based on the closed form of the target distribution.