Parallel Processing for Solution Space Partitions

Abstract

Systems, devices, methods, and computer-readable media are disclosed for utilizing group theoretic techniques to enable data exchange between a supervisory central processing unit (CPU) and a group of graphical processing units (GPUs). The CPU may be configured to utilize a tabu search metaheuristic to explore a solution space to determine an optimal solution to an optimization problem. More specifically, the CPU may determine a fragmentation of a solution space that yields multiple partitions of the solution space and may assign each partition to a respective GPU configured to calculate a computational result. The CPU may then determine a new fragmentation of the solution space based on the computational results received from the GPUs that yields new partitions of the solution space and may assign each new partition to a respective GPU configured to again generate a computational result based on its assigned new partition. The CPU may continue to determine new fragmentations based on the computational results of the GPUs until stopping criteria are satisfied and a timely, high-quality solution to the optimization problem is determined.

That which is claimed is: 
     
         1 . A method, comprising:
 determining a set of variables associated with an optimization problem;   determining a function associated with the optimization problem, wherein the function is to be optimized based at least in part on the set of variables;   determining an initial solution to the optimization problem, wherein determining the initial solution comprises determining an initial set of values of the set of variables and determining an initial value of the function based at least in part on the initial set of values;   determining a neighborhood of solutions associated with the initial solution;   selecting a first solution in the neighborhood of solutions as a current solution of the optimization problem;   determining one or more additional solutions to the optimization problem based at least in part on the current solution, wherein the at least first solution is determined by a first graphical processing unit (GPU) and at least a second solution is determined by a second GPU different from the first GPU, and wherein the determining further comprises allocating to the first solution for determination by the first GPU and the allocating the second solution for determination by the second GPU;   including the one or more additional solutions in a set of elite solutions; and   determining that a second solution in the set of elite solutions is a final solution to the optimization problem, wherein determining that the second solution is a final solution comprises:
 determining a final set of values of the set of variables, the final set of values being associated with the second solution; 
 determining a final value of the function based at least in part on the final set of values; and 
 determining that the final value of the function optimizes the function for each solution in the set of elite solutions. 
   
     
     
         2 . The method of  claim 1 , wherein determining the one or more additional solutions comprises:
 determining a second neighborhood of solutions associated with the first solution;   selecting a first additional solution of the one or more additional solutions as a new current solution; and   determining the second solution based at least in part the first additional solution.   
     
     
         3 . The method of  claim 2 , wherein determining the second neighborhood of solutions comprises determining that each solution in the second neighborhood of solutions preserves one or more characteristics of the first solution. 
     
     
         4 . The method of  claim 3 , wherein the first solution is represented as a permutation, and wherein the one or more characteristics of the first solution comprise at least one of a cycle structure of the permutation or a sub-path of the permutation. 
     
     
         5 . The method of  claim 1 , further comprising:
 receiving one or more carrier constraints of a carrier, wherein the carrier is configured to transport one or more vehicles;   receiving one or more vehicle attributes associated with one or more vehicles available to be transported by the carrier;   determining one or more optimal solution sets based at least in part on the one or more carrier constraints and the one or more vehicle attributes based at least in part on determining that the final value of the function optimizes the function for each solution in the set of elite solutions; and   providing the one or more optimal solution sets to a user device.   
     
     
         6 . The method of  claim 5 , further comprising:
 receiving from a user device a modification to the optimal solution, wherein modification comprises at least one of adding, deleting, accepting, trading, swapping, rejecting, and modifying at least one of the one or more vehicles comprised in the one or more optimal solution sets.   
     
     
         7 . The method of  claim 5 , wherein each of the one or more vehicles available to be transported by the carrier is associated with an optimized route segment for transporting each respective vehicle from a pick-up location to a delivery location. 
     
     
         8 . The method of  claim 5 , further comprising:
 assigning a selected optimal solution set to the carrier;   generating a schedule for the carrier to transport each vehicle included in the selected optimal solution set; and   providing instructions for dispatching each vehicle included in the selected optimal solution set to be transported by the carrier according to the schedule.   
     
     
         9 . The method of  claim 5 , wherein the one or more optimal solution sets are provided to a user device for selection via an online marketplace listing over a wireless network. 
     
     
         10 . A method, comprising:
 fragmenting a solution space associated with an optimization problem into a plurality of cells, wherein each cell comprises a respective disjoint subset of the solution space;   selecting a first cell of the plurality of cells;   fragmenting the first cell into a plurality of sub-cells;   determining a respective initial solution to the optimization problem for each of the plurality of sub-cells;   launching a respective processing thread for each of the plurality of sub-cells; and   executing each respective processing thread at least partially in parallel, wherein executing each respective processing thread comprises determining a respective elite solution to the optimization using the respective initial solution associated with the corresponding sub-cell of the plurality of sub-cells.   
     
     
         11 . The method of  claim 10 , further comprising:
 determining a cross-cell transversal;   determining that processing performed by each respective processing thread should be diversified from the first cell to a second cell of the plurality of sub-cells; and   selecting the second cell based at least in part on the cross-cell transversal.   
     
     
         12 . The method of  claim 10 , further comprising:
 determining that a threshold number of processing iterations have been performed; and   selecting a particular elite solution as a final solution to the optimization problem.   
     
     
         13 . A system, comprising:
 a central processing unit (CPU);   a graphical processing unit (GPU) comprising a plurality of arithmetic logic units (ALUs);   at least one memory storing computer-executable instructions; and   one or more buses that operatively couple the CPU, the GPU, and the at least one memory,   wherein the CPU is configured to access the at least one memory via at least one bus of the one or more buses and execute the computer-executable instructions to:
 fragment a solution space associated with an optimization problem into a plurality of cells, wherein each cell comprises a respective disjoint subset of the solution space; and 
 cause the GPU to launch a respective GPU thread to process a corresponding cell of the plurality of cells, wherein each respective GPU thread utilizes a corresponding ALU of the plurality of ALUs to process the corresponding cell to determine a respective solution to the optimization problem. 
   
     
     
         14 . The system of  claim 13 , wherein the CPU is further configured to execute the computer-executable instructions to:
 launch a plurality of kernels on the at least one memory, wherein each kernel is associated with a corresponding respective GPU thread.   
     
     
         15 . The system of  claim 13 , wherein the plurality of cells is a first plurality of cells, and wherein the CPU is further configured to execute the computer-executable instructions to:
 fragment the solution space into a second plurality of cells that is different from the first plurality of cells based at least in part on the respective solution to the optimization problem determined by each respective GPU thread.   
     
     
         16 . The system of  claim 13 , wherein the instructions further comprise:
 receiving one or more carrier constraints of a carrier, wherein the carrier is configured to transport one or more vehicles;   receiving one or more vehicle attributes associated with one or more vehicles available to be transported by the carrier;   determining one or more optimal solution sets based at least in part on the one or more carrier constraints and the one or more vehicle attributes based at least in part on the processing of the plurality of cells; and   providing the one or more optimal solution sets to a user device.   
     
     
         17 . The system of  claim 16 , wherein the instructions further comprise:
 receiving from a user device a modification to the optimal solution, wherein modification comprises at least one of adding, deleting, accepting, trading, swapping, rejecting, and modifying at least one of the one or more vehicles comprised in the one or more optimal solution sets.   
     
     
         18 . The method of  claim 16 , wherein each of the one or more vehicles available to be transported by the carrier is associated with an optimized route segment for transporting each respective vehicle from a pick-up location to a delivery location. 
     
     
         19 . The method of  claim 16 , wherein the instructions further comprise:
 assigning a selected optimal solution set to the carrier;   generating a schedule for the carrier to transport each vehicle included in the selected optimal solution set; and   providing instructions for dispatching each vehicle included in the selected optimal solution set to be transported by the carrier according to the schedule.   
     
     
         20 . The method of  claim 16 , wherein the one or more optimal solution sets are provided to a user device for selection via an online marketplace listing over a wireless network.