Search papers, labs, and topics across Lattice.
This paper addresses the challenge of minimizing the expected cost of evaluating stochastic Boolean functions by developing a branch-and-bound algorithm that incorporates variable-selection heuristics, pruning, and caching. The significance of this work lies in its establishment as the first practical exact algorithm capable of handling a broad range of scenarios involving variable costs and probabilistic truth assignments. Experimental results indicate that the proposed method is scalable and effectively balances efficiency with quality, particularly in applications such as heart-disease diagnosis, while also proving the problem's computational complexity as $\#P$-hard and within $\mathrm{PSPACE}$.
The first practical exact algorithm for cost-sensitive evaluation of stochastic Boolean functions reveals a surprising efficiency-quality trade-off that could transform decision-making processes in complex scenarios.
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}$.
