Due to this notorious hardness of BNSL, it is mostly solved using heuristics. One of the most
successful heuristic approaches relies on local search [1]}. More precisely, in this approach one starts with an
arcless DAG \(D\)  and adds, removes, or reverses an arc while this results in an increased
network score. More recent local search approaches do not use DAGs as solution representations but rather orderings of the variables [2]}, [3]}, [4]}. This approach is motivated by the fact that given an ordering \(\tau \)  of the variables, one may greedily find the optimal DAG \(D\)  among all DAGs for which \(\tau \)  is a topological ordering [5]}. Lee and van Beek [3]} study a local search approach that is based on an operation, where one interchanges the positions of two consecutive vertices on the ordering as long as this results in an improvement of the network score. We refer to this operation as an inversion. Alonso-Barba et al. [2]} an insert operation, where one removes a vertex from the ordering and inserts this vertex at a new position. Scanagatta et al. [4]} considered inversions, insertions, and a further generalized operation where one removes a larger block of consecutive vertices from the ordering and inserts the block of consecutive vertices at a new position.
<FIGURE>