Patent ID: 8190547

Claim:
A computer-implemented method of exploring a search space of potential solutions to an optimization problem, the method performed by a computing device comprising at least a processor, memory, and a storage, the method comprising: sorting, by the processor, the search space according to a first object function, the first objective function being more computationally expensive and more computationally efficient than a second objective function; performing, by the processor, a bounded depth-first search over the search space to find intermediate sub-solutions to the problem using the first object function; storing, by the processor, K best sub-solutions in the storage while performing the depth-first search, and storing intermediate sub-solutions from the storage in a probabilistic cache, wherein the probabilistic cache stores the sub-solutions in the form of entries, each entry comprising indicia of a sub-solution and an associated cost, and wherein a new entry in the probabilistic cache is stored by randomly selecting a subset of entries in the probabilistic cache and replacing an entry in the subset with the new entry by comparing a cost of the new entry with the costs of the entries in the subset; finding L best partial results using sub-solutions from the storage, where result quality that would be provided by a sub-solution is measured using the second objective function; and storing at least a subset of the L best partial results in the memory of a of the computing device, wherein the subset of the L best partial results is then used as the search space and the sorting, performing, storing, and finding are performed accordingly to produce final solutions to the optimization problem.