2018/08/14 by James Cussens, Cussens, James
Computer Science · Mathematics · #Algorithm #Artificial Intelligence (cs.AI) #Base (topology) #Combinatorics #Computer science #Discrete mathematics #FOS: Computer and information sciences #Formal Methods in Verification #Function (biology) #Integer (computer science) #Integer programming #Machine Learning and Algorithms #Mathematics #Programming language #Set (abstract data type) #cs.AI #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.1808.04758
arxiv created 2018/08/14 · openalex publication_date 2018/08/14 · arxiv updated 2018/08/15 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/01
Given (1) a set of clauses T in some first-order language \cal L and (2) a cost function c : B\cal L → ℝ+, 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.