Geodesic
Binary integer programming solution for troubleshooting with dependent actions
Kybernetika, Tome 53 (2017) no. 3, pp. 493-512 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

We deal with a sequencing problem that arises when there are multiple repair actions available to fix a broken man-made system and the true cause of the system failure is uncertain. The system is formally described by a probabilistic model, and it is to be repaired by a sequence of troubleshooting actions designed to identify the cause of the malfunction and fix the system. The task is to find a course of repair with minimal expected cost. 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 the minimal expected cost using linear programming relaxation. We also present three greedy algorithms for computing initial feasible solutions.
We deal with a sequencing problem that arises when there are multiple repair actions available to fix a broken man-made system and the true cause of the system failure is uncertain. The system is formally described by a probabilistic model, and it is to be repaired by a sequence of troubleshooting actions designed to identify the cause of the malfunction and fix the system. The task is to find a course of repair with minimal expected cost. 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 the minimal expected cost using linear programming relaxation. We also present three greedy algorithms for computing initial feasible solutions.
DOI : 10.14736/kyb-2017-3-0493
Classification : 90B25, 90C10, 90C90
Keywords: binary integer programming; decision-theoretic troubleshooting 
@article{10_14736_kyb_2017_3_0493,
     author = {L{\'\i}n, V\'aclav},
     title = {Binary integer programming solution for troubleshooting with dependent actions},
     journal = {Kybernetika},
     pages = {493--512},
     year = {2017},
     volume = {53},
     number = {3},
     doi = {10.14736/kyb-2017-3-0493},
     mrnumber = {3684682},
     zbl = {06819620},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-3-0493/}
}
TY  - JOUR
AU  - Lín, Václav
TI  - Binary integer programming solution for troubleshooting with dependent actions
JO  - Kybernetika
PY  - 2017
SP  - 493
EP  - 512
VL  - 53
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-3-0493/
DO  - 10.14736/kyb-2017-3-0493
LA  - en
ID  - 10_14736_kyb_2017_3_0493
ER  - 
%0 Journal Article
%A Lín, Václav
%T Binary integer programming solution for troubleshooting with dependent actions
%J Kybernetika
%D 2017
%P 493-512
%V 53
%N 3
%U http://geodesic.mathdoc.fr/articles/10.14736/kyb-2017-3-0493/
%R 10.14736/kyb-2017-3-0493
%G en
%F 10_14736_kyb_2017_3_0493
Lín, Václav. Binary integer programming solution for troubleshooting with dependent actions. Kybernetika, Tome 53 (2017) no. 3, pp. 493-512. doi: 10.14736/kyb-2017-3-0493

Cité par Sources :