---
title: "A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT"
authors:
  - "Knot Pipatsrisawat"
  - "Adnan Darwiche"
doi: ""
url: "https://ijcai.org/proceedings/2009/104"
pdf: "https://ijcai.org/proceedings/2009/0104.pdf"
venue: "Proceedings of the Twenty-First International Joint Conference on Artificial Intelligence"
year: 2009
pages: "590-594"
track: ""
keywords:
---

# A New d-DNNF-Based Bound Computation Algorithm for Functional E-MAJSAT

Knot Pipatsrisawat, Adnan Darwiche

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

## Abstract

We present a new algorithm for computing upper bounds for an optimization version of the EMAJSAT problem called functional E-MAJSAT. The algorithm utilizes the compilation language d- DNNF which underlies several state-of-the-art algorithms for solving related problems. This bound computation can be used in a branch-and-bound solver for solving functional E-MAJSAT. We then present a technique for pruning values from the branch-and-bound search tree based on the information available after each bound computation. We evaluated the proposed techniques in a MAP solver and a probabilistic conformant planner. In both cases, our experiments showed that the new techniques improved the efficiency of state-of-the-art solvers by orders of magnitude.Knot Pipatsrisawat, Adnan Darwiche