- Technical Program
- Workshops & Tutorials
- At a glance
- Doctoral Consortium
- Opening & Reception
- Best Papers from Sister Conferences Track
- IJCAI Video Track
- Trading Agent Competion (TAC)
- IJCAI-11 Awards
- Funding Opportunities for International Research Collaborations
- General Game Playing Competition
- Banquet
- Ramon Llull Session
- Industry Day
- Closing Event
- List of Accepted Papers
- Poster Boards

Pairwise decomposition for combinatorial optimization in graphical models

AurĂ©lie Favier and Simon de Givry

We propose a new additive decomposition of probability tables that preserves equivalence of the joint distribution while reducing the size of the potentials, without adding extra variables. We reformulate the problem of finding the Most Probable Explanation (MPE) in belief networks into a Weighted Constraint Satisfaction Problem (WCSP). Our pairwise decomposition allows to replace a cost function with smaller-arity cost functions. The resulting pairwise decomposed WCSP is then easier to be solved using state-of-the-art WCSP techniques. Although testing pairwise decomposition is equivalent to testing pairwise independence in the original belief network, we show an efficient way to do it in the WCSP framework, and to enforce it, even in the presence of hard constraints (i.e. determinism). Furthermore, after enforcing pairwise decomposition, we can still infer valuable information from the resulting nonbinary cost functions by projecting&subtracting them on binary cost functions. We observed very large improvements using pairwise decomposition and project&subtract compared to the current state-of-the-art solvers on two difficult benchmarks used in the UAI'08 MPE Evaluation contest.