Construction of an ROBDD for a PB-Constraint in Band Form and Related Techniques for PB-Solvers

Access this Article

Author(s)

    • NABESHIMA Hidetomo
    • Interdisciplinary Graduate School of Medicine and Engineering, University of Yamanashi

Abstract

Pseudo-Boolean (PB) problems are Integer Linear Problem restricted to 0-1 variables. This paper discusses on acceleration techniques of PB-solvers that employ SAT-solving of combined CNFs each of which is produced from each PB-constraint via a binary decision diagram (BDD). Specifically, we show (i) an efficient construction of a reduced ordered BDD (ROBDD) from a constraint in band form <i>l</i> ≤ <Linear term> ≤ <i>h</i>, (ii) a CNF coding that produces two clauses for some nodes in an ROBDD obtained by (i), and (iii) an incremental SAT-solving of the binary/alternative search for minimizing values of a given goal function. We implemented the proposed constructions and report on experimental results.

Journal

  • IEICE Transactions on Information and Systems

    IEICE Transactions on Information and Systems E98.D(6), 1121-1127, 2015

    The Institute of Electronics, Information and Communication Engineers

Codes

Page Top