Abstract
Given (1) a set of clauses $T$ in some first-order language $\cal L$ and (2)a cost function $c : B_{{\cal L}} \rightarrow \mathbb{R}_{+}$, mapping eachground atom in the Herbrand base $B_{{\cal L}}$ to a non-negative real, thenthe problem of finding a minimal cost Herbrand model is to either find aHerbrand model $\cal I$ of $T$ which is guaranteed to minimise the sum of thecosts of true ground atoms, or establish that there is no Herbrand model for$T$. A branch-cut-and-price integer programming (IP) approach to solving thisproblem is presented. Since the number of ground instantiations of clauses andthe size of the Herbrand base are both infinite in general, we add thecorresponding IP constraints and IP variables `on the fly' via `cutting' and`pricing' respectively. In the special case of a finite Herbrand base we showthat adding all IP variables and constraints from the outset can beadvantageous, showing that a challenging Markov logic network MAP problem canbe solved in this way if encoded appropriately.