Learning Chordal Markov Networks by Constraint Satisfaction
  We investigate the problem of learning the structure of a Markov network from
data. It is shown that the structure of such networks can be described in terms
of constraints which enables the use of existing solver technology with
optimization capabilities to compute optimal networks starting from initial
scores computed from the data. To achieve efficient encodings, we develop a
novel characterization of Markov network structure using a balancing condition
on the separators between cliques forming the network. The resulting
translations into propositional satisfiability and its extensions such as
maximum satisfiability, satisfiability modulo theories, and answer set
programming, enable us to prove optimal certain network structures which have
been previously found by stochastic search.
