DETAILED ACTION
This action is responsive to the RCE amendment filed on 3/2/2026. Claims 1-25 are being examined in the case. Claims 1, 9, and 16 are independent claims.
Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 112
The following is a quotation of the first paragraph of 35 U.S.C. 112(a):
(a) IN GENERAL.—The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor or joint inventor of carrying out the invention.
The following is a quotation of the first paragraph of pre-AIA 35 U.S.C. 112:
The specification shall contain a written description of the invention, and of the manner and process of making and using it, in such full, clear, concise, and exact terms as to enable any person skilled in the art to which it pertains, or with which it is most nearly connected, to make and use the same, and shall set forth the best mode contemplated by the inventor of carrying out his invention.
Claim 5 is rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the written description requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to reasonably convey to one skilled in the relevant art that the inventor or a joint inventor, or for applications subject to pre-AIA 35 U.S.C. 112, the inventor(s), at the time the application was filed, had possession of the claimed invention. The limitation “determining of the first candidate solutions includes performing, in parallel, respective first portions of the respective searches from the first solutions, and the respective searches, from the second solutions, include second portions of the respective searches. ” is contradictory and is not supported by the specification, because the specification describes the generation of the second solutions are dependent on the generation of candidate solutions. First candidate solutions and the second solutions are performed at best in series, and cannot be performed in “parallel” by the definitions laid out in the specification. in the specification (Fig.5), the first candidate solutions are determined from the first solutions, and then the second solutions are generated from the first candidate solutions.
Claim 5 is rejected under 35 U.S.C. 112(a) or 35 U.S.C. 112 (pre-AIA ), first paragraph, as failing to comply with the enablement requirement. The claim(s) contains subject matter which was not described in the specification in such a way as to enable one skilled in the art to which it pertains, or with which it is most nearly connected, to make and/or use the invention. The limitation “determining of the first candidate solutions includes performing, in parallel, respective first portions of the respective searches from the first solutions, and the respective searches, from the second solutions, include second portions of the respective searches. ” is contradictory and is not supported by the specification as to enable PHOSITA to make and use this limitation, because the specification describes the generation of the second solutions are dependent on the generation of candidate solutions. First candidate solutions and the second solutions are performed at best in series, and cannot be performed in “parallel” by the definitions laid out in the specification. in the specification (Fig.5), the first candidate solutions are determined from the first solutions, and then the second solutions are generated from the first candidate solutions.
2 ].
Claim Rejections - 35 USC § 112
The following is a quotation of 35 U.S.C. 112(b):
(b) CONCLUSION.—The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the inventor or a joint inventor regards as the invention.
The following is a quotation of 35 U.S.C. 112 (pre-AIA ), second paragraph:
The specification shall conclude with one or more claims particularly pointing out and distinctly claiming the subject matter which the applicant regards as his invention.
Claim 5 is rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite for failing to particularly point out and distinctly claim the subject matter which the inventor or a joint inventor (or for applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention. The limitation “determining of the first candidate solutions includes performing, in parallel, respective first portions of the respective searches from the first solutions, and the respective searches, from the second solutions, include second portions of the respective searches. ” is contradictory, because the first candidate solutions and the second solutions are performed at best in series, and cannot be performed in “parallel” by the definitions laid out in the claims. in parent claim 1, the first candidate solutions are determined from the first solutions, and then the second solutions are generated from the first candidate solutions.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
The factual inquiries for establishing a background for determining obviousness under 35 U.S.C. 103 are summarized as follows:
1. Determining the scope and contents of the prior art.
2. Ascertaining the differences between the prior art and the claims at issue.
3. Resolving the level of ordinary skill in the pertinent art.
4. Considering objective evidence present in the application indicating obviousness or nonobviousness.
Claims 1, 3-6, 8-13, and 15-16, 18-20, and 23-25 are rejected under 35 U.S.C. 103 as being unpatentable over Luong et al. (GPU Computing for Parallel Local Search Metaheuristic Algorithms, 2013), in view of Zhu et al , hereinafter Zhu 20200026264 A1.
Claim 1
Luong et al. teaches the operation of a set of compute engines to determine first candidate solutions-- “Each processor device on GPU supports the single program multiple data (SPMD) model, i.e., multiple autonomous processors simultaneously execute the same program on different data. For achieving this, the kernel is a function callable from the CPU host and executed on the specified GPU device. It defines the computation to be performed by a large number of threads, organized in thread blocks.” 4.1 paragraph 3, “Regarding the execution of a LSM on GPU, it consists in launching a kernel with a large number of threads. In this case, one thread is associated with one neighbor.”; Luong; 3.2 paragraph 2 and Algorithm 2 lines 12-15;-- one or more circuits to: operate compute engines using at least one parallel processing unit to, in parallel, determine, from first solutions within a search space associated with a combinatorial optimization problem, first candidate solutions within the search space that are determined to improve corresponding solutions of the first solutions; operate compute engines using at least one parallel processing unit to, in parallel, determine, operate the plurality of the compute engines using the respective inputs and the at least one parallel processing unit to, in parallel. Luong et al. teaches the determination of a subset of improvements of generated improvements based on evaluation of each of the candidate solutions, “Third, comes the parallel iteration level on GPU, in which each neighboring solution is generated (parallelism control), evaluated (memory management) and copied into the fitnesses structure (from lines 12 to 15).” See Algorithm 2 below. The fitnesses structure of Luong is being interpreted by the examiner as the set of improvements.).
Luong et al fail to explicitly teach provide second solutions selected as a subset of the first candidate solutions, that satisfy a set of constraints associated with the combinatorial optimization problem. Zhu shows selecting progeny solutions according to a preference matrix from a to-be-selected set. The progeny solutions are provided as input for regenerating new progeny combination ( 41-43-Fig. 1)—provide second solutions selected as a subset of the first candidate solutions, that satisfy a set of constraints associated with the combinatorial optimization problem.
Moreover, Luong et al fail to explicitly teach perform respective searches, from the second solutions, for one or more second candidate solutions within the search space that are determined to improve a corresponding solution of the second solutions, and provide a solution corresponding to the one or more second candidate solutions from the respective searches based at least on a value corresponding to an objective function that optimizes one or more features of the combinatorial optimization problem. However, Zhu teaches if cut-off conditions are met, then outputting a Pareto solution set and selecting a certain feasible solution, which enables the improvement of the diversity of solutions(42-43, 3, Fig.1).-- perform respective searches, from the second solutions, for one or more second candidate solutions within the search space that are determined to improve a corresponding solution of the second solutions, and provide a solution corresponding to the one or more second candidate solutions from the respective searches based at least on a value corresponding to an objective function that optimizes one or more features of the combinatorial optimization problem. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with combinatorial optimization of Zhu, because Zhu teaches improve the diversity of solutions (3).
Claim 3
Luong et al. and Yelmewad et al as applied to claim 1 teach the system of claim 1, but do not teach:
the plurality of the compute engines comprise respective solvers, at least one of the respective solvers implementing at least one different type of search algorithm than one or more others of the respective solvers. (Luong; 6.4 paragraph 1-2; Luong et al. teaches the application to the Traveling Salesman Problem, “Application to the Traveling Salesman Problem Given n cities and a distance matrix dn;n, where each element dij represents the distance between the cities i and j, the TSP consists in finding a tour which minimizes the total distance. A tour visits each city exactly once. The chosen representation is a permutation structure. A swap operator for the TSP has been implemented on GPU. The considered instances have been selected among the TSPLIB instances presented in [10]. Table 6 presents the results for the TSP implementation.”)
Claim 4
Luong et al. and Yelmewad et al as applied to claim 1 teach the system of claim 1, but do not teach:
wherein the combinatorial optimization problem is at least one of a traveling salesman, a vehicle routing problem, a bin packing problem, or a job shop scheduling problem. (Luong; 6.4 paragraph 1-2; Luong et al. teaches the application to the Traveling Salesman Problem, “Application to the Traveling Salesman Problem Given n cities and a distance matrix dn;n, where each element dij represents the distance between the cities i and j, the TSP consists in finding a tour which minimizes the total distance. A tour visits each city exactly once. The chosen representation is a permutation structure. A swap operator for the TSP has been implemented on GPU. The considered instances have been selected among the TSPLIB instances presented in [10]. Table 6 presents the results for the TSP implementation.”)
Claim 5
Based on the 35 USC 112 a, and b rejections above, Luong et al. teaches the operation of a set of compute engines to determine first candidate solutions-- “Each processor device on GPU supports the single program multiple data (SPMD) model, i.e., multiple autonomous processors simultaneously execute the same program on different data. For achieving this, the kernel is a function callable from the CPU host and executed on the specified GPU device. It defines the computation to be performed by a large number of threads, organized in thread blocks.” 4.1 paragraph 3, “Regarding the execution of a LSM on GPU, it consists in launching a kernel with a large number of threads. In this case, one thread is associated with one neighbor.”; Luong; 3.2 paragraph 2 and Algorithm 2 lines 12-15;-- determining of the first candidate solutions includes respective first portions of the respective searches from the first solutions.
Luong teaches in section 6.7 paragraph 2, 1, section 3.3, a method where the computed values are local minimum values within the search space assigned, “In the first approach, the standard GPU-based algorithm is considered, i.e., the fitnesses structure is copied back from the GPU to the CPU. In the second one, at each iteration, a reduction operation is iterated on GPU to find the minimum of all the fitnesses.” In Luong the initial solution comes with a local neighborhood. This local neighborhood is searched using parallel reduction techniques, for example by a hill climber, and a local minimum (for that neighborhood) is located. This is an iterative process and that new local minimum becomes the basis for the next search space and the process is repeated.)
-- determining of the first candidate solutions includes the respective searches, from the second solutions, include second portions of the respective searches.
Claim 6
Luong et al teaches inserting parallel operation resulting fitnesses into a structure (Luong; 3.2 paragraph 2 and Algorithm 2 lines 12-15;)-- based at least on the determination of the first candidate solutions, one or more of the compute engines update a shared data structure that the plurality of the compute engines access to determine the one or more second candidate solutions for the respective searches.
using the search algorithms running on different processor configurations, such as Hill Climbing, Tabu, Variable Neighborhood Search, etc for searching memory structures to find best mapping for efficiency and effectiveness (6, parag.2-3, 7, parag.2-6)-- different compute engines of the compute engines perform the searching by executing different respective local search algorithms.
Claim 8
Luong et al teach in section 6.3, paragraph 1 the use of the system as applied to the Weierstrass Continuous Function. This function sees use in simulations to model complex and irregular systems such as Brownian Motion or turbulence in fluid flow. “Application to the Weierstrass Continuous Function The Weierstrass functions belong to the class of continuous optimization problems. These functions have been widely used for the simulation of fractal surfaces.”) --
a system for performing simulation operations;
Claim 9 recites a system for implementing the processor of claim 1, and is likewise rejected.
Claim 10
Luong et al. do not teach:
wherein the combinatorial optimization problem comprises a vehicle routing problem. (Yelmewad; Abstract; Yelmewad et al. teaches the solving of a vehicle routing problem using a parallel computation strategy, “This paper presents the novel GPU-based parallel strategy for the heuristic algorithms to solve the large-scale Capacited Vehicle Routing Problem”).
Claim 11
Luong et al. do not teach:
wherein the second solutions include a set of intra-route improvements. (Yelmewad; IV (1) & Algorithm 1; Yelmewad et al. teaches the determination of a set of intra-route improvements, “Each thread x works on the corresponding node to find the best place on the same route r. The pseudocode version of the kernel function for the intraroute heuristics is presented in Algorithm 1. Three separate kernels have been used in the actual parallel implementation. Algorithm 1 shows the abstract of these three kernel functions for 2-opt, or-opt, and 3-opt improvement heuristics.”). Luong, Zhu, and Yelmewad are analogous art to the present invention because both are from the same field of endeavor of improving combinatorial optimization using parallel processing strategies. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with the application of the subset of improvements and the provision of a solution from the second set of solutions of Yelmewad. As such, it would have been obvious to one of ordinary skill in the art to modify the teachings of Luong to include the teachings of Yelmewad because the combination would allow for the predictable result of solving for a solution to a combinatorial optimization problem in an efficient and parallel manner.
Claim 12
Luong et al. do not teach:
the second respective improvements include a set of inter-route improvements. (Yelmewad; IV (2) paragraph 1 & Algorithm 2; Yelmewad et al. teaches of a set of inter-route improvements, “The parallel implementation of inter-route heuristic is similar to the parallel version of intraroute heuristics. The difference is that each thread finds its best suitable place on other routes than the same route. The stepwise details of this version are shown in Algorithm 2.”). Luong, Kellam, and Yelmewad are both analogous art to the present invention because they are from the same field of endeavor of improving combinatorial optimization using parallel processing strategies. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with the application of the subset of improvements and the provision of a solution from the second set of solutions of Yelmewad. As such, it would have been obvious to one of ordinary skill in the art to modify the teachings of Luong to include the teachings of Yelmewad because the combination would allow for the predictable result of solving for a solution to a combinatorial optimization problem in an efficient and parallel manner.
Claim 13
Luong et al. do not teach:
the respective searches each include: a candidate generation phase in which each compute engine respectively generates new potential solutions from the corresponding solution; and a move execution phase in which the compute engine sorts and processes the new potential solutions using one or more heavy constraints to select the one or more second candidate solutions. However, Zhu shows selecting progeny solutions according to a preference matrix from a to-be-selected set. The progeny solutions are provided as input for regenerating new progeny combination ( 41-43-Fig. 1)—provide second solutions selected as a subset of the first candidate solutions, that satisfy a set of constraints associated with the combinatorial optimization problem. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with combinatorial optimization of Zhu, because Zhu teaches improve the diversity of solutions (3).
Claim 15
Luong et al. and Yelmewad et al as applied to claim 9 teach the system of claim 9, but do not teach:
a system for performing simulation operations; (Luong; 6.3 paragraph 1; Luong et al. teaches the use of the system as applied to the Weierstrass Continuous Function. This function sees use in simulations to model complex and irregular systems such as Brownian Motion or turbulence in fluid flow. “Application to the Weierstrass Continuous Function The Weierstrass functions belong to the class of continuous optimization problems. These functions have been widely used for the simulation of fractal surfaces.”).
Regarding Claim 16
transmitting data causing a parallel processing unit to execute a plurality of compute engines to, using at least one parallel processing unit, in parallel, perform a plurality of iterations of: receiving inputs comprising solutions within a search space associated with a combinatorial optimization problem, and obtaining a solution to the combinatorial optimization problem from a compute engine of the plurality of compute engines. (Luong et al. teaches the parallel use of a search algorithm within a search space of a combinatorial optimization problem, Luong 6.7 paragraph 1-2 “The next experiment consists in comparing two GPU-based approaches of the Hill Climbing algorithm. This latter LSM iteratively improves a solution by selecting the best neighbor. The algorithm terminates when it cannot see any improvement anymore.” Luong 4.1 paragraph 1-2, 3.1 “Each processor device on GPU supports the single program multiple data (SPMD) model, i.e., multiple autonomous processors simultaneously execute the same program on different data. For achieving this, the kernel is a function callable from the CPU host and executed on the specified GPU device. It defines the computation to be performed by a large number of threads, organized in thread blocks.” The search space in Luong is the neighborhood being searched. Neighbor solutions are examined and selected in parallel using the local search metaheuristic (LSM) algorithms.)
Luong et al fail to explicitly teach the solutions being generated in a previous iteration of the plurality of iterations, and perform, using the inputs, respective searches from the solutions for one or more candidate solutions within the search space that are determined to improve a corresponding solution of the solutions, the one or more candidate solutions from the respective searches comprising updated solutions with respect to the solutions for a subsequent iteration of the plurality of iterations. However, Zhu shows iteratively selecting progeny solutions according to a preference matrix from a to-be-selected set. The progeny solutions are provided as input for regenerating new progeny combination ( 41-43-Fig. 1)— the solutions being generated in a previous iteration of the plurality of iterations. Additionally, Zhu teaches performing the iterations, which improve on the previous iteration(s). Then, if cut-off conditions are met, outputting a Pareto solution set and selecting a certain feasible solution, which enables the improvement of the diversity of solutions(42-43, 3, Fig.1).-- and perform, using the inputs, respective searches from the solutions for one or more candidate solutions within the search space that are determined to improve a corresponding solution of the solutions, the one or more candidate solutions from the respective searches comprising updated solutions with respect to the solutions for a subsequent iteration of the plurality of iterations. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with combinatorial optimization of Zhu, because Zhu teaches improve the diversity of solutions (3).
Claim 18
Luong et al. teach:
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. (Luong; 6.4 paragraph 1-2; Luong et al. teaches solving the traveling salesman problem, “Application to the Traveling Salesman Problem Given n cities and a distance matrix dn;n, where each element dij represents the distance between the cities i and j, the TSP consists in finding a tour which minimizes the total distance. A tour visits each city exactly once. The chosen representation is a permutation structure. A swap operator for the TSP has been implemented on GPU. The considered instances have been selected among the TSPLIB instances presented in [10]. Table 6 presents the results for the TSP implementation.”)
Claim 19
Luong et al. teach:
the compute engines determine the respective improvements based at least on executing respective search algorithms in parallel. (Luong; 6.7 paragraph 1-2, 4.1; Luong et al. teaches finding improvements using a parallel multiprocessors, then reducing the set of solutions to find the minimum using the GPU or iteratively improving the solutions by selecting from neighbor solutions, “Indeed, in some LSMs such as Hill Climbing, there is no need to transfer the entire fitnesses structure and further optimization is possible. The next experiment consists in comparing two GPU-based approaches of the Hill Climbing algorithm. This latter LSM iteratively improves a solution by selecting the best neighbor. The algorithm terminates when it cannot see any improvement anymore. In the first approach, the standard GPU-based algorithm is considered, i.e., the fitnesses structure is copied back from the GPU to the CPU. In the second one, at each iteration, a reduction operation is iterated on GPU to find the minimum of all the fitnesses.”)
Claim 20
Luong et al. teach:
wherein the at least one parallel processing unit comprises a graphical processing unit. (Luong; 4.1 paragraph 2-3; Luong et al. teaches the use of a graphical processing unit for parallel processing, “Hence, one of the key points to achieve high performance is to keep the GPU multiprocessors as active as possible. Latency hiding depends on the number of active warps per multiprocessor, which is implicitly determined by the execution parameters along with register constraints. That is the reason why, it is necessary to use threads and blocks in a way that maximizes hardware utilization. This is achieved with two parameters: the number of threads per block and the total number of threads. In general, threads per block should be a multiple of the warp size (i.e., 32 threads) to avoid wasting computation on underpopulated warps. Regarding the execution of a LSM on GPU, it consists in launching a kernel with a large number of threads.”)
Claim 23
Luong et al. teach allocating additional structures to calculate neighbors evaluations (3.2, parag.2)--for a least one iteration of the plurality of iterations, the solutions are generated based at least on expanding the updated solutions from the previous iteration to include at least one additional solution.
Claim 24
Luong et al teaches using the search algorithms running on different processor configurations, such as Hill Climbing, Tabu, Variable Neighborhood Search, etc for searching memory structures to find best mapping for efficiency and effectiveness (6, parag.2-3, 7, parag.2-6)-- different compute engines of the compute engines determine the one or more candidate solutions by executing different respective types of local search algorithms.
Claim 25
Luong et al. teach ending algorithm 3 based on the expense of computational time, and controlling the number of threads to meet memory constraints ( 6, parag.3-6)--the plurality of iterations are terminated based at least on determining an execution budget has been exceeded.
Claim 2, and 21-22 are rejected under 35 U.S.C. 103 as being unpatentable over Luong et al., in view of Zhu as applied to Claim 1 above, and further in view of Pandi (A Generic GPU-Accelerated Framework for the Dial-A-Ride Problem, 2020).
Claim 2
Luong et al. and Zhu as applied to claim 1 teach the method of claim 1 but do not teach:
wherein the first solutions are generated based at least on modifying a set of hyperparameters of an insertion algorithm-- (Pandi; IV(C) paragraph 2 and Algorithm 5; Pandi et al. teaches an insertion algorithm with parameters that can be modified to generate solutions, “In the Insertion kernel function, each thread is responsible to construct a unique neighborhood solution. The procedure is described as follows: i) initialize the value of idx as a function of threads and blocks, ii) for all values of idx less than Nsize, initialize the value of vehicle that represents the target vehicle ID in which the request req will be inserted, iii) for all the values of the variable tid ∈ [0, gpu[idx].routesize], insert the pick up and drop-off vertices associated with request req in vehicle at the start and gap positions, respectively. As a result, all the neighborhood solutions with respect to the current solution will be constructed. The indexing scheme with state1 and state2 optimizes branch divergence as detailed in Section V-D. Algorithm 5 describes the implementation of the Insertion kernel.“ Each thread will construct its own unique neighborhood solution. The threadIdx.x, blockIdx.x and blockDim.x are being interpreted as the hyperparameters, which are modified depending on the thread running the kernel.)
Luong, Kellam, Yelmewad, and Pandi are analogous art to the present invention because they are from the same field of endeavor of improving combinatorial optimization using parallel processing strategies. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine Luong, Kellam and Yelmewad as in Claim 1 above in addition to combining Pandi’s insertion kernel function to arrive at the system of Claim 2. The motivation to combine would be to accelerate and optimize the solving of combinatorial optimization problems.“ As such, it would have been obvious to one of ordinary skill in the art to modify the teachings of Luong and Yelmewad to include the teachings of Pandi because the combination accelerated neighborhood exploration of local search operations.
Claim 21
Luong et al. as applied to claim 16 teaches the method of claim 16 but does not teach:
wherein the operations of the search algorithm comprise an insertion algorithm to generate an initial set of solutions within the search space. (Pandi, IV(B) paragraph 1 and Algorithm 3; Pandi et al. teaches the use of an insertion algorithm to generate initial solutions within the search space in order to find improvements, “Next, we present the GPU-accelerated local search algorithm, which will be integrated into the metaheuristics in Section VI. This algorithm is built as a host function that invokes CUDA kernels that run on the GPU. The implementation details are presented in Algorithm 3. This algorithm identifies all neighbors of the current solution, evaluates them, and chooses the best one for the next iteration.”; Pandi et al IV(C) paragraph 2 and Algorithm 5; “In the Insertion kernel function, each thread is responsible to construct a unique neighborhood solution. The procedure is described as follows: i) initialize the value of idx as a function of threads and blocks, ii) for all values of idx less than Nsize, initialize the value of vehicle that represents the target vehicle ID in which the request req will be inserted, iii) for all the values of the variable tid ∈ [0, gpu[idx].routesize], insert the pick up and drop-off vertices associated with request req in vehicle at the start and gap positions, respectively. As a result, all the neighborhood solutions with respect to the current solution will be constructed. The indexing scheme with state1 and state2 optimizes branch divergence as detailed in Section V-D. Algorithm 5 describes the implementation of the Insertion kernel.“ The search space is being interpreted as the neighborhood of Pandi, wherein the neighbors are evaluated as potential solutions. The insertion kernel of Pandi is where the initial solutions are generated.)
Luong and Pandi are analogous art to the present invention because they are from the same field of endeavor of improving combinatorial optimization using parallel processing strategies. It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine Luong as in Claim 16 with Pandi’s insertion kernel function to arrive at the system of Claim 21. As such it would have been obvious to one of ordinary skill in the art to modify the teachings of Luong to include the teachings of Pandi because the combination would have had the predictable result of accelerating and optimizing the solving of combinatorial optimization problems.
Claim 22
Luong et al. and Pandi et al. as applied to claim 21 teach the method of claim 21 but do not teach:
wherein the initial set of solutions are variated by at least modifying a set of hyperparameters associated with the insertion algorithm. (Pandi; IV(C) paragraph 2 and Algorithm 5; Pandi et al. teaches an insertion kernel whose parameters ensure unique neighborhood solutions, “In the Insertion kernel function, each thread is responsible to construct a unique neighborhood solution. The procedure is described as follows: i) initialize the value of idx as a function of threads and blocks, ii) for all values of idx less than Nsize, initialize the value of vehicle that represents the target vehicle ID in which the request req will be inserted, iii) for all the values of the variable tid ∈ [0, gpu[idx].routesize], insert the pick up and drop-off vertices associated with request req in vehicle at the start and gap positions, respectively. As a result, all the neighborhood solutions with respect to the current solution will be constructed. The indexing scheme with state1 and state2 optimizes branch divergence as detailed in Section V-D. Algorithm 5 describes the implementation of the Insertion kernel. “ Each thread will construct its own unique neighborhood solution. The threadIdx.x, blockIdx.x and blockDim.x are being interpreted as the hyperparameters, which are modified depending on the thread running the kernel.)
Claim 14 is rejected under 35 U.S.C. 103 as being unpatentable over Luong et al. (GPU Computing for Parallel Local Search Metaheuristic Algorithms, 2013), in view of Zhu, and further in view of (Kahng et al, hereinafter Kahng, US 20230205968 A1, provisional application filed on 6/8/2020).
Claim 14
Luong et al. but do not teach:
the first solutions include randomly generated solutions to the search space. However. Kahng teaches performing routing by using seeds to obtain solutions (135). It would have been obvious to a person having ordinary skill in the art before the effective filing date to combine the solution generation, the operation of computer engines, and determination of a subset of improvements of Luong with, Kellam, Yelmewad, and Kahng because Kahng teaches a method for easier processing of routing solutions (129).
Allowable Subject Matter
Claims 7, and 17 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Response to Arguments
Applicant's arguments filed on 3/2/2026 have been fully considered but they are not persuasive. The Applicant indicates that “Applicant respectfully submits that the combination of references does not teach or suggest, at least, "provide, as respective inputs to a plurality of the compute engines, second solutions selected as a subset of the first candidate solutions, that satisfy a set of constraints associated with the combinatorial optimization problem," and "operate the plurality of the compute engines using the respective inputs and the at least one parallel processing unit to, in parallel, perform respective searches, from the second solutions, for one or more second candidate solutions within the search space that are determined to improve a corresponding solution of the second solutions,"…”.
Additionally, Applicant argues that “The combination of Luong and Kellam with Yelmewad does not cure the deficiency of Luong, nor was it used to show similar features…”.
In addition, Applicant argues that “For at least some similar reasons as amended independent claims 1 and 9, Luong fails to teach or suggest each and every feature of independent claim 16. As such, the Luong fails to teach or suggest each and every feature of dependent claims 17-20 and 23-25. Accordingly, Applicant respectfully requests withdrawal of the 35 U.S.C. § 103 rejection of claims 16-20 and 23-25.…”. Claim 17 has been objected to for containing allowable subject matter. The other claims have been rejected under new grounds of rejection as indicated above.
In addition, Applicant argues that “As described above, the combination of references fails to teach or suggest each and every feature of independent claim 1. Further, the Pandi reference fails to overcome the deficiencies described above with respect to the independent claim, nor was it cited to for doing so. As such, the combination of reference, including the additional references, fails to teach or suggest each and every feature of dependent claim 2. Accordingly, Applicant respectfully requests withdrawal of the 35 U.S.C. § 103 rejection of claim 2”.
In addition, Applicant argues that “As described above, the combination of references fails to teach or suggest each and every feature of independent claim 9. Further, the Kahng reference fails to overcome the deficiencies described above with respect to the independent claim, nor was it cited to for doing so. As such, the combination of reference, including the additional references, fails to teach or suggest each and every feature of dependent claim 14. Accordingly, Applicant respectfully requests withdrawal of the 35 U.S.C. § 103 rejection of claim 14.”.
In addition, Applicant argues that “As described above, the combination of references fails to teach or suggest each and every feature of independent claim 6. Further, the Arbelaez reference fails to overcome the deficiencies described above with respect to the independent claim, nor was it cited to for doing so. As such, the combination of references, including the additional reference, fails to teach or suggest each and every feature of dependent claim 7. Accordingly, Applicant respectfully requests withdrawal of the 35 U.S.C. § 103 rejection of claim 7.”.
Furthermore, Applicant argues that “As described above, Luong fails to teach or suggest each and every feature of independent claim 16. Further, the Pandi reference fails to overcome the deficiencies described above with respect to the independent claim, nor was it cited to for doing so. As such, the combination of references, including the additional reference, fails to teach or suggest each and every feature of dependent claims 21 and 22. Accordingly, Applicant respectfully requests withdrawal of the 35 U.S.C. § 103 rejection of claims 21 and 22.”.
New grounds of rejection have been included which address the newly introduced amendments referred to by Applicant above.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Çördük -- US-20230145783-A1, which discloses solutions to combinatorial optimization problems are determined using a plurality of solvers executing in parallel.
Stapleton-- US-20220019663-A1, which discloses limiting the vulnerability of machine learning models to attack and/or exploitation of the model for malicious use, and for detecting when such attack/exploitation has occurred.
Aladahalli-- US-12229670-B2, which discloses employing an artificial neural network to infer an outcome from an image instance in a sequence of images based on combined output data from the different layers of the artificial neural network.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to CESAR PAULA whose telephone number is (571) 272-4128. The examiner can normally be reached Monday - Friday, 6 a.m. - 4:30 p.m. ET..
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor David Wiley can be reached on 571‐272‐3923. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for
more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/CESAR B PAULA/Supervisory Patent Examiner, Art Unit 2145
Prosecution Insights