A lower bound on CNF encodings of the at-most-one constraint.
Petr KuceraPetr SavickýVojtech VorelPublished in: CoRR (2017)
Keyphrases
- lower bound
- upper bound
- branch and bound algorithm
- sat solving
- branch and bound
- objective function
- lower and upper bounds
- boolean functions
- sat encodings
- sat instances
- np hard
- linear programming relaxation
- lower bounding
- boolean satisfiability
- normal form
- worst case
- upper and lower bounds
- sufficiently accurate
- combinatorial problems
- linear constraints
- optimal solution