1. |
|
|
2. |
|
|
3. |
|
|
4. |
|
|
5. |
|
|
6. |
|
|
7. |
- Demirović, Emir, et al.
(författare)
-
Pseudo-Boolean Reasoning About States and Transitions to Certify Dynamic Programming and Decision Diagram Algorithms
- 2024
-
Ingår i: 30th International Conference on Principles and Practice of Constraint Programming (CP 2024). - 1868-8969. - 9783959773362 ; 307
-
Konferensbidrag (refereegranskat)abstract
- Pseudo-Boolean proof logging has been used successfully to provide certificates of optimality from a variety of constraint- and satisifability-style solvers that combine reasoning with a backtracking or clause-learning search. Another paradigm, occurring in dynamic programming and decision diagram solving, instead reasons about partial states and possible transitions between them. We describe a framework for generating clean and efficient pseudo-Boolean proofs for these kinds of algorithm, and use it to produce certifying algorithms for knapsack, longest path, and interval scheduling. Because we use a common proof system, we can also reason about hybrid solving algorithms: we demonstrate this by providing proof logging for a dynamic programming based knapsack propagator inside a constraint programming solver.
|
|