Cost-Optimal Decision Diagrams for Stochastic Boolean Function Evaluation

The paper presents a novel branch-and-bound algorithm for the cost-optimal evaluation of stochastic Boolean functions, addressing the challenge of minimizing expected evaluation costs under variable costs and probabilistic truth assignments. This marks the first practical exact algorithm capable of handling such generality, with experimental results demonstrating its scalability and efficiency, alongside a greedy beam-search variant. The findings are significant for practitioners as they provide a new method for decision-making processes in AI applications where cost and efficiency are critical, particularly in domains like medical diagnosis.