Finding Minimal Cost Herbrand Models with Branch-Cut-and-Price

Given (1) a set of clauses T in some first-order lan-
guage L and (2) a cost function c : BL → R+,
mapping each ground atom in the Herbrand base
BL to a non-negative real, then the problem of
finding a minimal cost Herbrand model is to either
find a Herbrand model I of T which is guaranteed
to minimise the sum of the costs of true ground
atoms, or establish that there is no Herbrand model
for T . A branch-cut-and-price integer program-
ming (IP) approach to solving this problem is pre-
sented. Since the number of ground instantiations
of clauses and the size of the Herbrand base are
both infinite in general, we add the corresponding
IP constraints and IP variables ‘on the fly’ via ‘cut-
ting’ and ‘pricing’ respectively. In the special case
of a finite Herbrand base we show that adding all
IP variables and constraints from the outset can be
advantageous, showing that a challenging Markov
logic network MAP problem can be solved in this
way if encoded appropriately