US 2010/0138373 A1 · Maximizing Diversity in a Subset of Elements Utilizing GRASP With Path Relinking

Abstract

Methods, systems, and computer-readable media for maximizing diversity in a subset of elements selected from a set of elements are provided. An algorithm that combines the GRASP and path relinking heuristics is utilized to find an approximate solution to a max-min diversity problem modeled from the set of elements. The GRASP heuristic is applied to the set of elements for a number of iterations to generate a set of feasible solutions, and a best solution is determined from the set. The path relinking heuristic is then applied between a pair of solutions in the set of feasible solutions to generate a candidate solution. If the candidate solution is better than the best solution, then the best solution is replaced with the candidate solution, and the process is repeated until the path relinking heuristic has been applied between each pair of solutions in the set of feasible solutions.

Claims20

Dependent claims

A method of selecting a plurality of routes between two nodes in a telecommunications network from a set of possible routes between the two nodes such that a diversity amongst the plurality of routes is maximized, the method comprising:

determining the set of possible routes between the two nodes in the telecommunications network;
modeling a max-min diversity problem (“MMDP”) for selecting the plurality of routes from the set of possible routes such that a minimum diversity between the plurality of routes is maximized;
finding an approximate solution to the MMDP utilizing a hybrid between a greedy randomized adaptive search procedure (“GRASP”) heuristic and a path relinking heuristic;
and
selecting the plurality of routes based on the approximate solution.

2 more elements

A system for finding an approximate solution to a max-min diversity problem (“MMDP”), comprising:

a memory for storing a program containing computer-executable instructions for finding an approximate solution to the MMDP;
and
a processing unit functionally coupled to the memory, the processing unit being responsive to the computer-executable instructions and operative to:
apply a greedy randomized adaptive search procedure (“GRASP”) heuristic for a number of iterations to generate a set of feasible solutions,
determine a best solution from the set of feasible solutions,
apply a path relinking heuristic between a pair of solutions in the set of feasible solutions to generate a first candidate solution,
determine if the first candidate solution is better than the best solution,
upon determining that the first candidate solution is better than the best solution, replace the best solution with the first candidate solution, and
designate the best solution as the approximate solution.

6 more elements

A computer-readable storage medium having computer executable instructions stored thereon that, when executed by a computer, cause the computer to:

apply a greedy randomized adaptive search procedure (“GRASP”) heuristic for a number of iterations to generate a set of feasible solutions to a max-min diversity problem;
determine a best solution from the set of feasible solutions;
apply a path relinking heuristic between a pair of solutions in the set of feasible solutions to generate a first candidate solution;
determine if the first candidate solution is better than the best solution;
and
upon determining that the first candidate solution is better than the best solution, replace the best solution with the first candidate solution.

3 more elements

Dependencies are inferred from the claim text.

Maximizing Diversity in a Subset of Elements Utilizing GRASP With Path Relinking

Life of this patent

Maximizing Diversity in a Subset of Elements Utilizing GRASP With Path Relinking

Life of this patent

Abstract

Claims20