NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Back to Results
New high performance algorithmic solution for diagnosis problemIn this paper we address the problem of generating the minimal diagnosis from the conflicts. This problem can be formulated as the well-known Hitting Set Problem. Our approach starts by mapping the Hitting Set problem into the Integer Programming Problem that enables us, for the first time, a priori determination of the lower and upper bounds on the size for the solution. Based on these bounds, we introduce a new concept of solution window for the problem. We also propose a new branch-and-bound technique that not only is faster than the current techniques in terms of number of operations (by exploiting the structure of the problem) but also, using the concept of window, allows a massive reduction (pruning) in the number of branches. Furthermore, as the branch-and-bound proceeds, the solution window is dynamically updated and narrowed to enable further pruning.
Document ID
20060044371
Acquisition Source
Jet Propulsion Laboratory
Document Type
Conference Paper
External Source(s)
Authors
Fijany, Amir
Vatan, Farrokh
Date Acquired
August 23, 2013
Publication Date
March 5, 2005
Meeting Information
Meeting: IEEE Aerospace Conference
Location: Big Sky, MT
Country: United States
Start Date: March 5, 2005
End Date: March 12, 2005
Distribution Limits
Public
Copyright
Other
Keywords
diagnosis problems
integer programming

Available Downloads

There are no available downloads for this record.
No Preview Available