Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation

In many real-world scenarios—such as medical diagnosis, system testing, or classification—gathering information (observing variables) incurs different costs. The Stochastic Boolean Function Evaluation (SBFE) problem asks: what is the optimal sequence of observations to determine the truth value of a Boolean formula while minimizing the total expected cost? While previous research has explored special cases or approximation methods, this paper addresses the need for a practical, exact algorithm capable of handling general Boolean formulas and complex probability distributions.

The authors propose a branch-and-bound algorithm to construct optimal decision diagrams. Their approach incorporates several key techniques to improve scalability:

• Variable-Selection Heuristics: Intelligent ordering of variables to prune the search space effectively.
• Pruning and Caching: Using lower-bound estimates and memoization of subproblem solutions to avoid redundant computations.
• Beam Search: A greedy variant that provides an efficiency-quality trade-off for instances where finding the absolute optimum is too time-consuming.

The algorithm is evaluated on both random instances and a structured heart-disease diagnosis problem. Additionally, the authors provide theoretical complexity results, establishing that the problem is #P-hard and resides within PSPACE.

Findings and Significance

The study demonstrates that the proposed algorithm can solve instances that were previously intractable. By moving beyond restricted cost functions or uniform probability assumptions, the authors provide a robust framework for decision-making under uncertainty. The #P-hardness result clarifies the inherent difficulty of the problem, explaining why exact solutions are computationally demanding and justifying the use of heuristics and pruning in the proposed algorithm.