Sequential testing in sparse precedence networks
Rostami S, Rostami A (2026)
Publication Type: Journal article
Publication year: 2026
Journal
DOI: 10.1016/j.ejor.2026.04.014
Abstract
We address the problem of sequentially testing the components of an n-out-of-n system to verify its operational status at minimum expected cost. Such a system is operational if all n components pass their tests; otherwise, it is non-operational. Each test has a given success probability, incurs a fixed cost, and may be subject to precedence constraints. Without precedence dependencies or when these form a series–parallel network, the problem can be solved in polynomial time; however, it becomes strongly NP-hard for general graphs. Current state-of-the-art methods perform well for dense networks but struggle with sparse ones. To address this limitation, we derive new theoretical results and propose an exact branch-and-bound algorithm, where at each level of the search tree, the algorithm selects the next test in the sequence. At each node, we solve a series–parallel relaxation in polynomial time to obtain a tight lower bound. Extensive computational experiments show that our method significantly extends the size of solvable instances and reduces runtimes, establishing a new state-of-the-art. Our results can be directly extended to other optimization problems, including single-machine total weighted completion time scheduling.
Involved external institutions
France (FR)How to cite
APA:
Rostami, S., & Rostami, A. (2026). Sequential testing in sparse precedence networks. European Journal of Operational Research. https://doi.org/10.1016/j.ejor.2026.04.014
MLA:
Rostami, Salim, and Ali Rostami. "Sequential testing in sparse precedence networks." European Journal of Operational Research (2026).
BibTeX: Download