Determining a minimum cost solution for resolving covering-by-pairs problem

A system for determining a minimum cost solution for resolving a covering-by-pairs problem given a plurality of covering nodes, a plurality of branch nodes, and a plurality of edges connecting the covering nodes and the branch nodes, comprising:

• a memory for storing a program for determining the minimum cost solution;
• and
• a processor functionally coupled to the memory, the processor being responsive to computer-executable instructions contained in the program and operative to:
• generate a plurality of vectors, each vector comprising a plurality of genes, each gene having a binary value and corresponding to one of the covering nodes, the binary value of each gene indicating whether the corresponding covering node is a selected covering node included in a proposed solution or a non-selected covering node not included in the proposed solution,
• for each vector in the plurality of vectors, determine whether the selected covering nodes cover the branch nodes,
• responsive to determining that the selected covering nodes do not cover the branch nodes, complete each vector so that the selected covering nodes cover the branch nodes,
• responsive to determining that selected covering nodes cover the branch nodes or to completing the vector, remove redundant covering nodes from each vector,
• insert the vectors into a current population, and
• generate a new population by evolving the current population for at least one generation, the minimum cost solution comprising the vector with a lowest cost from the new population.

A non-transitory computer-readable medium having instructions stored thereon for execution by a processor to provide a method for determining a minimum cost solution for resolving a covering-by-pairs problem given a plurality of covering nodes, a plurality of branch nodes, and a plurality of edges connecting the covering nodes and the branch nodes, the method comprising:

• generating a plurality of vectors, each vector comprising a plurality of genes, each gene having a binary value and corresponding to one of the covering nodes, the binary value of each gene indicating whether the corresponding covering node is a selected covering node included in a proposed solution or a non-selected covering node not included in the proposed solution;
• for each vector in the plurality of vectors, determining whether the selected covering nodes cover the branch nodes;
• responsive to determining that the selected covering nodes do not cover the branch nodes, completing each vector so that the selected covering nodes cover the branch nodes;
• responsive to determining that selected covering nodes cover the branch nodes or to completing the vector, removing redundant covering nodes from each vector;
• inserting the vectors into a current population;
• and
• generating a new population by evolving the current population for at least one generation, the minimum cost solution comprising the vector with a lowest cost from the new population.