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 dDNNF 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 effificiency of state-of-the-art solvers by orders of magnitude