| Title:
|
Binary integer programming solution for troubleshooting with dependent actions (English) |
| Author:
|
Lín, Václav |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 (print) |
| ISSN:
|
1805-949X (online) |
| Volume:
|
53 |
| Issue:
|
3 |
| Year:
|
2017 |
| Pages:
|
493-512 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
binary integer programming |
| Keyword:
|
decision-theoretic troubleshooting |
| MSC:
|
90B25 |
| MSC:
|
90C10 |
| MSC:
|
90C90 |
| idZBL:
|
Zbl 06819620 |
| idMR:
|
MR3684682 |
| DOI:
|
10.14736/kyb-2017-3-0493 |
| . |
| Date available:
|
2017-11-12T09:45:08Z |
| Last updated:
|
2018-01-10 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/146939 |
| . |
| Reference:
|
[1] Baker, K. R., Trietsch, D.: Principles of Sequencing and Scheduling..John Wiley and Sons, Hoboken, NJ 2009. MR 2964084, 10.1002/9780470451793 |
| Reference:
|
[2] Bixby, R. E.: A brief history of linear and mixed-integer programming computation. |
| Reference:
|
[3] Feige, U., Lovász, L., Tetali, P.: Approximating min-sum set cover..Algorithmica 40 (2004), 219-234. MR 2084361, 10.1007/s00453-004-1110-5 |
| Reference:
|
[4] Heckerman, D., Breese, J. S., Rommelse, K.: Decision-theoretic troubleshooting..Comm. ACM 38 (1995), 49-57. 10.1145/203330.203341 |
| Reference:
|
[5] Jensen, F. V., Kj\aerulff, U., Kristiansen, B., Langseth, H., Skaanning, C., Vomlel, J., Vomlelová, M.: The {SACSO} methodology for troubleshooting complex systems..AI EDAM 15 (2001), 321-333. 10.1017/s0890060401154065 |
| Reference:
|
[6] Jiroušek, R.: Heuristic methods of construction of sequential questionnaire..Kybernetika 11 (1975), 253-270. MR 0411831, 10.1016/b978-0-12-362340-9.50016-1 |
| Reference:
|
[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. |
| Reference:
|
[8] Lín, V.: On Sequencing Problems in the Management of Troubleshooting Operations..PhD Thesis, University of Economics in Prague 2016. MR 3178412 |
| Reference:
|
[9] Munagala, K., Babu, S., Motwani, R., Widom, J.: The pipelined set cover problem..In: Proc.10th International Conference on Database Theory (T. Eiter and L. Libkin, eds.), Springer, Berlin 2005, pp. 83-98. MR 2145992, 10.1007/978-3-540-30570-5_6 |
| Reference:
|
[10] Nemhauser, G. L., Wolsey, L.: Integer and Combinatorial Optimization..John Wiley and Sons, New York 1988. MR 0948455, 10.1002/9781118627372 |
| Reference:
|
[11] Reinelt, G.: The Linear Ordering Problem: Algorithms and Applications..Heldermann Verlag, Berlin 1985. MR 0831936 |
| Reference:
|
[12] Vomlelová, M., Vomlel, J.: Troubleshooting: $\cal NP$-hardness and solution methods..Soft Computing 7 (2003), 357-368. 10.1007/s00500-002-0224-4 |
| . |
