Research map / Learning theory and algorithms / Combinatorial and search optimization
Counting the Optimal Solutions in Graphical Models
Radu Marinescu, Rina Dechter
Read the paperCheck your idea against 137,217 papers
AI-extracted. The measured effects below were read by AI from the paper's full text (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use AOBB instead of explicit enumeration with BnB | #opt solver · grid 64 vars, p=0.80 | CPU time (s): 206.02 -> 0.09 | Improved |
| use AOBB instead of A* search | #opt solver · grid 196 vars, p=0.20 | CPU time (s): 2887.35 -> 199.32 | Improved |
| use AOBB instead of BE | #opt solver · grid 196 vars, p=0.20 | CPU time (s) | Improved |
| use AOBB instead of A* | #opt solver · random 60 vars, p=0.80 | CPU time (s): 370.66 -> 0.35 | Improved |
| use BE instead of search on small induced width | #opt solver · random 60 vars, p=0.20 | CPU time (s): 0.33 -> 5.85 | Hurt |
| use AOBB instead of BnB on SPOT5/ISCAS | #opt solver · ISCAS c432 | CPU time (s): 1050.67 -> 0.07 | Improved |
| use AOBB instead of BE on SPOT5 instance 29 | #opt solver · SPOT5 29 | CPU time (s): 187.78 -> 7.29 | Improved |
| use BE instead of AOBB on low-width SPOT5 1502 | #opt solver · SPOT5 1502 | CPU time (s): 0.08 -> 0.03 | Improved |
| increase perturbation p (more optimal solutions) | AOBB · grid 196 vars | CPU time (s): 199.32 -> 62.13 | Improved |
| increase perturbation p from 0.50 to 0.80 | AOBB · grid 196 vars | CPU time (s): 62.13 -> 113.34 | Mixed |
| increase perturbation p (more optimal solutions) | AOBB · random 120 vars | CPU time (s): 1815.84 -> 182.24 | Improved |
| increase number of optimal solutions | A* and BnB · grid and random | instances solved | Hurt |
Closest papers by meaning
- Maximum Persistency via Iterative Relaxed Inference in Graphical Models (TPAMI 2017 · similarity 0.87)
- Maximum Model Counting (AAAI 2017 · similarity 0.87)
- Partial Optimality by Pruning for MAP-Inference with General Graphical Models (TPAMI 2016 · similarity 0.86)
- Anytime Best+Depth-First Search for Bounding Marginal MAP (AAAI 2017 · similarity 0.86)
- A Novel Approach for Constrained Optimization in Graphical Models (NeurIPS 2020 · similarity 0.86)
- Anytime Recursive Best-First Search for Bounding Marginal MAP (AAAI 2019 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.
