November 27, 2023
George Katsirelos (MIA Paris-Saclay, INRAE)Bayesian networks are probabilistic graphical models with a wide range of application areas including gene regulatory network inference, risk analysis and image processing. Learning the structure of a Bayesian network (BNSL) from discrete data is known to be an NP-hard task with a superexponential search space of directed acyclic graphs.
In this talk, I will present recent work on solving the BNSL using constraint programming. Building on previous work on solving BNSL with CP and with ILP, we propose new algorithms for handling the difficult acyclicity constraint and the so-called cluster cuts that can be generated from it. We give a new polynomial time algorithm for discovering a subset of all possible cluster cuts, a greedy algorithm for approximately solving the resulting linear program, and a generalised arc consistency algorithm for the acyclicity constraint. These improve performance by orders of magnitude compared to previous CP-based approaches, but scalability is still limited by the fact that the basic decision variables used in this model have domain size Omega(n^log n). We propose a novel representation of domains using decision trees and show that relatively simple operations are sufficient to implement all propagation and bounding algorithms. The combination of the algorithmic techniques and the new representation result in a solver which compares favourably with all competing state-of-the-art approaches.