Parallel processing for combinatorial optimization
AssigneeNVIDIA Corporation
InventorsMehmet Akif Çördük, Frank Joseph Eaton, Alexandre Jacques Antoine Fender, Hugo Linsenmaier, Shankara Rao Thejaswi Nanditale
Life of this patent
Estimating the term…
Abstract
In various examples, solutions to combinatorial optimization problems are determined using a plurality of solvers executing in parallel. In an embodiment, the plurality of solvers executed in parallel perform one or more search algorithms. Furthermore, in such embodiments, the operations of the one or more search algorithms are also executed in parallel.
Claims25
A processor comprising:
- one or more circuits to:
- generate a first set of solutions within a search space associated with a combinatorial optimization problem;
- operate a set of compute engines to determine, in parallel using at least one parallel processing unit, a set of improvements to the first set of solutions;
- determine a subset of improvements of the set of improvements satisfy a set of constraints associated with the combinatorial optimization problem;
- transmit data causing the subset of improvements to be applied to the first set of solutions to generate a second set of solutions within the search space;
- and
- provide a solution corresponding to the second set of solutions based at least in part on a value computed based at least in part on a objective function that optimizes one or more features of the combinatorial optimization problem.
A system comprising:
- one or more processing units;
- and
- one or more memory units storing instructions that, as a result of being executed by the one or more processing units, cause the one or more processing units to execute operations comprising:
- initiating a set of compute engines on a set of parallel processing units, the set of compute engines being assigned a first set of solutions to a combinatorial optimization problem;
- transmit data causing the set of parallel processing units to execute the set of compute engines in parallel to determine a set of improvements to apply to the first set of solutions to generate a second set of solutions to the combinatorial optimization problem;
- and
- determining a solution to the combinatorial optimization problem based at least in part on an objective function computed based at least in part on the second set of solutions, where the objective function optimizes a feature of the combinatorial optimization problem.
A method comprising:
- transmitting data causing a parallel processing unit to execute a plurality of compute engines, to perform, at least substantially in parallel, operations of a search algorithm within a search space of a combinatorial optimization problem;
- and
- obtaining a solution from a compute engine of the plurality of compute engines.
The method of 16, wherein the compute engine comprises at least one of a hill climber, a local optimizer, or a solver.
The method of 16, wherein the combinatorial optimization problem comprises at least one of a traveling salesman problem, a vehicle routing problem, a bin packing problem, or a job shop scheduling problem.
The method of 16, wherein two or more of the operations of the search algorithm are executed at least substantially in parallel by the parallel processing unit.
The method of 16, wherein the parallel processing unit comprises a graphical processing unit.
The method of 16, wherein the operations of the search algorithm comprise an insertion algorithm to generate an initial set of solutions within the search space.
The method of 21, wherein the initial set of solutions are variated by at least modifying a set of hyperparameters associated with the insertion algorithm.
The method of 21, wherein solutions of the initial set of solutions are assigned to compute engines of the plurality of compute engines.
The method of 16, wherein the operations of the search algorithm further comprise a tabu search to avoid local maxima.
The method of 16, wherein compute engines of the plurality of compute engines are assigned a status of a set of statutes based at least in part on a result of the operations of the search algorithm the compute engine is performing.
Dependencies are inferred from the claim text.