Exploiting Combinatorial Structure in Constraint Programming: ...

on YouTube ↗47m

" summary

Shows how constraint programming yields exact and approximate counts (19 solutions and 10/19 marginals in a regular constraint DAG example), gives a practical weighted counting route for alldifferent via Rasmussen-style estimators plus domain filtering, and computes edge marginals and MST-cost counts using the matrix-tree theorem. Describes the CP-BP framework that mixes belief propagation with CP to produce marginals for min-entropy branching, near-uniform sampling, and neural integration for training or constrained decoding. Worth watching if implementation details and trade-offs are needed.

AI-written summary · about

" chapters (11)

1. 0:00Introduction to CP goals
2. 1:02Structure in CP models
3. 3:25Counting and inference
4. 7:38Counting with regular constraints
5. 11:56Marginal computation
6. 15:01Estimators for all-different
7. 20:55Spanning tree constraints
8. 27:42Domain relaxation
9. 28:33Belief propagation in CP
10. 34:32Neurosymbolic AI applications
11. 39:20Conclusion and Q&A

" related talks

• 37mSolving Marginal MAP Exactly by Probabilistic Circuit TransformationsYooJung Choi · Probabilistic Circuits and Logic 2023
• 01h 03mLogic and Probabilistic Circuits 2YooJung Choi · Logic and Algorithms in Database Theory and AI Boot Camp
• 46mConstrained Sampling and CountingMoshe Vardi · Uncertainty in Computation 2016
• 41mCounting Solutions to Random CNF FormulasLeslie Ann Goldberg · Computational Phase Transitions (Simons Institute, 2020)
• 51mRandom Projections for Probabilistic InferenceStefano Ermon · Uncertainty in Computation 2016
• 20mStatic Posterior Inference of Bayesian Probabilistic Programming via Polynomial SolvingGuanyan Li, Peixin Wang, Hongfei Fu, Tengshun Yang, C.-H. Luke Ong · PLDI 2024
• 29mSampling Algorithms for Combinatorial Pure ExplorationAnupam Gupta · Optimization, Statistics and Uncertainty
• 47mSuccinct Representations and Efficient Algorithms Based on Linear ProgrammingSudipto Guha · Workshop on Succinct Data Representations and Applications (Simons Institute Big Data 2013)