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. In this talk, I will present some recent work on attacking this problem by combining techniques from constraint programming and integer programming. I will show that a subclass of violated inequalities from a well known exponentially large formulation of the problem can be detected efficiently and the resulting LP solved approximately, all using techniques derived from constraint programming. This deep integration of CP and ILP techniques yields significant improvements in runtime and scalability.