Original title:
Algorithms for single-fault troubleshooting with dependent actions
Authors:
Lín, Václav Document type: Papers Conference/Event: WUPES 2015. Workshop on Uncertainty Processing /10./, Monínec (CZ), 2015-09-16 / 2015-09-19
Year:
2015
Language:
eng Abstract:
We study the problem of single-fault troubleshooting with dependent actions. We propose a binary integer programming formulation for the problem. This can be used to solve the problem directly or to compute lower bounds of optima using linear programming relaxation. We present an optimal dynamic programming algorithm, and three greedy algorithms for computing upper bounds of optima.
Keywords:
algorithms; linear programming relaxation; single-fault troubleshooting Project no.: GA13-20012S (CEP) Funding provider: GA ČR Host item entry: Proceedings of the 10th Workshop on Uncertainty Processing WUPES’15, ISBN 978-80-245-2102-2