Timezone: »

 
Poster
Counting the Optimal Solutions in Graphical Models
Radu Marinescu · Rina Dechter

Wed Dec 11 10:45 AM -- 12:45 PM (PST) @ East Exhibition Hall B + C #179
in Probabilistic Methods -- Graphical Models »

We introduce #opt, a new inference task for graphical models which calls for counting the number of optimal solutions of the model. We describe a novel variable elimination based approach for solving this task, as well as a depth-first branch and bound algorithm that traverses the AND/OR search space of the model. The key feature of the proposed algorithms is that their complexity is exponential in the induced width of the model only. It does not depend on the actual number of optimal solutions. Our empirical evaluation on various benchmarks demonstrates the effectiveness of the proposed algorithms compared with existing depth-first and best-first search based approaches that enumerate explicitly the optimal solutions.

Keywords: Graphical Models · Belief Propagation · Probabilistic Methods · Optimization -> Combinatorial Optimization; Probabilistic Methods
[ Paper]  [ Slides] 

Author Information

Radu Marinescu (IBM Research)
Rina Dechter (UCI)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors