System for solving diagnosis and hitting set problems

A method for calculating a minimal Hitting Set as set forth in claim 8, wherein the act of splitting a label further comprises acts of:

• on label λ=(M, Tin, Tout), if the jth column of the matrix M is an all-one column, then changing the label λ to the label ({ }, Tin∪{{tilde over (j)}}, Tout), where ∪ denotes the union of two sets, { } is an empty matrix and {tilde over (j)} is a corresponding column in the original matrix;
• on label λ=(M, Tin, Tout), if the matrix M has a row of weight one, with 1 as its jth component, then changing the label λ to the label (Remove—1 [M, j], Tin∪{{tilde over (j)}}, Tout) where ∪ denotes the union of two sets, {tilde over (j)} is the corresponding column in the original matrix, and Remove—1 [M, j] denotes a sub-matrix of M obtained by deleting the jth column of M and deleting all rows of M that correspond with non-zero components of that column;
• on label λ=(M, Tin, Tout), if the matrix M has an all-one row, then deleting that row;
• on label λ=(M, Tin, Tout), if jth column of the matrix M is an all-zero column, then changing the label λ to the label (Remove—0 [M, j], Tin, Tout∪{{tilde over (j)}}), where ∪ denotes the union of two sets, {tilde over (j)} is the corresponding column in the original matrix, and Remove—0 [M, j] denotes a sub-matrix of M obtained by deleting the jth column of M;
• on label λ=(M, Tin, Tout), if the matrix M has two equal rows, then deleting one of them;
• and
• repeating the acts of claim 9 until all of the acts of claim 9 are exhausted.

A computer program product for calculating a minimal Hitting Set from a collection of sets, the computer program product comprising computer-readable instruction means stored on a computer-readable medium for causing a computer to:

• receive information regarding the collection of sets from the system;
• create an incidence matrix of the collection of sets;
• create nodes from the incidence matrix such that each node is a node in a search tree and has a label that includes a sub-matrix of the incidence matrix, and two disjoint subsets of the columns of the incidence matrix;
• calculate an upper bound and calculating a lower bound for each label, where the upper bound and lower bound define a range of solutions for the minimal Hitting Set;
• and
• determine whether each label has any child nodes or is a leaf node without any child nodes;
• if the label does not have any child nodes, then stop and designate the label as a leaf node;
• if the label does have a child node, splitting the label to create two new labels;
• repeating operations of calculating and determining until all labels have been designated as leaf nodes;
• determining a solution of the Hitting Set with information gathered from leaf nodes;
• and
• providing an indication of the Hitting set to a user.

A computer program product for calculating a minimal Hitting Set as set forth in claim 17, wherein when splitting a label, the computer program product further comprises instruction means for causing a computer to perform operations of:

• on label λ=(M, Tin, Tout), if the jth column of the matrix M is an all-one column, then changing the label λ to the label ({ }, Tin∪{{tilde over (j)}}, Tout), where ∪ denotes the union of two sets, { } is an empty matrix and {tilde over (j)} is a corresponding column in the original matrix;
• on label λ=(M, Tin, Tout), if the matrix M has a row of weight one, with 1 as its jth component, then changing the label λ to the label (Remove—1 [M, j], Tin∪{{tilde over (j)}}, Tout) where ∪ denotes the union of two sets, {tilde over (j)} is the corresponding column in the original matrix, and Remove—1 [M, j] denotes a sub-matrix of M obtained by deleting the jth column of M and deleting all rows of M that correspond with non-zero components of that column;
• on label λ=(M, Tin, Tout), if the matrix M has an all-one row, then deleting that row;
• on label λ=(M, Tin, Tout), if jth column of the matrix M is an all-zero column, then changing the label λ to the label (Remove—0 [M, j], Tin, Tout∪{{tilde over (j)}}), where ∪ denotes the union of two sets, {tilde over (j)} is the corresponding column in the original matrix, and Remove—0 [M, j] denotes a sub-matrix of M obtained by deleting jth column of M;
• on label λ=(M, Tin, Tout), if the matrix M has two equal rows, then deleting one of them;
• and
• repeating operations of claim 19 until all of the operations of claim 19 are exhausted.

A computer program product for calculating a minimal Hitting Set as set forth in claim 18, further comprising instruction means for causing a computer to perform an operation of applying a Branch-and-Bound technique to the incidence matrix A to find an optimal solution for the problem, comprising operations of:

• initializing a label λ0 as λ0=Rules*[{A, { }, { }}], where Rules* denotes applying and repeating the operations of claim 19 until all of the operations of claim 19 are exhausted;
• initializing a set of labels as {λ0};
• initializing a value of the upper bound U as the upper bound of λ0;
• initializing a solution set as the upper bound set of λ0;
• choosing a label λ from the set of labels;
• deleting λ from the set of labels;
• computing U1 as the upper bound of λ and its corresponding upper bound set;
• if U1<U, then changing the value of U to U1 and the value of the solution set to the upper bound set;
• if the label λ is not a leaf, then splitting λ to labels λ0 and λ1 and adding the new labels λ0 and λ1 to the set of labels;
• if the set of labels is not empty, repeating the operations of choosing a label λ through the operation of repeating the operations;
• if the set of labels is empty, then the outputting is the solution set and stopping.

A computer program system for calculating a minimal diagnosis set from a collection of conflict sets, the computer system being configured to perform operations of:

• creating an incidence matrix of the collection of sets;
• creating nodes from the incidence matrix such that each node is a node in a search tree and has a label that includes a sub-matrix of the incidence matrix, and two disjoint subsets of the columns of the incidence matrix;
• calculating an upper bound and calculating a lower bound for each label, where the upper bound and lower bound define a range of solutions for the minimal Hitting Set;
• and
• determining whether each label has any child nodes or is a leaf node without any child nodes;
• if the label does not have any child nodes, then stop and designate the label as a leaf node;
• if the label does have a child node, splitting the label to create two new labels;
• repeating acts of calculating and determining until all labels have been designated as leaf nodes;
• determining a solution of the Hitting Set with information gathered from leaf nodes;
• and
• providing an indication of the Hitting set to a user.