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 . In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
DETAILED ACTION
This Final Office Action is in response Applicant communication filled on 04/28/2026.
Status of Claims
Claims 1-8 and 10-15 have been amended by Applicant.
Claims 1-15 are currently pending and rejected as follows.
Response to Amendments / Arguments
Applicant’s 04/28/2026 amendment necessitated new grounds of rejection in this action.
Response to previous claim objection
Objection to Claims 1,3-5,12-14 in previous act are withdrawn in view of Applicant’s amendment.
Response to previous 112(b) rejection
112(b) rejection in the prior act is withdrawn in view of Applicant’s amendment.
Response to 35 USC 101 rejection
Remarks 04/28/2026 p.10 ¶3-p.11 ¶1 cites Original Specification to further argued at Id. p.11 ¶2 that the newly added or amended limitations (iv)-(ix) is not merely a method of organizing human activities nor does it recite abstract idea but rather elements that integrate any purported judicial exception into a practical application, amount to significantly more than the judicial exception, and include features involving an improvement in the functioning of a computer itself.
Examiner fully considered the argument but respectfully disagrees finding it unpersuasive.
-> First, Examiner notes that Applicant extensively relies on the Original Specification at
Remarks 04/28/2026 p.10 ¶3-p.11 ¶1 and cautions that the “101 inquiry must focus on language of Asserted Claims themselves” as in “Synopsys, Inc. v Mentor Graphics Corp, U.S. Court of Appeals Federal Circuit, No 2015-1599, October 17 2016 2016 BL 344522 839 F3d 1138” citing “Accenture Global Servs., GmbH
PNG
media_image1.png
1
1
media_image1.png
Greyscale
v
PNG
media_image1.png
1
1
media_image1.png
Greyscale
. Guidewire Software, Inc. 728
PNG
media_image1.png
1
1
media_image1.png
Greyscale
F.3d
PNG
media_image1.png
1
1
media_image1.png
Greyscale
1336, 1345 108 USPQ2d 1173 Fed Cir. 2013: admonishing that the important inquiry for a 101 analysis is to look to the claim”, citing “Content Extraction & Transmission LLC
PNG
media_image1.png
1
1
media_image1.png
Greyscale
v.
PNG
media_image1.png
1
1
media_image1.png
Greyscale
Wells Fargo Bank Nat’l Ass’n 776
PNG
media_image1.png
1
1
media_image1.png
Greyscale
F3d
PNG
media_image1.png
1
1
media_image1.png
Greyscale
1343, 1346 113 USPQ2d 1354 (Fed. Cir. 2014): We focus here on whether the claims of the asserted patents fall within the excluded category of abstract ideas”, cert. denied, 136 S Ct 119, 193 L. Ed. 2d 208 2015). This is consistent with MPEP 2103 I.C stating that “claims define the property rights provided by patent, thus require careful scrutiny. The goal of claim analysis is to identify boundaries of protection sought by applicant and to understand how claims relate to and define what applicant indicated is the invention. USPTO personnel must first determine the scope of a claim by thoroughly analyzing the language of claim before determining if claim complies with each statutory requirement for patentability”. Simply said “[T]he name of the game is the claim”. MPEP 2103 I C citing In re Hiniker Co 150 F3d 1362 1369 47 USPQ2d 1523, 1529 Fed Cir 1998.
-> Second, the Examiner notes the preponderance of contingent limitations at independent Claims 1, as introduced by expressions: “when” and “responsive to”, and thus points to the limited patentable weight of such contingent limitations as indicated by MPEP 2111.04 II.
-> Third, Examiner submits that the limitations (iv)-(ix), as amended and then argued at Remarks 04/28/2026 p.11 ¶-p.12 ¶1 do not render the claims less abstract and eligible.
For once the expression “(iv) “executing, by the processor, prior to executing an optimization calculation, a trial calculation based on the model of the power grid and the input data to determine whether a complete solution is expected from the optimization calculation” [akin to what is known in the art as proof of concept, or order-of-magnitude estimation] “for executing the optimization calculation (a) as a single optimization problem” [akin to sensitivity analysis] “or (b) in a plurality of stages” [akin to boundary and constraint testing] does set forth abstract mathematical calculations of MPEP 2106.04(a)(2) (I) (C) and/or the abstract mathematical relationships expressed in words of MPEP 2106.04(a)(2)(I) (A).
Next per, (v) “responsive to an output of the trial calculation indicating that the complete solution is not expected, automatically executing, by the processor, the optimization calculation in the plurality of stages representing different constraint-applying methods of the one or more constraints”; and (vi) “generating, by the processor, during execution of the plurality of stages, at least: (a) “one or more interim results from partial execution of the optimization calculation and stored in the memory and (b) information indicating a violation status for each of the one or more constraints” and (vii) “responsive to the information indicating a violation associated with at least a violated constraint of the one or more constraints, iteratively executing, by the processor, one or more of the plurality of stages with updated constraints excluding or modifying the violated constraint” [boded emphasis added], the Examiner finds such limitation similar abstract mathematical approaches such as Rolle’s theorem, divide and conquer, heuristics approximation, to set forth the abstract mathematical calculations of MPEP 2106.04(a)(2) (I) C and/or the abstract mathematical relationships expressed in words of MPEP 2106.04(a)(2)(I) (A). Even when more granularly investigating the purported execution of such algorithms by a computer, it has been established that “The requirements that the machine learning model be ‘iteratively trained’ or dynamically adjusted based on real-time changes not represent a technological improvement” at least because they are “incident to the very nature of machine learning”. See Recentive Analytics, Inc. v. Fox Corp., 134 F.4th 1205, 1212 (Fed. Cir. 2025 and cited by PTAB Appeal 2025-003304.
Examiner also points to Brandan Artley, Training a Neural Network by Hand, towardsdatascience webpages, Jun 23, 2022, incorporated herein, who discloses the training of a neural network by hand to solve a regression problem where the model continually improves its predictions to arrive at a highly accurate model. It then follows that here, similar to the iterative training in Recentive Analytics and Brandan Artley above, the current “executing, by the processor, the optimization calculation in the plurality of stages” would also be incident to the very nature of machine learning, thus incapable to render the claims patent eligible.
Further, per (viii) “when the optimization calculation cannot be completed after iteratively executing the one or more of the plurality of stages, retrieving, by the processor, at latest interim result of the one or more interim results from the memory and generating the latest interim result for display via a user interface”; and (ix) “when the optimization calculation is completed using at least one of the updated constraints, generating, by the processor, for display via the user interface, a result of the optimization calculation comprising the complete solution”, the Examiner finds such limitations not meaningfully different than the abstract approaches of heuristics, iterative refinement or approximation, which set forth the abstract mathematical calculations of MPEP 2106.04(a)(2) (I) C and/or the abstract mathematical relationships expressed in words of MPEP 2106.04(a)(2)(I) (A). Once again, Examiner stresses that as ruled by the Federal Circuit in Recentive Analytics, Inc. v. Fox Corp., 134 F.4th 1205, 1212 (Fed. Cir. 2025) and cited by PTAB Appeal 2025-003304: “The requirements that the machine learning model be ‘iteratively trained’ or dynamically adjusted based on real time changes do not represent a technological improvement” at least because they are “incident to the very nature of machine learning”. Examiner also points again to Brandan Artley, Training a Neural Network by Hand, towardsdatascience webpages, Jun 23, 2022, incorporated herein, corroborating that the training of a neural network by hand to solve a regression problem where the model continually improves its predictions to arrive at a highly accurate model.
It then follows that here, similar to the iteratively training and dynamically adjustment in Recentive Analytics and Brandan Artley, the use in the current independent Claims 1,12, of a “latest interim result” “when the optimization calculation cannot be completed” and the use of “a result of the optimization calculation” “when the optimization calculation is completed” etc. would also be incident to the very nature of machine learning, if not abstract right from the onset, as indicative to the mathematical relationships of MPEP 2106.04(a)(2) I A and/or cognitive and evaluation functions of MPEP 2106.04(a)(2) III ¶2, performed in a computer environment of MPEP 2106.04(a)(2) III C #2 or using a computer as a tool of MPEP 2106.04(a)(2) III C #3.
No matter if considered as additional elements (Step 2A prong two, Step 2B), or as integral to the abstract exception itself (Step 2A prong one), and executed in computer environment [MPEP 2106.04(a)(2) III C #2] or by a computer as a tool [MPEP 2106.04(a)(2) III C #3], such computational limitations are incapable to render the claims patent eligible, given the legal preponderance of evidence as articulated by the Examiner above.
Lastly, as per the alleged improvement argument, raised Remarks 04/28/2026 p.10 ¶2, p.12 ¶1, the Examiner submits that any improvements the aforementioned limitations would convey, would be improvements in the mathematical principles and models identified above for optimization planning, rather than an improvement in actual technology, with its utilization of such optimization planning in a “power grid” representing a mere narrowing of the abstract calculations and evaluations to a field of use or technological environment in a manner not meaningfully different than limiting the combination of collecting information, analyzing it, and displaying certain results of the collection and analysis to an electric power grid in Electric Power Group, LLC v. Alstom S.A., 830 F.3d 1350, 1354, 119 USPQ2d 1739, 1742 (Fed. Cir. 2016), which, as revealed by MPEP 2106.05(h)(vi) does not integrate the abstract exception into a practical application or provide significantly more. Furter MPEP 2106.04 I. is also clear that even a “groundbreaking, innovative, or even brilliant discovery does not by itself satisfy the §101 inquiry” citing Myriad, 569 U.S at 591, 106 USPQ2d at 1979”. Such rationale as articulated by the Court in Myriad was further corroborated in SAP Am, Inc v InvestPic as cited MPEP 2106.04(a)(2) I. C (i). Specifically, the Court found in SAP that “even if one assumes that the techniques claimed are groundbreaking, innovative, or even brilliant those features are not enough for eligibility because their innovation is innovation in ineligible subject matter. An advance of that nature is ineligible for patenting. Specifically, the proposed solution in SAP supra utilized a bootstrap method, which estimated distribution of data in a pool (a sample space) by repeated sampling of the data in the pool. A sample space in a boot-strap method can be defined by selecting a specific investment or a particular period of time. Data samples were drawn from the sample space with replacement: samples are drawn from the sample space and then returned to the pool before next sample is drawn. Yet, the Federal Circuit noted: “Dependent method claims 2-7 and 10 add limitations… [that] require the resampling method to be a bootstrap method." SAP, 260 F. Supp. 3d at 715 . Likewise, "[c]laims 8 and 9 add limitations that the statistical method is a jackknife method and a cross validation method." Id. at 716. Because bootstrap, jack-knife, and cross-validation methods are all "particular methods of resampling," those features simply provide further narrowing of what are still mathematical operations. They add nothing outside the abstract realm. See Mayo, 566 U.S. at 88-89 (stating that narrow embodiments of ineligible matter, citing mathematical ideas as an example, are still ineligible); buySAFE, 765 F.3d at 1353 (same). Dependent method claims 12-21 are no different”. This is further corroborated by MPEP 2106.04 I ¶5, 3rd sentence citing Mayo, 566 U.S. 71, 101 USPQ2d at 1965); Flook, 437 U.S. at 591-92, 198 USPQ2d at 198 to articulate that, for the purpose of subject matter eligibility, the novelty of a mathematical algorithm is not a determining factor at all.
Since implementation of a sample space with replacement where samples were drawn from the sample space and then returned to the pool before next sample is drawn, were incapable to save the claims in SAP from patent ineligibility, and since the iterative properties of
boot-strap, jackknife, cross validation, and resampling for analysis of data, were also incapable to save the claims in SAP from patent ineligibility, despite its alleged improvement, Examiner reasons that here, the analogous optimization of either a complete solution, expect[ed] from single optimization program or iteratively executed in stages would not render the claims eligible.
Based on the preponderance of legal evidence, Examiner submits that even as amended, the argued claims remain patent ineligible, and the Applicant’s argument is thus unpersuasive.
-------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Response to prior art rejection
Remarks 04/28/2026 p.14 ¶1 argues that the prior Office Action has not asserted any references teaching, the newly added or amended features of:
- 1. “executing” “a trial calculation” [before or] “prior to executing an optimization calculation” “to determine whether a complete solution is expected from the optimization calculation”
- 2. [using] “responsive to an output of the trial calculation indicating that the complete solution is not expected, automatically executing” “the optimization calculation in the plurality of stages”
- 3. “generating” “(a) one or more interim results from partial execution of the optimization calculation” “and” “(b) information indicating a violation status for each of one or more constraints”
- 4. “iteratively executing” “one or more of the stages with updated constraints excluding” “modifying a violated constraint”
- 5. “when the optimization calculation” [still] “cannot be completed”, “retrieving” “a latest interim result” “for display” “when the optimization calculation is completed using at least one of the updated constraints”, “generating” “a result of the optimization calculation comprising the complete solution for display”
Examiner fully considered the prior art argument which is moot in view of new grounds of rejection. Raghunathan et al US 20150199606 A1 is now relied to teach the argued features of:
- 1. “executing” “a trial calculation” [before or] “prior to executing an optimization calculation” “to determine whether a complete solution is expected from the optimization calculation”
(Raghunathan ¶ [0005] 2nd sentence: search space of the solutions and constraints of the OPF problem partitioned using structure and characteristics of the elements of the power grid, and thus the branch and bound framework can be utilized to search for the global minimum.
Raghunathan ¶ [0007] Some embodiments of the invention are based on an additional realization that the branch and bound method should be implemented such that a search for the lowest lower and upper bound in a nested region can use, as starting point, the result of the search in the region from which the nested region was partitioned according to the branch and bound principles. This realization is based in part on the recognition that the structure of the power grid has patterns or similarities repeated over the span of the grid. Thus, the result of the search in one region can be used to speed up the search over a different region.
Raghunathan ¶ [0056] 2nd-3rd sentences: some embodiments of the invention are based on an additional realization that the branch and bound method should be implemented such that a search for the lowest lower and upper bound in a nested region can use, as a starting point, the result of the search in the region from which the nested region was partitioned according to the branch and bound principles. This realization is based in part on the recognition that the structure of the power grid has patterns or similarities repeated over the span of the grid.
Raghunathan ¶ [0065] 3rd-10th sentences: Using the obtained solution a sufficient condition for the upper bound solution to be a globally optimal solution is checked 622. If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. Instead, the lower bound for the node is set to that of the upper bound 626. Then, the lower upper bound for the BB tree is updated 627 and the algorithm proceeds to 645 of the flowchart in FIG. 6A. If the sufficient condition 622 does not hold then, the lower bounding problem is solved 623. The solution of the lower bounding problem is checked 623 if it satisfies a sufficient condition that allows constructing an upper bound solution with same objective value as the lower bound solution. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. If the lower bound sufficient condition 623 holds then, the upper bound for the node is set to that obtained from the lower bound 628 and the upper bound solution is set to that obtained from the lower bounding problem 629. The algorithm then proceeds to 629. For example see
Raghunathan Figs.7-12 ->R2->R3->R4, ¶ [0066] 2nd-3rd sentences: global optimum cannot be determined from R shown in Fig.7B, feasible region R is partitioned into R1 and R2, and the BB procedure is repeated. The resulting BB tree 700 after the partition is shown in Fig.3C.
Raghunathan ¶ [0067] After a node has been processed but the termination conditions for BB have not been satisfied and there exist nodes that are yet unanalyzed the BB procedure proceeds by selecting one of the unanalyzed nodes and calculating the upper and lower bounds for the particular specification of the feasible region.
Raghunathan ¶ [0068] For instance, suppose the region R2 is selected to be analyzed and upper and lower bounding problems are solved to obtain U2,L2 respectively as shown in FIG. 8A. Further suppose that U2−L2<τ and U2=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R2 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R2 820 is deemed as fathomed (as shown in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0069] 3rd sentence: Because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 in Fig. 9B.
Raghunathan ¶ [0071] 3rd-4th sentences: a globally optimal solution has been obtained for region corresponding to the node R4 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (as shown in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0072] 1st sentence: if there is an optimality gap, then the feasible region is partitioned into two sub-regions, over which the BB procedure is repeated
Raghunathan ¶ [0127] 3rd -5th sentences: A significant advantage of ADMM algorithm is that if a good initial guess is available for the problem (8) then the algorithm converges quickly. Such a behavior cannot be expected for interior point algorithms for semidefinite programs. This property is commonly called as warm-starting and is important especially when semidefinite programs are to be solved as part of a branch and bound algorithm as described earlier)
- 2. [using or] “responsive to an output of the trial calculation indicating that the complete solution is not expected, automatically executing” “the optimization calculation in the plurality of stages”
(Raghunathan ¶ [0048] 3rd-5th sentences: usually branch and bound methods are implemented using linear under-approximation of optimized function, because solution of such approximation can be efficiently performed. Yet, the embodiments recognized that for power flow analysis of the power grid, the linear under-approximation of cost function representing power flow is inefficient due to over approximation of the feasible region that results from linear approximations. Hence, it was realized that despite of solution complexity of the SDP over the linear under-approximation, the usage of the SDP approximation in the context of the power grids is advantageous.
Raghunathan ¶ [0064] If (Ubest−Lbest) or (Ubest−Lbest)/Ubest<predetermined threshold τ 655, then BB terminates with current lowest upper bounding solution 660. Otherwise another node from BB tree 615 is selected to update/improve lower and upper bound using the solving steps.
Raghunathan ¶ [0065] Fig.6B shows block diagram of the BB method, in which the solution of the upper and lower bounding problem 620 is expanded. The upper bound problem for the node is solved 621 first. Using the obtained solution a sufficient condition for the upper bound solution to be a globally optimal solution is checked 622. If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. Instead, the lower bound for the node is set to that of upper bound 626. Then, the lower upper bound for BB tree is updated 627 and the algorithm proceeds to 645 of e flowchart in Fig.6A. If sufficient condition 622 does not hold then, the lower bounding problem is solved 623. The solution of lower bounding problem is checked 623 if it satisfies a sufficient condition that allows constructing an upper bound solution with same objective value as the lower bound solution. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. If the lower bound sufficient condition 623 holds then, the upper bound for the node is set to that obtained from the lower bound 628 and the upper bound solution is set to that obtained from the lower bounding problem 629. The algorithm then proceeds to 629. Typically, the computation of the lower bound is expensive and then sufficiency check in 622 can help in avoiding unnecessary calculations when the upper bound problem is indeed able to solve the node to global optimality.
Raghunathan ¶ [0024]-¶ [0030] Figs. 7-13 are examples of different stages of BB method
Raghunathan ¶ [0066] after the solution of upper and lower bounding problems for root node R, Ubest is set to U. Further, (U−L), and (U−L)/U and (Ubest−L) are all larger > predetermined threshold T. In this case, global optimum cannot be determined from R and in Fig.7B, the feasible region R is partitioned into R1 and R2, and BB procedure is repeated. The resulting BB tree 700 after the partition is shown in Fig.3C. Now R1 and R2 are placed in a list of nodes 710 that need to be explored and are temporarily assigned the lower bound L based on the lower bound obtained from the parent node R as shown in Fig. 3C. Following this, Lbest can be updated as the smallest of the temporary lower bounds in the list of the unexplored nodes in the list. In this case, Lbest=L.
Raghunathan ¶ [0067] After a node has been processed but the termination conditions for BB have not been satisfied and there exist nodes yet unanalyzed the BB procedure proceeds by selecting one of unanalyzed nodes and calculating the upper and lower bounds for the particular specification of the feasible region. ¶ [0068] For instance, suppose region R2 is selected to be analyzed and upper and lower bounding problems are solved to obtain U2,L2 respectively in Fig.8A. Further suppose U2−L2<τ and U2=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R2 and the globally optimal solution > objective value than best solution identified from previous explorations in the BB tree. In such case, the node R2 820 is deemed as fathomed (shown in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far. The list of unexplored nodes 810 now only includes R1. Also, there is no update of Ubest,Lbest since U2=Ubest and Lbest determined from the list of unexplored nodes is still L. ¶ [0069] The node R1 is explored and the upper and lower bounding problems are solved to obtain U1,L1 respectively in Fig.9A. In this case, suppose (U1−L1) and (U1−L1)/U1 and (Ubest−L) are all > predetermined threshold r and U1<Ubest. Hence, update Ubest=U1. Because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 in Fig.9B. The resulting BB tree 900 and the list of unexplored nodes 910 are shown in Fig.9C. The unexplored nodes inherit the lower bounds from the parent node R1 and hence, Lbest which is based on the lower bound of unexplored nodes is set to L1.
Raghunathan ¶ [0070] Suppose R3 is selected to be explored from the list of unexplored nodes and the upper, lower bounds be computed for R3 as respectively U3,L3 in Fig.10 A. Further suppose that U3-L3<τ and U3=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R3 and the globally optimal solution has same objective value as the best solution identified from previous explorations in the BB tree. In such case, node R3 is deemed as fathomed (in Fig.10B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained thus far. The list of unexplored nodes 1010 of the BB tree 1000 now only includes R4. Also, there is no update of Ubest,Lbest since U3=Ubest and Lbest determined from the list of unexplored nodes is still L1.
Raghunathan ¶ [0071] node R4 is explored and upper, lower bounds U4,L4 are obtained for the feasible region corresponding to R4 in Fig.11A. Further suppose U4-L4<τ and U4>Ubest. In this case, a globally optimal solution has been obtained for region corresponding to the node R4 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (shown in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than best upper bound solution that has been obtained thus far. The list of unexplored nodes is now empty. At this point the globally optimal solution has been found and it is the solution corresponding to the upper bound of U1=Ubest. ¶ [0072] In other words, if there is optimality gap, then the feasible region is partitioned into 2 sub-regions, over which the BB procedure is repeated. Nodes are deleted (in branch and bound terms fathomed X) when lower bound L > current best upper bound. The BB procedure terminates when all nodes have been processed. In that case, the best upper bounding solution is returned as globally optimal solution.
Raghunathan ¶ [0073] Figs.12A-B show another example, in which the upper bounding solution for R1 1210 satisfies the sufficient condition 622 in Fig.6B. In this case, L1=U1 is set as in 626 of Fig.6B. By step 627 of Fig.6B, the lowest upper bound is updated as Ubest=U1. The BB algorithm proceeds to step 645 in Fig.6A and deletes the node R1 1220 in Fig.12B. At this point, there are no more nodes to be evaluated and the algorithm returns the upper bounding solution for R1 as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings.
Raghunathan ¶ [0074] Figs.13A-B show another example, in which the upper bounding solution for R1 does not satisfy the sufficient condition 622 but the sufficient condition in 624 is satisfied. Then, proceeding as per Fig.6B the upper bound for the node is updated as U1=L1 and the best upper bound for the BB tree is updated as Ubest=U1. In this case proceeding 625 of Fig. 6A it is clear the upper and lower bound for the node are within tolerance and the algorithm proceeds to 645 of FIG. 6A. The current node R1 is fathomed as in Fig.13B. Since there are no more nodes in the BB tree the lower bounding solution is returned as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings)
- 3. “generating” “(a) one or more interim results from partial execution of the optimization calculation” (Raghunathan ¶ [0047] According to [branch and bound] BB framework, if lower bound for some tree node (set of candidates) A > upper bound for some other node B, then A may be safely discarded from the search. This step is called pruning, and is implemented by maintaining a global variable m (shared among all nodes of the tree) that records minim upper bound seen among all subregions examined so far) “and” “(b) information indicating a violation status for each of one or more constraints” (Raghunathan ¶ [0063] 1st sentence: If lower & upper bound (U−L), or (U−L)/U 630 or (Ubest−L) 635 < predetermined threshold τ, then the current node is deleted from BB tree 645. ¶ [0064] 1st sentence: If (Ubest−Lbest), or optionally (Ubest−Lbest)/Ubest, < predetermined threshold τ 655, then the to [branch and bound] BB method terminates with the current lowest upper bounding solution 660. Also ¶ [0065] 4th,7th,9th sentences: If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. If the sufficient condition 622 does not hold then, the lower bounding problem is solved 623. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. ¶ [0069] 3rd sentence: noting a different example where, because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 as shown in Fig. 9B)
- 4. … “iteratively executing” (Raghunathan ¶ [0046] Branch & bound (BB) for finding optimal solutions of various optimization problems and includes of iterative enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded by using upper 253 and lower 257 bounds of the quantity being optimized. ¶ [0048] 1st sentence: noting an example that determine 250 iteratively upper 253 and lower 257 bounds of the objective function. In addition, in one embodiment, the lower bounds on the optimal objective function are determined using a semi-definite programming (SDP) 255 relaxation of optimal power flow (OPF) problem. ¶ [0052] noting an example at Fig.3A showing flow chart performing optimization 220 using BB framework 240. The method splits 310 iteratively a feasible region of the OPF problem into a nested tree of regions corresponding to a BB tree, wherein the nested tree of regions includes a first region 311 and a second region 312 nested in the first region. Similarly, ¶ [0102])
= “one or more of the stages with updated constraints excluding”
(Raghunathan ¶ [0063] If lower bound and upper bound (U−L), or (U−L)/U 630 or (Ubest−L) 635 < predetermined threshold τ, then the current node is deleted from the BB tree 645.
Raghunathan ¶ [0072] 2nd sentence Nodes are deleted (in branch & bound terms fathomed X) when the lower bound L > current best upper bound. ¶ [0073] 4th sentence: The BB algorithm proceeds to step 645 in Fig.6A and deletes the node R1 1220 as shown in Fig.12B) “or”
= “modifying a violated constraint”
(Raghunathan ¶ [0014] 2nd sentence: optimizing, objective function representing an operation of the power grid using a spatial branch and bound (BB) framework for determining iteratively upper and lower bounds of the objective function, wherein the lower bounds are determined using a semi-definite programming (SDP) relaxation [or modification] of an optimal power flow (OPF) problem. ¶ [0044] 2nd sentence: Some embodiments of the invention are based on a realization that OPF problem can be solved based on the spatial branch and bound framework with lower bounds on the optimal objective function value calculated by solving a semi-definite programming (SDP) relaxation [or modification] of the OPF. Similarly, ¶ [0048] 2nd sentence: the lower bounds on optimal objective function are determined using a semi-definite programming (SDP) 255 relaxation [or modification] of an optimal power flow (OPF) problem. Another example at ¶ [0053] 3rd sentence: the tree is used to determine the global minimum for the OPF by constructing a convex relaxation of the feasible region R associated with the OPF that is easier to solve and provides a lower bound (L) on the optimal objective function value. ¶ [0056] last sentence: noting yet another example that uses a solution of the OPF problem corresponding to the lower bound of the first region as an input to the SDP relaxation [or modification] for determining the lower bound of the second region. ¶ [0100] The equality constraints in the semidefinite relaxation. Also ¶ [0102], ¶ [0104]); “and”
- 5. “when the optimization calculation” [still] “cannot be completed”, “retrieving” “a latest interim result” “for display” (Raghunathan ¶ [0068] 3rd-5th sentences: globally optimal solution has been obtained for region corresponding to node R2 and globally optimal solution has larger objective value than best solution identified from previous explorations in BB tree. In such a case, node R2 820 is deemed as fathomed (shown [or displayed] in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained so far. The list of unexplored nodes 810 now only includes R1. Similarly,
Raghunathan ¶ [0070] 3rd-5th sentences: a globally optimal solution has been obtained for region corresponding to node R3 and the globally optimal solution has same objective value as best solution identified from previous explorations in the BB tree. In such case, node R3 is deemed as fathomed (shown [or displayed] in Fig.10B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained thus far. The list of unexplored nodes 1010 of the BB tree 1000 now only includes R4.
Raghunathan ¶ [0071] 2nd-3rd sentences: a globally optimal solution has been obtained for region corresponding to node R4 and globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (as shown [or displayed] in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far) or
“when the optimization calculation is completed using at least one of the updated constraints”, “generating” “a result of the optimization calculation comprising the complete solution for display” (Raghunathan ¶ [0068]-¶ [0073] with emphasis on ¶ [0072] 3rd- 4th sentences: The BB procedure terminates when all nodes have been processed. In that case, the best upper bounding solution is returned as the globally optimal solution. ¶ [0073] Figs.12A-B show [or display] an example, where upper bounding solution for R1 1210 satisfies the sufficient condition 622 in Fig. 6B. In this case, L1=U1 is set as in 626 of Fig.6B. By step 627 of FIG. 6B, the lowest upper bound is updated as Ubest=U1. The BB algorithm proceeds to step 645 in FIG. 6A and deletes the node R1 1220 as shown [or displayed] in Fig.12B. At this point, there are no more nodes to be evaluated and the algorithm returns the upper bounding solution for R1 as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings).
Thus, the prior art teaches the contested features and the argument is unpersuasive.
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.
Claims 1-15 are 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 pre-AIA the applicant regards as the invention.
Claims 1,12 are independent and have been amended to each recite, among others:
- “(vii) responsive to the information indicating a violation associated with at least a violated constraint of the one or more constraints, iteratively executing” (Claim 1) / “execute” (Claim 12), “by the processor, one or more of the plurality of stages with updated constraints excluding or modifying the violated constraint”; (Claims 1,12) rendering each of said claims vague and indefinite because it is unclear how “one” [single] stage “of the plurality of stages” as covered by broad expression “one or more of the plurality of stages” would be “iteratively” executed when read in light of the Original Specification.
Claims 1,12 are recommended to be amended to recite, as an example only, “iteratively executing” (Claim 1) / “execute” (Claim 12), at least two stages “of the plurality of stages”
Claims 2-11,15 are dependent and rejected based on rejected parent independent Claim 1.
Claims 13,14 are dependent and rejected based on rejected parent independent Claim 12.
Clarification and/or correction is/are required.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Claim Rejections - 35 USC § 101
35 U.S.C. 101 reads as follows:
Whoever invents or discovers any new and useful process, machine, manufacture, or composition of matter, or any new and useful improvement thereof, may obtain a patent therefor, subject to the conditions and requirements of this title.
Claims 1-15 are rejected under 35 U.S.C. 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea, here abstract idea) without significantly more. Here, the claims1, recite, describe or set forth, a fundamental, thus abstract practice or principle [MPEP 2106.04(a)(2) II A] of planning namely “power grid planning” as summarized by the Title of the Application and by the preamble of Claims 12-14 within the broad Certain Method of Organizing Human Activities grouping [MPEP 2106.04(a)(2)II] implemented through equally abstract mathematical calculations & relationships expressed in words [MPEP 2106.04(a)(2) I A,C] as evidenced throughout the body of Claims 1-15 by language such as objective and constraint functions, constraints, optimization calculation, decomposition method, definitions of one or more variables, constants, and data sets etc., which, at their turn, are used in what appear to be computer-aided [MPEP 2106.04(a)(2) III C #1,2,3] mental processes of observation, evaluation, and judgment, [MPEP 2106.04(a)(2) III C] such as collecting information, analyzing it, and displaying certain results of the collection and analysis, as exemplified by Electric Power Group v. Alstom, S.A., 830 F.3d 1350, 1353-54, 119 USPQ2d 1739, 1741-42 (Fed. Cir. 2016) and cited by MPEP 2106.04(a)(2) III. For example, in Electric Power Group v. Alstom, S.A., 830 F.3d 1350, 1353-54, 119 USPQ2d 1739, 1741-42 (Fed Cir 2016), the Court ruled the claims were ineligible despite accumulating and updating the measurements from the data streams and the dynamic stability metrics, grid data, and non-grid data in real time over the wide area of the interconnected electric power grid.
- Here, as in Electric Power Group, the claims similarly recite collection or “receiving” of “one or more constraints on the power grid”, and “input data related to the power grid” (independent Claims 1,12, dependent Claim 15), “receiving one or more invalidations and/or edits to the constraint(s) received in step (ii)” (dependent Claim 4), “receiving a plurality of constraint functions, (independent Claims 1,12, and dependent Claim 6) “representing respective one or more constraints on the power grid, wherein the objective function and the one or more constraint functions together represent model of the power grid” (independent Claims 1,12), “and the method further comprises receiving an order in which the constraint functions are to be applied” (dependent Claim 6), “receiving a priority for the subset of constraints, and/or a maximum number of constraints to be generated at once” (dependent Claim 8), “receiving definitions of one or more variables, definitions of one or more constants, and definitions of one or more data sets” (dependent Claim 9), “receiving a request” “to perform the trial calculation” (dependent Claim 11)
- Here, as in Electric Power Group supra and MPEP 2106.04(a)(2) III C, the current claims similarly set forth an analysis or computer-aided evaluation, through what appear to be equally abstract mathematical relationships expressed in words [MPEP 2106.04(a)(2) I (A)] and mathematical calculations [MPEP 2106.04(a)(2) I (C)] represented here by:
(iv) “a trial calculation based on the model of the power grid and the input data to determine whether a complete solution is expected from the optimization calculation” [akin to proof of concept, or order-of-magnitude estimation] “for executing the optimization calculation (a) as a single optimization problem” [akin to sensitivity analysis] or (b) in a plurality of stages” [akin to boundary and constraint testing], followed by equally abstract judgment based evaluations:
(v) “responsive to an output of the trial calculation indicating that the complete solution is not expected”, “executing” “the optimization calculation in the plurality of stages representing different constraint-applying methods of the one or more constraints”;
(vi) “generating”, “during execution of the plurality of stages, at least: (a) “one or more interim results from partial execution of the optimization calculation and stored in the memory and (b) information indicating a violation status for each of the one or more constraints”
(vii) “responsive to the information indicating a violation associated with at least a violated constraint of the one or more constraints, iteratively executing”, “one or more of the plurality of stages with updated constraints excluding or modifying the violated constraint”
(independent Claims 1,12)
do akin to similar approaches such as Rolle’s theorem, divide and conquer, heuristics and approximation, set forth the abstract mathematical calculations of MPEP 2106.04(a)(2) (I) C and/or the abstract mathematical relationships expressed in words of MPEP 2106.04(a)(2)(I) (A).
The same principles and rationales apply to:
“executing” “the optimization calculation as the single optimization problem” “responsive to the output of the trial calculation indicating that the complete solution is expected”.
(dependent Claims 2,13)
“applying a decomposition method to the objective function and the one or more constraint functions, so as to arrive at a plurality of sub-problems representing the objective function, wherein the plurality of sub-problems with the objective function applied with the decomposition method and the one or more constraint functions represent the model of the power grid”
(dependent Claim 5)
“applying a constraint generation method to one or more of the one or more constraint functions, the constraint generation method applying a sub-set of constraints and adding additional constraints sequentially”
(dependent Claim 7),
“provides one or more of the constraint functions and/or constraint applying methods”
(dependent Claim 10).
Finally, with respect to: (viii) “when the optimization calculation cannot be completed after iteratively executing the one or more of the plurality of stages, retrieving” “at latest interim result of the one or more interim results” “and generating the latest interim result” “for display”; and
and (ix) “when the optimization calculation is completed using at least one of the updated constraints, generating” “for display” “a result of the optimization calculation comprising the complete solution”, (independent Claims 1,12 dependent Claim 15), and “providing the calculated interim result(s) to the user” (dependent Claims 3,14), “the trial calculation, indicating whether the complete solution is expected from the optimization calculation defined by the model of the power grid and the input data” (dependent Claim 11), the Examiner points to Electric Power Group supra, and finds said limitations (viii) and (ix) to recite, describe or set forth, the abstract displaying certain results of the collection and analysis as of what appear to be equally abstract heuristics, iterative refinement or approximation, as abstract mathematical calculations of MPEP 2106.04(a) (2)(I)C and/or abstract mathematical relationships expressed in words of MPEP 2106.04(a)(2)(I) (A) following the aforementioned judged evaluations of MPEP 2106.04(a)(2) III ¶2.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
This judicial exception is not integrated into a practical application because per Step 2A prong two, the individual or combination of the additional, computer-based elements are/is found, to merely narrow the abstract character of the claims to a field of use or technological environment, or at most, apply the aforementioned abstract exception. Here, the computer-based additional elements are “one or more processors” of dependent Claims 12-15, the “memory” of
Claims 1,12-14, and possibly the “user interface” of Claims 1,3,12,14 and “reinforcement learning system” of dependent Claim 10, which if not already representative of computer-aids, at the above step, represent mere additional elements, as invocation of machinery or components of a computer that merely apply the above identified abstract concepts above through execution of mathematical algorithms2 [here “reinforcement learning system” etc.], which, as identified above, perform a business planning practice. Yet, per MPEP 2106.05(f)(2)(i), such computerization or automation does not integrate the abstract idea into a practical application.
Also per MPEP 2106.05(f)(2)(iii) and MPEP 2106.05(f)(2) ¶1, the capabilities of the additional computer-based elements, as identified above to monitor audit log data3 [here related to the power grid], and to receive and transmit [here display, indicating etc.] data4 also represent mere invocation of computer execution as tools to perform the aforementioned abstract idea or existing processes, and thus again do not integrate said abstract exception into a practical application. The same principles apply to the capabilities of the additional computer-based elements, as tested per MPEP 2106.05(f)(2) v,ii, to tailor information and provide it to user on a computer5, relevant here to (ix) “generating, by the processor, for display via the user interface, a result of the optimization calculation comprising the complete solution” at independent Claims 1,12 and dependent Claim 15, “providing the calculated interim result(s) to the user” at dependent Claims 3,14. Also, it can perhaps be argued that here, when tested per MPEP 2106.05(h)6, the additional, computer-based elements above, could also be argued to represent a narrowing of the combination of collecting information, analyzing, and displaying certain results of the collection and analysis to a technological environment represented by computerization (“one or more processors”, “memory”, “interface”, “reinforcement learning system”) and applicability to a “power grid”, which, again would not integrate the abstract exception into a practical application.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
The claim(s) does/do not include additional elements that are sufficient to amount to significantly more than the judicial exception because as shown above, the additional computer-based elements merely apply the already recited abstract idea and link the use of abstract idea to a field of use or technological environment. Specifically, Examiner follows MPEP 2106.05 (d) II guidelines and carries over the findings tested per MPEP 2106.05 (f) and/or (h) to submit that the additional computer-based elements also do not provide significantly more without having to rely on the conventionality test. Yet assuming arguendo, that further evidence would be required to demonstrate conventionality of the additional, computer-based elements, the Examiner would also point as evidence on case law (MPEP 2106.05(d) II) and/or the high level of generality of the additional elements. For example, MPEP 2106.05(d) (II) finds electronic recordkeeping7 and gathering statistics8 [akin here to objective and constraint functions, constraints, optimization calculation, decomposition method, definitions of variables, constants, and data sets, as well as “one or more interim results from partial execution of the optimization calculation and stored in the memory” etc.], performing repetitive calculations9 [here “(vii) responsive to the information indicating a violation associated with at least a violated constraint of the one or more constraints, iteratively executing, by the processor, one or more of the plurality of stages with updated constraints excluding or modifying the violated constraint”; “(viii) when the optimization calculation cannot be completed after iteratively executing the one or more of the plurality of stages, retrieving, by the processor, a latest interim result of the one or more interim results from the memory and generating the latest interim result for display via a user interface”
and possibly “(iv) executing, by the processor, prior to executing an optimization calculation, a trial calculation based on the model of the power grid and the input data to determine whether a complete solution is expected from the optimization calculation for executing the optimization calculation (a) as a single optimization problem or (b) in a plurality of stages;(v) responsive to an output of the trial calculation indicating that the complete solution is not expected, automatically executing, by the processor, the optimization calculation in the plurality of stages representing different constraint-applying methods of the one or more constraints”;], arranging groups hierarchy, sorting10 and determining and estimated outcome11 [here optimization of objective function, whether a complete solution is expected from the optimization calculation etc.] are well understood routine or conventional.
If still necessary, Examiner would also follow MPEP 2106.05(d) I.2.(a), and point as evidence for conventionality of the additional computer-based elements as read in light of Specification:
- Original Specification p.7 ¶3-p.8 ¶1: Fig.1 shows an example of a power grid planning support system 1. The power grid planning support system may also be referred to as a power grid planning support tool. The tool 1 is provided, in this example, as a general computer having a central control unit 11, arithmetic logic unit 12, input unit 13,output unit 14,main memory unit 15, and auxiliary memory unit 16. These units are connected to each other via computer bus 17. The auxiliary memory unit 16 includes one or more databases 18 and one or more programs 19. The "processing functions" discussed below with reference to Figure 2 are realised by the central control unit 11 loading programs stored in the auxiliary memory unit 16 into the main memory unit 15. The output unit 14 may comprise a display device or may be a component which provides an output to a display device or other a user terminal (so as to be displayed by the terminal).
- Original Specification p.25 ¶2-¶3: “While the disclosure has been described in conjunction with the exemplary embodiments described above, many equivalent modifications and variations will be apparent to those skilled in the art when given this disclosure. Accordingly, the exemplary embodiments of the disclosure set forth above are considered to be illustrative and not limiting. Various changes to the described embodiments may be made without departing from the spirit and scope of the disclosure. For the avoidance of any doubt, any theoretical explanations provided herein are provided for the purposes of improving the understanding of a reader. The inventors do not wish to be bound by any of these theoretical explanations. Any section headings used herein are for organizational purposes only and are not to be construed as limiting the subject matter described”.
In conclusion, Claims 1-15 although directed to statutory categories (“method” or process at Claims 1-11, “system” or machine at Claim 12-14, and “non-transitory medium” or computer product at Claim 15) they still recite or set forth the abstract idea (Step 2A prong one), with their additional, computer-based elements not integrating the abstract idea into a practical application (Step 2A prong two) or providing significantly more than the abstract idea itself (Step 2B).
In conclusion, Claims 1-15 are patent ineligible.
Claim Rejections - 35 USC § 102
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1,2,4-9,11-13 and 15 are rejected under 35 U.S.C. 102(a)(1) based upon a public use or sale or other public availability of the invention as disclosed by:
Raghunathan et al, US 20150199606 A1 hereinafter Raghunathan. As per,
Claims 1,12,15 Raghunathan teaches “A method comprising steps of”: / “A power grid planning support system, comprising one or more processors and memory, the memory containing machine executable instructions which, when executed on the one or more processors cause the one or more processors to: / A non-transitory computer-readable storage medium containing machine executable instructions which, when executed on one or more processors, cause the one or more processors to perform the method set out in claim 1”([0044]-]0048],[0076])
- (i) “receiving, by a processor coupled with memory, an objective function, the objective function representing a quantity or parameter associated with a power grid”;
(Raghunathan ¶ [0014] 2nd sentence: optimizing, using a processor, an objective function representing power grid operation using spatial branch and bound (BB) framework for determining iteratively upper & lower bounds of the objective function, the lower bounds determined using a semi-definite programming (SDP) relaxation of an optimal power flow (OPF) problem.
Raghunathan ¶ [0045] and Fig. 2, 210->221 noting objective function 221 representing an operation of the power grid using a spatial branch and bound (BB) framework 240. ¶ [0009] 2nd sentence, ¶ [0102] 2nd sentence noting the usage of the ADMM method for SDP relaxation in a current iteration of the branch and bound method allows reusing the outputs of the previous iteration of the branch and bound method to accelerate the convergence of the method. ¶ [0007]
Raghunathan ¶ [0070] 3rd sentence: a globally optimal solution obtained for region corresponding to node R3 and the globally optimal solution has same objective value as the best solution identified from previous explorations in the BB tree. ¶ [0076] 1st sentence: the power grid includes at least one storage system, and the objective function represents the operation of the power grid over time. ¶ [0099], ¶ [0102] 3rd sentence: The objective function of the OPF problem is typically quadratic in the real power from generators. ¶ [0105] 1st sentence noting total objective function 1530 obtained by summing over the individual time-step components. Similarly, ¶ [0109] and ¶ [0110] 1st sentence: including an augmented Lagrangian term in the objective)
- (ii) “receiving, by the processor, one or more constraint functions, representing respective one or more constraints on the power grid” (Raghunathan ¶ [0049] input 210 optimization 20 includes
1) A graph G(N,E) with set of N nodes connected by a set of E edges (i,j).
2) admittance of the lines yij=gij+jbij (i,j)εE, where g represents conductance of the line, b represents susceptance (imaginary part of the admittance) of the line with j=√-1.
3) Constraints on active power PiG,min,PiG,max I ε N produced by the generators, and the reactive power Qi G,min,Qi G,max∀iεN that can be produced by the generators.
4) Constraints Sijmax,Pij max∀(i,j)εE on apparent and active power transferred on the lines. 5) Limits Vimin,Vimax ∀iεN on voltage magnitudes at the buses.
6) Constraints Lij max∀(i,j)εE on thermal losses on the lines),
“wherein the objective function and the one or more constraint functions together represent a model of the power grid”; (Raghunathan ¶ [0044] Fig.2 shows system and method determining a power flow of power grid according to some embodiments of the invention. Some embodiments of the invention are based on a realization that OPF problem can be solved based on the spatial branch and bound framework with lower bounds on the optimal objective function value calculated by solving a semi-definite programming (SDP) relaxation of the OPF. Those embodiments are based on recognition that search space of the solutions and constraints of OPF problem can be partitioned using structure and characteristics of the elements of the power grid, and thus the branch and bound framework can be utilized to search for the global minimum.
Raghunathan ¶ [0105] Fig.15 shows graphical representation of the time coupled problem in terms of single time-step constraints 1505, time coupling constraints 1510, single time-step objective function contributions 1520 and total objective function 1530 obtained by summing over the individual time-step components. In one embodiment, augmented Lagrangian formulation is used to decompose the Multi-period Optimal Power Flow problem by dualizing only the time coupled constraints in eq (2). The constraints are the dynamics equation for the batteries and the ramp limits for the power generation. The first step in the decomposition is to introduce additional variables and rewriting the time-coupled constraints involving the variables Bi(t), PiG(t), QiG(t).
Raghunathan ¶ [0109] Fig.16 shows a graphical representation of the time coupled problem after the introduction of the additional variables in terms of single time-step constraints 1605, time coupling constraints 1610, single time-step objective function contributions 1620 and total objective function 1630 obtained by summing over the individual time-step components.
Raghunathan ¶ [0110] The second step includes dualizing the constraints involving Bi(t), PiG(t), QiG(t) and also including an augmented Lagrangian term in the objective. Prior to this the following notation is introduced for convenience.
Raghunathan [0113] Fig17 shows graphical representation of dual augmented Lagrangian problem with coupling in the objective in terms of single time-step constraints 1705, single time-step objective function contributions 1710, time coupling portion of the objective 1720 and the total objective function 1730 obtained by summing over the individual time-step components.
Raghunathan ¶ [0114] In optimization problem (7) the constraints do not involve coupling between the variables across time steps. The coupling across time-steps still exists in the objective function through the quadratic terms introduced in the augmented Lagrangian formulation, which is resolved using the ADMM)
- (iii) “receiving, by the processor, input data related to the power grid”; (Raghunathan ¶ [0049] input 210 includes 1) graph G(N,E) with set of N nodes connected by a set of E edges (i,j). 2) admittance of lines yij=gij+jbij (i,j)εE, where g represents conductance of the line, b represents susceptance (imaginary part of admittance) of the line with j=√-1 5) Limits Vimin,Vimax ∀iεN on voltage magnitudes at the buses. 6) Constraints Lij max∀(i,j)εE on thermal losses on the lines).
- “(iv) “executing, by the processor, prior to executing an optimization calculation, a trial calculation based on the model of the power grid and the input data to determine whether a complete solution is expected from the optimization calculation for executing the optimization calculation (a) as a single optimization problem or (b) in a plurality of stages”;
(Raghunathan ¶ [0005] 2nd sentence: search space of the solutions and constraints of the OPF problem partitioned using structure and characteristics of the elements of the power grid, and thus the branch and bound framework can be utilized to search for the global minimum.
Raghunathan ¶ [0007] Some embodiments of the invention are based on an additional realization that the branch and bound method should be implemented such that a search for the lowest lower and upper bound in a nested region can use, as starting point, the result of the search in the region from which the nested region was partitioned according to the branch and bound principles. This realization is based in part on the recognition that the structure of the power grid has patterns or similarities repeated over the span of the grid. Thus, the result of the search in one region can be used to speed up the search over a different region.
Raghunathan ¶ [0056] 2nd-3rd sentences: some embodiments of the invention are based on an additional realization that the branch and bound method should be implemented such that a search for the lowest lower and upper bound in a nested region can use, as a starting point, the result of the search in the region from which the nested region was partitioned according to the branch and bound principles. This realization is based in part on the recognition that the structure of the power grid has patterns or similarities repeated over the span of the grid.
Raghunathan ¶ [0065] 3rd-10th sentences: Using the obtained solution a sufficient condition for the upper bound solution to be a globally optimal solution is checked 622. If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. Instead, the lower bound for the node is set to that of the upper bound 626. Then, the lower upper bound for the BB tree is updated 627 and the algorithm proceeds to 645 of the flowchart in FIG. 6A. If the sufficient condition 622 does not hold then, the lower bounding problem is solved 623. The solution of the lower bounding problem is checked 623 if it satisfies a sufficient condition that allows constructing an upper bound solution with same objective value as the lower bound solution. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. If the lower bound sufficient condition 623 holds then, the upper bound for the node is set to that obtained from the lower bound 628 and the upper bound solution is set to that obtained from the lower bounding problem 629. The algorithm then proceeds to 629. For example see
Raghunathan Figs.7-12 ->R2->R3->R4, ¶ [0066] 2nd-3rd sentences: global optimum cannot be determined from R shown in Fig.7B, feasible region R is partitioned into R1 and R2, and the BB procedure is repeated. The resulting BB tree 700 after the partition is shown in Fig.3C.
Raghunathan ¶ [0067] After a node has been processed but the termination conditions for BB have not been satisfied and there exist nodes that are yet unanalyzed the BB procedure proceeds by selecting one of the unanalyzed nodes and calculating the upper and lower bounds for the particular specification of the feasible region.
Raghunathan ¶ [0068] For instance, suppose the region R2 is selected to be analyzed and upper and lower bounding problems are solved to obtain U2,L2 respectively as shown in FIG. 8A. Further suppose that U2−L2<τ and U2=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R2 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R2 820 is deemed as fathomed (as shown in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0069] 3rd sentence: Because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 in Fig. 9B.
Raghunathan ¶ [0071] 3rd-4th sentences: a globally optimal solution has been obtained for region corresponding to the node R4 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (as shown in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0072] 1st sentence: if there is an optimality gap, then the feasible region is partitioned into two sub-regions, over which the BB procedure is repeated
Raghunathan ¶ [0127] 3rd -5th sentences: A significant advantage of ADMM algorithm is that if a good initial guess is available for the problem (8) then the algorithm converges quickly. Such a behavior cannot be expected for interior point algorithms for semidefinite programs. This property is commonly called as warm-starting and is important especially when semidefinite programs are to be solved as part of a branch and bound algorithm as described earlier) “and”
- (v) “responsive to an output of the trial calculation indicating that the complete solution is not expected, automatically executing, by the processor, the optimization calculation in the plurality of stages representing different constraint-applying methods of the one or more constraints”; (Raghunathan ¶ [0048] 3rd-5th sentences: Usually, the branch and bound methods are implemented using linear under-approximation of the optimized function, because solution of such approximation can be efficiently performed. However, the embodiments recognized that in the context of the power flow analysis of the power grid, the linear under-approximation of the cost function representing the power flow is inefficient due to the over approximation of the feasible region that results from linear approximations. Hence, it was realized that despite of solution complexity of the SDP over the linear under-approximation, the usage of the SDP approximation in the context of the power grids is advantageous.
Raghunathan ¶ [0064] If (Ubest−Lbest) or (Ubest−Lbest)/Ubest<predetermined threshold τ 655, then BB terminates with current lowest upper bounding solution 660. Otherwise another node from BB tree 615 is selected to update/improve lower and upper bound using the solving steps.
Raghunathan ¶ [0065] Fig.6B shows block diagram of the BB method, in which the solution of the upper and lower bounding problem 620 is expanded. The upper bound problem for the node is solved 621 first. Using the obtained solution a sufficient condition for the upper bound solution to be a globally optimal solution is checked 622. If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. Instead, the lower bound for the node is set to that of upper bound 626. Then, the lower upper bound for BB tree is updated 627 and the algorithm proceeds to 645 of e flowchart in Fig.6A. If sufficient condition 622 does not hold then, the lower bounding problem is solved 623. The solution of lower bounding problem is checked 623 if it satisfies a sufficient condition that allows constructing an upper bound solution with same objective value as the lower bound solution. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. If the lower bound sufficient condition 623 holds then, the upper bound for the node is set to that obtained from the lower bound 628 and the upper bound solution is set to that obtained from the lower bounding problem 629. The algorithm then proceeds to 629. Typically, the computation of the lower bound is expensive and then sufficiency check in 622 can help in avoiding unnecessary calculations when the upper bound problem is indeed able to solve the node to global optimality.
Raghunathan ¶ [0024]-¶ [0030] Figs. 7-13 are examples of different stages of BB method
Raghunathan ¶ [0066] after the solution of upper and lower bounding problems for root node R, Ubest is set to U. Further, (U−L), and (U−L)/U and (Ubest−L) are all larger > predetermined threshold T. In this case, global optimum cannot be determined from R and in Fig.7B, the feasible region R is partitioned into R1 and R2, and BB procedure is repeated. The resulting BB tree 700 after the partition is shown in Fig.3C. Now R1 and R2 are placed in a list of nodes 710 that need to be explored and are temporarily assigned the lower bound L based on the lower bound obtained from the parent node R as shown in Fig. 3C. Following this, Lbest can be updated as the smallest of the temporary lower bounds in the list of the unexplored nodes in the list. In this case, Lbest=L.
Raghunathan ¶ [0067] After a node has been processed but the termination conditions for BB have not been satisfied and there exist nodes yet unanalyzed the BB procedure proceeds by selecting one of unanalyzed nodes and calculating the upper and lower bounds for the particular specification of the feasible region. ¶ [0068] For instance, suppose region R2 is selected to be analyzed and upper and lower bounding problems are solved to obtain U2,L2 respectively in Fig.8A. Further suppose U2−L2<τ and U2=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R2 and the globally optimal solution > objective value than best solution identified from previous explorations in the BB tree. In such case, the node R2 820 is deemed as fathomed (shown in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far. The list of unexplored nodes 810 now only includes R1. Also, there is no update of Ubest,Lbest since U2=Ubest and Lbest determined from the list of unexplored nodes is still L. ¶ [0069] The node R1 is explored and the upper and lower bounding problems are solved to obtain U1,L1 respectively in Fig.9A. In this case, suppose (U1−L1) and (U1−L1)/U1 and (Ubest−L) are all > predetermined threshold r and U1<Ubest. Hence, update Ubest=U1. Because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 in Fig.9B. The resulting BB tree 900 and the list of unexplored nodes 910 are shown in Fig.9C. The unexplored nodes inherit the lower bounds from the parent node R1 and hence, Lbest which is based on the lower bound of unexplored nodes is set to L1.
Raghunathan ¶ [0070] Suppose R3 is selected to be explored from the list of unexplored nodes and the upper, lower bounds be computed for R3 as respectively U3,L3 in Fig.10 A. Further suppose that U3-L3<τ and U3=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R3 and the globally optimal solution has same objective value as the best solution identified from previous explorations in the BB tree. In such case, node R3 is deemed as fathomed (in Fig.10B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained thus far. The list of unexplored nodes 1010 of the BB tree 1000 now only includes R4. Also, there is no update of Ubest,Lbest since U3=Ubest and Lbest determined from the list of unexplored nodes is still L1.
Raghunathan ¶ [0071] node R4 is explored and upper, lower bounds U4,L4 are obtained for the feasible region corresponding to R4 in Fig.11A. Further suppose U4-L4<τ and U4>Ubest. In this case, a globally optimal solution has been obtained for region corresponding to the node R4 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (shown in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than best upper bound solution that has been obtained thus far. The list of unexplored nodes is now empty. At this point the globally optimal solution has been found and it is the solution corresponding to the upper bound of U1=Ubest. ¶ [0072] In other words, if there is optimality gap, then the feasible region is partitioned into 2 sub-regions, over which the BB procedure is repeated. Nodes are deleted (in branch and bound terms fathomed X) when lower bound L > current best upper bound. The BB procedure terminates when all nodes have been processed. In that case, the best upper bounding solution is returned as globally optimal solution.
Raghunathan ¶ [0073] Figs.12A-B show another example, in which the upper bounding solution for R1 1210 satisfies the sufficient condition 622 in Fig.6B. In this case, L1=U1 is set as in 626 of Fig.6B. By step 627 of Fig.6B, the lowest upper bound is updated as Ubest=U1. The BB algorithm proceeds to step 645 in Fig.6A and deletes the node R1 1220 in Fig.12B. At this point, there are no more nodes to be evaluated and the algorithm returns the upper bounding solution for R1 as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings.
Raghunathan ¶ [0074] Figs.13A-B show another example, in which the upper bounding solution for R1 does not satisfy the sufficient condition 622 but the sufficient condition in 624 is satisfied. Then, proceeding as per Fig.6B the upper bound for the node is updated as U1=L1 and the best upper bound for the BB tree is updated as Ubest=U1. In this case proceeding 625 of Fig. 6A it is clear the upper and lower bound for the node are within tolerance and the algorithm proceeds to 645 of FIG. 6A. The current node R1 is fathomed as in Fig.13B. Since there are no more nodes in the BB tree the lower bounding solution is returned as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings)
- (vi) “generating, by the processor, during execution of the plurality of stages, at least:
(a) “one or more interim results from partial execution of the optimization calculation and stored in the memory” (Raghunathan ¶ [0047] According to [branch and bound] BB framework, if lower bound for some tree node (set of candidates) A > upper bound for some other node B, then A may be safely discarded from the search. This step is called pruning, and is implemented by maintaining [or storing] a global variable m (shared among all nodes of the tree) that records [or stores] minim upper bound seen among all subregions examined so far), “and”
(b) information indicating a violation status for each of the one or more constraints”; (Raghunathan ¶ [0063] 1st sentence: If lower bound and upper bound (U−L), or (U−L)/U 630 or (Ubest−L) 635 < predetermined threshold τ, then the current node is deleted from the BB tree 645. ¶ [0064] 1st sentence: If (Ubest−Lbest), or optionally (Ubest−Lbest)/Ubest, < predetermined threshold τ 655, then the to [branch and bound] BB method terminates with the current lowest upper bounding solution 660. Also ¶ [0065] 4th,7th,9th sentences: If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. If the sufficient condition 622 does not hold then, the lower bounding problem is solved 623. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in Fig.6A. ¶ [0069] 3rd sentence: noting a different example where, because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 as shown in Fig. 9B)
- (vii) “responsive to the information indicating a violation associated with at least a violated constraint of the one or more constraints, iteratively executing, by the processor, one or more of the plurality of stages” (Raghunathan ¶ [0046] Branch & bound (BB) is a method for finding optimal solutions of various optimization problems and includes of iterative enumeration of all candidate solutions, where large subsets of fruitless candidates are discarded by using upper 253 and lower 257 bounds of the quantity being optimized. ¶ [0048] 1st sentence: noting an example that determine 250 iteratively upper 253 and lower 257 bounds of the objective function. In addition, in one embodiment, the lower bounds on the optimal objective function are determined using a semi-definite programming (SDP) 255 relaxation of optimal power flow (OPF) problem. ¶ [0052] noting an example at Fig.3A showing a flow chart of a method for performing the optimization 220 using the BB framework 240 according to some embodiments. The method splits 310 iteratively a feasible region of the OPF problem into a nested tree of regions corresponding to a BB tree, wherein the nested tree of regions includes a first region 311 and a second region 312 nested in the first region. Similarly, ¶ [0102]) “with updated constraints excluding” (Raghunathan ¶ [0063] If lower bound and upper bound (U−L), or (U−L)/U 630 or (Ubest−L) 635 < predetermined threshold τ, then the current node is deleted from the BB tree 645. ¶ [0072] 2nd sentence: Nodes are deleted (in branch and bound terms fathomed X) when the lower bound L is greater than the current best upper bound. ¶ [0073] 4th sentence: The BB algorithm proceeds to step 645 in FIG. 6A and deletes the node R1 1220 as shown in Fig.12B) “or modifying the violated constraint” (Raghunathan
¶ [0014] 2nd sentence: optimizing, an objective function representing an operation of the power grid using a spatial branch and bound (BB) framework for determining iteratively upper and lower bounds of the objective function, wherein the lower bounds are determined using a semi-definite programming (SDP) relaxation [or modification] of an optimal power flow (OPF) problem. ¶ [0044] 2nd sentence: Some embodiments of the invention are based on a realization that OPF problem can be solved based on the spatial branch and bound framework with lower bounds on the optimal objective function value calculated by solving a semi-definite programming (SDP) relaxation [or modification] of the OPF. Similarly, ¶ [0048] 2nd sentence: the lower bounds on optimal objective function are determined using a semi-definite programming (SDP) 255 relaxation [or modification] of an optimal power flow (OPF) problem. Another example at ¶ [0053] 3rd sentence: the tree is used to determine the global minimum for the OPF by constructing a convex relaxation of the feasible region R associated with the OPF that is easier to solve and provides a lower bound (L) on the optimal objective function value. ¶ [0056] last sentence: noting yet another example that uses a solution of the OPF problem corresponding to the lower bound of the first region as an input to the SDP relaxation [or modification] for determining the lower bound of the second region. ¶ [0100] The equality constraints in the semidefinite relaxation. Also ¶ [0102], ¶ [0104]);
- (viii) “when the optimization calculation cannot be completed after iteratively executing the one or more of the plurality of stages, retrieving, by the processor, a latest interim result of the one or more interim results from the memory and generating the latest interim result for display via a user interface”; (Raghunathan ¶ [0068] 3rd-5th sentences: globally optimal solution has been obtained for region corresponding to node R2 and globally optimal solution has a larger objective value than best solution identified from previous explorations in the BB tree. In such a case, node R2 820 is deemed as fathomed (shown [or displayed] in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained so far. The list of unexplored nodes 810 now only includes R1. Similarly,
Raghunathan ¶ [0070] 3rd-5th sentences: a globally optimal solution has been obtained for region corresponding to node R3 and the globally optimal solution has same objective value as best solution identified from previous explorations in the BB tree. In such case, node R3 is deemed as fathomed (shown [or displayed] in Fig.10B by X) since exploration of any further partition of its feasible region cannot result in a solution better than best upper bound solution obtained thus far. The list of unexplored nodes 1010 of the BB tree 1000 now only includes R4.
Raghunathan ¶ [0071] 2nd-3rd sentences: a globally optimal solution has been obtained for region corresponding to node R4 and globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (as shown [or displayed] in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far) “and”
- (ix) “when the optimization calculation is completed using at least one of the updated constraints, generating, by the processor, for display via the user interface, a result of the optimization calculation comprising the complete solution”
(Raghunathan ¶ [0068]-¶ [0073] with emphasis on ¶ [0072] 3rd- 4th sentences: The BB procedure terminates when all nodes have been processed. In that case, the best upper bounding solution is returned as the globally optimal solution. ¶ [0073] Figs.12A-B show [or display] an example, where upper bounding solution for R1 1210 satisfies the sufficient condition 622 in Fig. 6B. In this case, L1=U1 is set as in 626 of Fig.6B. By step 627 of FIG. 6B, the lowest upper bound is updated as Ubest=U1. The BB algorithm proceeds to step 645 in FIG. 6A and deletes the node R1 1220 as shown [or displayed] in Fig.12B. At this point, there are no more nodes to be evaluated and the algorithm returns the upper bounding solution for R1 as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings).
Claims 2,13 Raghunathan teaches all limitations in claims 1,12 above. Further,
Raghunathan teaches “responsive to the output of the trial calculation indicating that the complete solution is expected, automatically executing, by the processor, the optimization calculation as the single optimization problem” (Raghunathan ¶ [0120] steps 2a-c. are repeated until [or responsive to] convergence criterion in step 2d is satisfied. Step 1 still involves solving a considerably large SDP for a single time-step. The next section shows how this computation can also be made efficient using the ADMM. ¶ [0121] ADMM for Single Time-Step Optimal Power Flow. ¶ [0122] The single time-step problem resulting from time decoupling described in previous section results in the following SDP can be succinctly represented. ¶ [0135] Exploiting Structure in the Solution of the Single Time-Step Optimal Power Flow. ¶ [0136] computationally demanding task in the ADMM algorithm presented for (9) is the eigenvalue decomposition that is involved in the solution of optimization problem for Xk+1 in Step 2b. To address this computational bottleneck the graph of the electrical network can be exploited. The graph G(N,E) induced by the typical electrical network is sparse in the sense that there does not exist an electrical line between every pair of buses in the network. This sparsity can be exploited to decompose the positive semidefinite constraint in (9) which is on a matrix of size 2|N|×2|N| into a number of positive semidefinite constraint of smaller sized matrices. This also allows the eigenvalue step computation to be parallelized and allows speeding up of the algorithm).
Claim 4. Raghunathan teaches all limitations in teaches all limitations in claim 1 above. Further
Raghunathan teaches “receiving one or more invalidations and/or edits to the one or more constraints received in step (ii), such that the optimization calculation is performed without the one or more invalidations to the one or more constraints and/or with the edits to the one or more constraints” (Raghunathan ¶[0014] 2nd sentence: optimizing, objective function representing an operation of the power grid using a spatial branch and bound (BB) framework for determining iteratively upper and lower bounds of the objective function, wherein the lower bounds are determined using a semi-definite programming (SDP) relaxation [or edit] of an optimal power flow (OPF) problem. ¶ [0044] 2nd sentence: Some embodiments of the invention are based on realization that OPF problem can be solved based on the spatial branch and bound framework with lower bounds on the optimal objective function value calculated by solving a semi-definite programming (SDP) relaxation [or edit] of the OPF. Similarly, ¶ [0048] 2nd sentence: the lower bounds on optimal objective function are determined using a semi-definite programming (SDP) 255 relaxation [or edit] of an optimal power flow (OPF) problem. Another example at ¶ [0053] 3rd sentence: the tree is used to determine the global minimum for the OPF by constructing a convex relaxation of the feasible region R associated with the OPF that is easier to solve and provides a lower bound (L) on the optimal objective function value. ¶ [0056] last sentence: noting yet another example that uses a solution of the OPF problem corresponding to the lower bound of the first region as an input to the SDP relaxation [or edit] for determining the lower bound of the second region. ¶ [0100] The equality constraints in the semidefinite relaxation. Also ¶ [0102], ¶ [0104]);
Claim 5. Raghunathan teaches all limitations in teaches all limitations in in claim 1 above. Further,
Raghunathan teaches: “applying a decomposition method to the objective function and the one or more constraint functions, so as to arrive at a plurality of sub-problems representing the objective function, wherein the plurality of sub-problems with the objective function applied with the decomposition method and the one or more constraint functions represent the model of the power grid” (Raghunathan ¶ [0104] SDP relaxations of the multi-period optimal power flow problem tend to be large scale problems. Thus some embodiments use decomposition methods to solve the problems effectively. For example, they take advantage from recognition that the computational efficiency of the ADMM method can be improved by decomposing the semidefinite constraint in the SDP into semidefinite constraints on smaller blocks based on the electrical network. This approach allows accelerating the computation and further increases the efficiency of the branch and bound method. ¶ [0105] 1st - 3rd sentences: an augmented Lagrangian formulation used to decompose Multi-period Optimal Power Flow problem by dualizing only the time coupled constraints in eq (2). The constraints are the dynamics equation for the batteries and the ramp limits for the power generation. The first step in the decomposition is to introduce additional variables and rewriting the time-coupled constraints involving the variables Bi (t), Pi G(t), Qi G(t). Also ¶ [0129]-¶ [0142] noting a different example of Maximal Clique Decomposition)
Claim 6 Raghunathan teaches all limitations in teaches all limitations in in claim 1 above. Further
Raghunathan teaches “wherein step (ii) includes receiving a plurality of constraint functions, and the method further comprises receiving an order in which the plurality of constraint functions are to be applied” (Raghunathan ¶ [0040] 3rd sentence: the variables and constraints that control the operation of the power grid are continuously controllable. Fig.15, steps 1510
->1505->1520 ¶ [0105] 4th sentence: the first [or initial] step in the decomposition is to introduce additional variables and rewriting the time-coupled constraints involving the variables Bi (t), Pi G(t), Qi G(t). Then decoupling at ¶ [0106]-¶ [0108]. Similarly Fig.16 steps 1610->1605->1620, Fig.17 steps 1705->1710->1720)
Claim 7 Raghunathan teaches all limitations in teaches all limitations in in claim 1 above. Further
Raghunathan teaches “applying a constraint generation method to one or more of the one or more constraint functions, the constraint generation method applying a subset of constraints and adding additional constraints sequentially”
(Raghunathan ¶ [0105] 2nd-3rd sentence: augmented Lagrangian formulation is used to decompose Multi-period Optimal Power Flow problem by dualizing only the time coupled constraints in eq (2). The constraints are the dynamics equation for the batteries and ramp limits for the power generation. The 1st step in the decomposition is to introduce additional variables and rewriting the time-coupled constraints involving the variables Bi (t),Pi G(t),Qi G(t). Also,
Raghunathan ¶ [0109] Fig.16 shows a graphical representation of the time coupled problem after introduction of the additional variables in terms of single time-step constraints 1605, time coupling constraints 1610, single time-step objective function contributions 1620 and the total objective function 1630 obtained by summing over the individual time-step components).
Claim 8 Raghunathan teaches all limitations in teaches all limitations in in claim 7 above. Further
Raghunathan further teaches
- “receiving a priority for the subset of constraints” (Raghunathan Fig.15, priority steps 1510->1505->1520 ¶ [0105] 4th sentence: 1st step in decomposition is to introduce additional variables and rewriting the time-coupled constraints involving variables Bi (t), Pi G(t), Qi G(t). Then decoupling at ¶ [0106] - ¶ [0108]. Similarly see Fig.16 priority given by steps 1610->1605->1620, Fig.17, 1705->1710->1720) “and/or a maximum number of constraints to be generated at once”
Claim 9. Raghunathan teaches all limitations in teaches all limitations in in claim 1 above. Further
Raghunathan teaches “wherein step (i) includes receiving definitions of one or more variables” (Raghunathan ¶ [0049] input 210 the optimization 20 includes: 1) A graph G(N,E) with set of N nodes connected by set of E edges (i,j). 2) admittance of the lines yij=gij+jbij (i,j)εE, where g represents conductance of the line, b represents susceptance (imaginary part of the admittance) of the line with j=√-1. 3) Constraints on active power PiG,min,PiG,max I ε N produced by the generators, and reactive power Qi G,min,Qi G,max∀iεN that can be produced by the generators. 4) Constraints Sijmax,Pij max∀(i,j)εE on apparent and active power transferred on the lines. 5) Limits Vimin,Vimax ∀iεN on voltage magnitudes at the buses. 6) Constraints Lij max∀(i,j) ε E on thermal losses on the lines),), “definitions of one or more constants” (Raghunathan ¶ [0078], the form of the function ƒ is quadratic and strictly increasing:
PNG
media_image2.png
64
472
media_image2.png
Greyscale
Also, ¶ [0123] 3rd sentence: For convenience of providing the definitions, lower and upper bounds are specified for all the variables by introducing additional parameters [or constants]).
Claim 11 Raghunathan teaches all the limitations in claim 1 above.
- “receiving a request, before executing the optimization calculation, to perform a trial calculation” (Raghunathan ¶ [0004] there is a need to optimize the power grid of various structures and configurations considering multiple time periods of optimization)“the method further including”
- “performing the trial calculation, the trial calculation indicating whether a complete solution is expected from the optimization calculation defined by the model of the power grid and the input data” (Raghunathan ¶ [0127] 2nd-6th sentences: A significant advantage of using ADMM algorithm is that if a good initial guess is available for the problem (8) then the algorithm converges quickly. Such a behavior cannot be expected for interior point algorithms for semidefinite programs. This property is commonly called as warm-starting and is important especially when semidefinite programs are to be solved as part of a branch and bound algorithm as described earlier. The warm-starting property of the ADMM allows to improve the overall computational efficiency of the branch-and-bound process. ¶ [0102] 2nd sentence: the usage of the ADMM method for SDP relaxation in a current iteration of the branch and bound method allows reusing the outputs of tprevious iteration of the branch and bound method to accelerate the convergence of the method
Raghunathan ¶ [0065] Fig.6B shows a block diagram of one embodiment of BB method, in which the solution of the upper and lower bounding problem 620 is expanded. The upper bound problem for the node is solved 621 first. Using the obtained solution a sufficient condition for the upper bound solution to be a globally optimal solution is checked 622. If the sufficient condition 622 holds then the lower bounding problem for the node is not solved. Instead, the lower bound for the node is set to that of the upper bound 626. Then, the lower upper bound for the BB tree is updated 627 and the algorithm proceeds to 645 of the flowchart in FIG. 6A. If the sufficient condition 622 does not hold then, the lower bounding problem is solved 623. The solution of the lower bounding problem is checked 623 if it satisfies a sufficient condition that allows constructing an upper bound solution with same objective value as the lower bound solution. If the lower bound sufficient condition does not hold then algorithm proceed to 625 in FIG. 6A. If the lower bound sufficient condition 623 holds then, the upper bound for the node is set to that obtained from the lower bound 628 and the upper bound solution is set to that obtained from the lower bounding problem 629. The algorithm then proceeds to 629. Typically, the computation of the lower bound is expensive and then sufficiency check in 622 can help in avoiding unnecessary calculations when the upper bound problem is indeed able to solve the node to global optimality.
Raghunathan Figs.7-12 ->R2->R3->R4, ¶ [0066] 2nd-3rd sentences: global optimum cannot be determined from R shown in Fig.7B, feasible region R is partitioned into R1 and R2, and the BB procedure is repeated. The resulting BB tree 700 after the partition is shown in Fig.3C.
Raghunathan ¶ [0067] After a node has been processed but the termination conditions for BB have not been satisfied and there exist nodes that are yet unanalyzed the BB procedure proceeds by selecting one of the unanalyzed nodes and calculating the upper and lower bounds for the particular specification of the feasible region.
Raghunathan ¶ [0068] For instance, suppose the region R2 is selected to be analyzed and upper and lower bounding problems are solved to obtain U2,L2 respectively as shown in FIG. 8A. Further suppose that U2−L2<τ and U2=Ubest. In this case, a globally optimal solution has been obtained for region corresponding to node R2 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R2 820 is deemed as fathomed (as shown in Fig.8B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0069] 3rd sentence: Because the termination condition is not satisfied the feasible region corresponding to R1 is further partitioned into regions R3 and R4 in Fig. 9B.
Raghunathan ¶ [0071] 3rd-4th sentences: a globally optimal solution has been obtained for region corresponding to the node R4 and the globally optimal solution has a larger objective value than the best solution identified from previous explorations in the BB tree. In such a case, the node R4 is deemed as fathomed (as shown in Fig.11B by X) since exploration of any further partition of its feasible region cannot result in a solution that is better than the best upper bound solution that has been obtained thus far.
Raghunathan ¶ [0072] 1st sentence: if there is an optimality gap, then the feasible region is partitioned into two sub-regions, over which the BB procedure is repeated
Raghunathan ¶ [0073] Figs.12A-B show another example, in which the upper bounding solution for R1 1210 satisfies the sufficient condition 622 in Fig.6B. In this case, L1=U1 is set as in 626 of Fig.6B. By step 627 of Fig.6B, the lowest upper bound is updated as Ubest=U1. The BB algorithm proceeds to step 645 in Fig.6A and deletes node R1 1220 in Fig.12B. At this point, there are no more nodes to be evaluated and the algorithm returns the upper bounding solution for R1 as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings.
Raghunathan ¶ [0074] Figs.13A-B show another example, in which the upper bounding solution for R1 does not satisfy the sufficient condition 622 but the sufficient condition in 624 is satisfied. Then, proceeding as per Fig.6B the upper bound for the node is updated as U1=L1 and the best upper bound for the BB tree is updated as Ubest=U1. In this case proceeding 625 of FIG. 6A it is clear the upper and lower bound for the node are within tolerance and the algorithm proceeds to 645 of Fig.6A. The current node R1 is fathomed as in FIG. 13B. Since there are no more nodes in the BB tree the lower bounding solution is returned as the globally optimal solution. The algorithm exploits the satisfaction of the sufficient condition to avoid exploring the BB tree further and this leads to significant computational savings.
Raghunathan ¶ [0140] Upper Bound-Based Sufficient Condition
Raghunathan ¶ [0141] 1st -2nd sentence: The upper bound based sufficient condition is used to verify if the obtained solution is a globally optimal solution. This is possible in the case of MOPF since it is an instance of a quadratically constrained quadratic program.
Raghunathan ¶ [0143] Lower Bound-Based Sufficient Condition
Raghunathan ¶ [0144] 1st -2nd sentences: The sufficient condition for the lower bound to be a globally optimal solution is to simply check if in the solution to (2), the matrices w(t) have rank less than or equal to 2. This again is a simple check that can be performed quickly).
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Rejections under 35 § U.S.C. 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 of this title, 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.
This application currently names joint inventors. In considering patentability of the claims the examiner presumes that the subject matter of the various claims was commonly owned as of the effective filing date of the claimed invention(s) absent any evidence to the contrary. Applicant is advised of the obligation under 37 CFR 1.56 to point out the inventor and effective filing dates of each claim that was not commonly owned as of the effective filing date of the later invention in order for the examiner to consider the applicability of 35 U.S.C. 102(b)(2)(C) for any potential 35 U.S.C. 102(a)(2) prior art against the later invention.
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 3,14 are rejected under 35 U.S.C. 103 as being unpatentable over:
Raghunathan as applied to parent claims 1,12 above, and in view of
Slutsker et al, US 20140278817 A1 hereinafter Slutsker. As per,
Claims 3,14 Raghunathan teaches all the limitations in claims 1,12 above. Further,
Raghunathan teaches at ¶ [0068], ¶ [0070], ¶ [0071] global optimum cannot be determined and the feasible region cannot result in a solution, but does not explicitly recite: - “indicating to a user, via the user interface, that the optimization calculation cannot be completed and providing the one or more interim results to the user” as claimed. However,
Slutsker in analogous managing energy generation teaches or at least suggests:
- “indicating to a user, via the user interface, that the optimization calculation cannot be completed” (Slutsker ¶ [0014] 3rd-4th sentences: The solver sends information that the problem is not solvable if the objective function cannot be minimized/maximized, as applicable, to optimize costs while bound by all constraints. If the module receives such information an equation error is reported to user (step 118) ¶ [0043] 1st-2nd sentences: Fig.4 illustrates an optional functionality, hereinafter described as a slack functionality, that may be activated if a solver determines that the problem presented to it is not solvable. As in the embodiment illustrated by Fig.1, this embodiment would respond by sending an equation error to the user (step 118)) “and”
- “providing the one or more interim results to the user” (Slutsker ¶ [0030] 3rd-5th sentences: The module then performs a check on the Inputs 104 (step 108) to ensure that all Inputs 104 fall within feasible values. If the Inputs 104 are not valid the module will proceed to report the improper data (step 110). In this embodiment the data error is reported to a user (step 110) through a user interface, but in an embodiment not initiated by a user the data error could be reported to another part of a larger program or system in which the module is integrated)
It would have been obvious to one skilled in the art, before the effective filling date of the claimed invention, to have modified Raghunathan’s “method”/“system” to have included Slutsker’s teachings or suggestions to have more rigorously improved upon computation accuracy or efficiency of Raghunathan algorithms (Slutsker ¶[0018]-[0021] in view of MPEP 2143 G and/or F) by creating operating plans for generation utilization or evaluating the impacts of potential energy trade opportunities within a defined zone of generation assets (Slutsker ¶ [0022]-¶ [0023] in view of MPEP 2143 G and/or F). Predictability of such modification would have been corroborated by the broad level of skill of one of ordinary skills in the art as articulated by Slutsker ¶ [0051].
Further, the claimed invention could have also been viewed as a mere combination of old elements in a similar energy-related field of endeavor. In such combination, each element would have merely performed same analytical and notification or display function as it did separately. Thus, one of ordinary skill in the art would have recognized that, given the existing technical ability to combine the elements as evidenced by Raghunathan in view of Slutsker, the to be combined elements would have fitted together, like pieces of a puzzle, in a logical, complementary, technologically feasible and/or economically desirable manner. Thus, it would have been reasoned that the results of the combination would have been predictable (MPEP 2143 A).
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over:
Raghunathan as applied to parent claim 1 above, and in view of
Ye et al, US 20240330396 A1 hereinafter Ye. As per,
Claim 10. Raghunathan teaches all the limitations in claim 1 above.
Raghunathan does not explicitly recite:
- “wherein a reinforcement learning system provides one or more of the one or more constraint functions and/or constraint applying methods” as explicitly claimed.
Ye in analogous energy management problem of a microgrid teaches or suggests:
- “wherein a reinforcement learning system provides one or more of the one or more constraint functions and/or constraint applying methods”.
(Ye ¶ [0037] the microgrid spatial-temporal perception energy management method based on safe deep reinforcement learning transforms an energy management problem of a microgrid into a constrained Markov decision process, and considers stochasticity of exogenous factors, such as variability [as exemplary constrain] of renewable energy generation and demand. By using advantages of ECC and LSTM networks, a feature extraction network is built to extract spatial-temporal related features of an operating status of the microgrid, which enhances the generalization capability of a control policy, solves the control policy by using most advanced IPO method, enhances spatial-temporal perception on operating status of microgrid, and promotes learning in multi-dimensional and continuous states and action spaces. The quality of energy management policies is improved, and distribution network related constraints are satisfied).
It would have been obvious to one skilled in the art, before the effective filling date of the claimed invention, to have further modified Raghunathan’s “method” to have included Ye’s teachings or suggestions in order to have provided a microgrid spatial-temporal perception energy management method based on safe deep reinforcement learning, which would have enhanced perception on an MG spatial-temporal operating status, safeguarded the secure operation of the distribution network, improved MG cost efficiency, and achieved superior energy management policy cost efficiency, and uncertainty adaptability (Ye ¶ [0005] in view of MPEP 2143 G and/or F). The predictability of such modification would have been corroborated by the broad level of skills of one of ordinary skills in the art as articulated by Raghunathan in view Ye ¶ [0038], [0048].
Further, the claimed invention could have also been viewed as a mere combination of old elements in a similar energy-related field of endeavor. In such combination, each element would have merely performed same analytical and notification or display function as it did separately. Thus, one of ordinary skill in the art would have recognized that, given the existing technical ability to combine the elements as evidenced by Raghunathan in view of Ye, the to be combined elements would have fitted together, like pieces of a puzzle, in a logical, complementary, technologically feasible and/or economically desirable manner. Thus, it would have been reasoned that the results of the combination would have been predictable (MPEP 2143 A).
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Conclusion
The following art is made of record and considered pertinent to Applicant's disclosure:
- Omi S,Nakayama Y,Kawamoto N,Optimal placement of synchronous condensers based on Benders decomposition with taking into account short-circuit and network constraints, In2023 IEEE PES Innovative Smart Grid Technologies Europe, pp1-5, Oct 23,2023, teaching at its p. 2, 2nd column that S. Hadavi et al. proposed a method based on the semi-definite optimisation
to determine the installation capacity and location of synchronous condensers.
- WO 2021219656 A1 teaching Power grid resource allocation
US 20200212681 A1 Method, apparatus and storage medium for transmission network expansion planning considering extremely large amounts of operation scenarios
US 20220115867 A1 Advanced power distribution platform
US 20150317584 A1 Conservation modeling engine framework
US 20110227417 A1 Renewable Energy Delivery Systems and Methods
US 20070185729 A1 System for negotiating green tags or fixed price energy contracts
US 20130179202 A1 Method and system for analysis of infrastructure
US 20060276938 A1 Optimized energy management system
US 20050165511 A1 Energy network
US 20220320868 A1 Method and electronic device for dispatching power grid
US 7130832 B2 Energy service business method and system
US 20020087234 A1 System, method and computer program product for enhancing commercial value of electrical power produced from a renewable energy power production facility
US 20080195255 A1 Utility grid, controller, and method for controlling the power generation in a utility grid
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to OCTAVIAN ROTARU whose telephone number is (571)270-7950. The examiner can normally be reached on 571.270.7950 from 9AM to 6PM. If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, PATRICIA H MUNSON, can be reached at telephone number (571)270-5396. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300. Information regarding the status of an application may be obtained from Patent Center. Status information for published applications may be obtained from Patent Center. Status information for unpublished applications is available through Patent Center for authorized users only. Should you have questions about access to Patent Center, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). 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) Form at https://www.uspto.gov/patents/uspto-automated- interview-request-air-form.
/Octavian Rotaru/
Primary Examiner, Art Unit 3624 A
June 3rd, 2026
1 MPEP 2106.04(a): “examiners should identify at least one abstract idea grouping, but preferably identify all groupings to the extent possible”.
Electric Power Group v. Alstom, S.A., 830 F.3d 1350, 1353-54, 119 USPQ2d 1739, 1741-42 (Fed. Cir. 2016)
2 Alice Corp Pty Ltd V. CLS Bank Int’l, 573 U.S. 208,223,110 USPQ2d 1976, 1983 (2014);
Gottschalk v. Benson, 409 U.S.63,64,175 USPQ 673,674 (1972)
Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015);
3 FairWarning IP, LLC v. Iatric Sys., 839 F.3d 1089, 1095, 120 USPQ2d 1293, 1296 (Fed. Cir. 2016)
4 Affinity Labs v. DirecTV, 838 F.3d 1253, 1262, 120 USPQ2d 1201, 1207 (Fed. Cir. 2016) (cellular telephone); TLI Communications LLC v. AV Auto, LLC, 823 F.3d 607, 613, 118 USPQ2d 1744, 1748 (Fed. Cir. 2016)
Intellectual Ventures I LLC v. Capital One Bank (USA), 792 F.3d 1363, 1367, 115 USPQ2d 1636, 1639 (Fed. Cir. 2015).
5 Intellectual Ventures I LLC v. Capital One Bank (USA), 792 F.3d 1363, 1370-71, 115 USPQ2d 1636, 1642 (Fed. Cir. 2015)
6 Electric Power Group, LLC v. Alstom S.A., 830 F.3d 1350, 1354, 119 USPQ2d 1739, 1742 (Fed. Cir. 2016)
7 Alice Corp. Pty. Ltd. v. CLS Bank Int'l, 573 U.S. 208, 225, 110 USPQ2d 1984 (2014), Ultramercial, 772 F.3d at 716, 112 USPQ2d at 1755
8 OIP Techs., 788 F.3d at 1362-63, 115 USPQ2d at 1092-93
9 Flook, 437 U.S. at 594, 198 USPQ2d at 199 (recomputing or readjusting alarm limit values);
Bancorp Services v. Sun Life, 687 F.3d 1266, 1278, 103 USPQ2d 1425, 1433 (Fed. Cir. 2012)
10 Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1331, 115 USPQ2d 1681, 1699 (Fed. Cir. 2015).
11 OIP Techs., 788 F.3d at 1362-63, 115 USPQ2d at 1092-93
Prosecution Insights