---
title: "Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming"
authors:
  - "Fulya Trösser"
  - "Simon de Givry"
  - "George Katsirelos"
doi: "10.24963/ijcai.2021/584"
url: "https://ijcai.org/proceedings/2021/584"
pdf: "https://ijcai.org/proceedings/2021/0584.pdf"
venue: "Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence"
year: 2021
pages: "4250-4257"
track: "Main Track"
keywords:
  - "Uncertainty in AI: Bayesian Networks"
  - "Constraints and SAT: Constraint Optimization"
---

# Improved Acyclicity Reasoning for Bayesian Network Structure Learning with Constraint Programming

Fulya Trösser, Simon de Givry, George Katsirelos

*Proceedings of the Thirtieth International Joint Conference on Artificial Intelligence*, pages 4250-4257. DOI: [10.24963/ijcai.2021/584](https://doi.org/10.24963/ijcai.2021/584)

## Abstract

Bayesian networks are probabilistic graphical models with a wide
range of application areas including gene regulatory networks 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
work, we propose 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 generalized
arc consistency algorithm for the acyclicity constraint.  We embed
these in the constraint programming-based branch-and-bound solver
CPBayes and show that, despite being suboptimal, they improve
performance by orders of magnitude. The resulting solver also compares
favorably with GOBNILP, a state-of-the-art solver for the BNSL
problem which solves an NP-hard problem to discover each cut and
solves the linear program exactly.