Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation
For decision-making under costly information acquisition, this provides the first exact algorithm for general stochastic Boolean function evaluation, though experiments are limited to small random instances and a single structured case.
The paper presents the first practical exact algorithm for minimizing expected cost of evaluating propositional formulas under variable costs and probability distributions, demonstrating scalability on random instances and a heart-disease diagnosis case. The problem is proven #P-hard and in PSPACE.
In many decision-making scenarios, acquiring information incurs different costs. We consider the problem of constructing a deterministic evaluation strategy that minimizes the expected cost of evaluating a propositional formula under variable costs and a probability distribution over truth assignments. We present a branch-and-bound algorithm with variable-selection heuristics, pruning, and caching. To the best of our knowledge, it is the first practical exact algorithm for this level of generality. Experiments on random instances demonstrate scalability and quantify the efficiency-quality trade-off of a greedy beam-search variant. We additionally evaluate a structured heart-disease diagnosis instance. Finally, we prove that the problem is $\#P$-hard and contained in $\mathrm{PSPACE}$.