  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 each
ground atom in the Herbrand base $B_{{\cal L}}$ to a non-negative real, then
the problem of finding a minimal cost Herbrand model is to either find a
Herbrand model $\cal 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 programming (IP) approach to solving this
problem is presented. 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 `cutting' 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.
