On Boolean functions encodable as a single linear pseudo-Boolean constraint

Smaus, J.-G.
(2007) Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 4th International Conference, CPAIOR 2007 — Location: Brussels, Belgium (23.May.2007)

Files

No attached file found for this publication.

Details

Authors
  • Smaus, J.-G.
    Author
Abstract
A linear pseudo-Boolean constraint (LPB) is an expression of the form a/sub 1/ ldr l/sub 1/+ ... + a/sub m/ ldr l/sub m/ >or= d, where each l/sub i/ is a literal (it assumes the value 1 or 0 depending on whether a propositional variable x/sub i/ is true or false) and a/sub 1/,...,a/sub m/, d are natural numbers. An LPB is a generalisation of a propositional clause, on the other hand it is a restriction of integer linear programming. LPBs can be used to represent Boolean functions more compactly than the well-known conjunctive or disjunctive normal forms. In this paper, we address the question: how much more compactly? We compare the expressiveness of a single LPB to that of related formalisms, and give an algorithm for computing an LPB representation of a given formula if this is possible.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Smaus, J.-G. (2007). On Boolean functions encodable as a single linear pseudo-Boolean constraint. In Van Hentenryck, P.; Wolsey, L.; (ed.), Integration of AI and OR Techniques in Constraint Programming forCombinatorial Optimization Problems. Proceedings 4th InternationalConference, CPAIOR 2007 (p. p. 288-302). Springer-verlag. https://hdl.handle.net/2078.5/221151