Binary integer programming solution for troubleshooting with dependent actions

Václav Lín

Kybernetika (2017)

  • Volume: 53, Issue: 3, page 493-512
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Lín, Václav. "Binary integer programming solution for troubleshooting with dependent actions." Kybernetika 53.3 (2017): 493-512. <http://eudml.org/doc/294728>.

@article{Lín2017,
abstract = {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.},
author = {Lín, Václav},
journal = {Kybernetika},
keywords = {binary integer programming; decision-theoretic troubleshooting},
language = {eng},
number = {3},
pages = {493-512},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Binary integer programming solution for troubleshooting with dependent actions},
url = {http://eudml.org/doc/294728},
volume = {53},
year = {2017},
}

TY - JOUR
AU - Lín, Václav
TI - Binary integer programming solution for troubleshooting with dependent actions
JO - Kybernetika
PY - 2017
PB - Institute of Information Theory and Automation AS CR
VL - 53
IS - 3
SP - 493
EP - 512
AB - 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.
LA - eng
KW - binary integer programming; decision-theoretic troubleshooting
UR - http://eudml.org/doc/294728
ER -

References

top
  1. Baker, K. R., Trietsch, D., 10.1002/9780470451793, John Wiley and Sons, Hoboken, NJ 2009. MR2964084DOI10.1002/9780470451793
  2. Bixby, R. E., A brief history of linear and mixed-integer programming computation 
  3. Feige, U., Lovász, L., Tetali, P., 10.1007/s00453-004-1110-5, Algorithmica 40 (2004), 219-234. MR2084361DOI10.1007/s00453-004-1110-5
  4. Heckerman, D., Breese, J. S., Rommelse, K., 10.1145/203330.203341, Comm. ACM 38 (1995), 49-57. DOI10.1145/203330.203341
  5. Jensen, F. V., Kj, U., Kristiansen, B., Langseth, H., Skaanning, C., Vomlel, J., Vomlelová, M., 10.1017/s0890060401154065, AI EDAM 15 (2001), 321-333. DOI10.1017/s0890060401154065
  6. Jiroušek, R., 10.1016/b978-0-12-362340-9.50016-1, Kybernetika 11 (1975), 253-270. MR0411831DOI10.1016/b978-0-12-362340-9.50016-1
  7. Langseth, H., Jensen, F. V., Heuristics for two extensions of basic troubleshooting., In: SCAI'01 - Proc. Seventh Scandinavian Conference on Artificial Intelligence (H. H. Lund, B. H. Mayoh, J. W. Perram, eds.), IOS Press, Amsterdam 2001, pp. 80-89. 
  8. Lín, V., On Sequencing Problems in the Management of Troubleshooting Operations., PhD Thesis, University of Economics in Prague 2016. MR3178412
  9. Munagala, K., Babu, S., Motwani, R., Widom, J., 10.1007/978-3-540-30570-5_6, In: Proc.10th International Conference on Database Theory (T. Eiter and L. Libkin, eds.), Springer, Berlin 2005, pp. 83-98. MR2145992DOI10.1007/978-3-540-30570-5_6
  10. Nemhauser, G. L., Wolsey, L., 10.1002/9781118627372, John Wiley and Sons, New York 1988. MR0948455DOI10.1002/9781118627372
  11. Reinelt, G., The Linear Ordering Problem: Algorithms and Applications., Heldermann Verlag, Berlin 1985. MR0831936
  12. Vomlelová, M., Vomlel, J., 10.1007/s00500-002-0224-4, Soft Computing 7 (2003), 357-368. DOI10.1007/s00500-002-0224-4

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.