6533b7dafe1ef96bd126ecaf
RESEARCH PRODUCT
New Encodings of Pseudo-Boolean Constraints into CNF
Olivier RousselYacine BoufkhadOlivier Bailleuxsubject
Discrete mathematics[INFO.INFO-CC]Computer Science [cs]/Computational Complexity [cs.CC]Polynomial021103 operations researchUnit propagation[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS]0211 other engineering and technologies[INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS]02 engineering and technologyComputer Science::Computational ComplexityExpressive powerExponential functionCombinatorics[ INFO.INFO-CC ] Computer Science [cs]/Computational Complexity [cs.CC]Encoding (memory)0202 electrical engineering electronic engineering information engineeringLocal consistency020201 artificial intelligence & image processingPoint (geometry)[INFO.INFO-CC] Computer Science [cs]/Computational Complexity [cs.CC][ INFO.INFO-DS ] Computer Science [cs]/Data Structures and Algorithms [cs.DS]Mathematicsdescription
International audience; This paper answers affirmatively the open question of the existence of a polynomial size CNF encoding of pseudo-Boolean (PB) constraints such that generalized arc consistency (GAC) is maintained through unit propagation (UP). All previous encodings of PB constraints either did not allow UP to maintain GAC, or were of exponential size in the worst case. This paper presents an encoding that realizes both of the desired properties. From a theoretical point of view, this narrows the gap between the expressive power of clauses and the one of pseudo-Boolean constraints.
| year | journal | country | edition | language |
|---|---|---|---|---|
| 2009-06-30 |