---
title: "Variable and Value Ordering for MPE Search"
authors:
  - "Sajjad Ahmed Siddiqi"
  - "Jinbo Huang"
doi: ""
url: "https://ijcai.org/proceedings/2009/324"
pdf: "https://ijcai.org/proceedings/2009/0324.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "1964-1968"
track: ""
keywords:
---

# Variable and Value Ordering for MPE Search

Sajjad Ahmed Siddiqi, Jinbo Huang

*Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence*, pages 1964-1968.

## Abstract

In Bayesian networks, a most probable explanation (MPE) is a most likely instantiation of all network variables given a piece of evidence. Solving (the decision version of) an MPE query is NP-hard. Recent work proposed a branch-and-bound search algorithm that finds exact solutions to MPE queries, where bounds are computed on a relaxed network obtained by a technique known as node splitting. In this work we study the impact of variable and value ordering on such a search algorithm. We study several heuristics based on the entropies of variables and on the notion of nogoods, and propose a new meta-heuristic that combines their strengths. Experiments indicate that search efficiency is significantly improved, allowing many hard problems to be solved for the first time.Sajjad Ahmed Siddiqi, Jinbo Huang