Our algorithms work not only for the standard BNSL problem but also for some structural
constraints that we may wish to impose on the final DAG. To formulate the algorithms compactly,
we introduce a generalization of BNSL, where each possible parent set
is associated with a score and a weight and the aim is to find the highest scoring network
that does not exceed a specified weight bound. We show that this captures natural types of
structural constraints. As a side result, we show that a previous polynomial-time
algorithm for acyclic directed superstructures [1]} can be generalized to this new more general
problem.
