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
The following NON-FINAL Office action is in response to application 18659949 filed 05/09/2024.
Status of Claims
Claims 1-15 are currently pending and have been rejected as follows.
Priority
Receipt is acknowledged of papers submitted under 35 U.S.C. 119(a)-(d), which papers have been placed of record in the file.
IDS
The information disclosure statement filed on 05/09/2024 and 05/16/2025 complies with the provisions of 37 CFR 1.97, 1.98 and MPEP § 609 and is considered by the Examiner.
Objections
Claims 1,12 are independent and each objected for informally reciting at limitation (ii) “constraint function(s)” instead of grammatically correct one or more constraint functions.
Claims 12-14 are objected for informally reciting at its preamble …“when executed on the processor(s) cause the processor(s)” … instead of grammatically correct, when executed on the one or more processors cause the one or more processors”
Claim 3 is dependent and objected for informally reciting, among others: “interim result(s) to the user” instead of grammatically correct one or more interim results to the user.
Claim 4 is dependent and objected for informally reciting “constraint(s)” repeatedly throughout said claim, instead of grammatically correct one or more constraints.
Claim 5 is dependent and objected for informally reciting constraint function(s), instead of grammatically correct one or more constraint functions.
Corrections are required.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 recite among others: (ii) “receiving one or more constraint functions, the or each constraint function representing constraints on the power grid, the objective function and constraint function(s) together representing a model of the power grid”; [bolded emphasis added] rendering each of said claims vague and indefinite because there is insufficient antecedent basis for “the or”. Specifically, given the extensive use of abbreviations in the claims as identified by examiner above, it is now unclear if expression “the or” was meant to refer to a previously recited “or” abbreviation, or to “or” as a coordinating conjunction. Given the claim record above, the Examiner reasons that such issue becomes one of lack of antecedent basis and unclarity rather than one of pure grammatical informalities.
Claims 1,12 are recommended to be amended to each recite, among others, and as an example only: (ii) receiving one or more constraint functions, each of the one or more constraint functions representing constraints on the power grid, the objective function and the one or more constraint functions ;
Claims 2-11,15 are dependent and rejected upon rejected parent independent Claim 1.
Claims 13,14 are dependent and rejected based on rejected parent independent Claim 12.
Claims 3 is dependent and further recites “the calculated interim result(s)”, while sister
Claim 14 is also dependent on the sister claims’ branch tree, and similarly recites, among others, “the calculated interim results” [bolded emphasis added]
Claims 3,14 are rendered vague and indefinite because there is insufficient antecedent basis for “the calculated interim result(s)” (plural at Claim 3) and “the calculated interim results” (plural at Claim 14), when their parent dependent Claims 2,13 would cover only a single one result, as broadly covered by expression “calculating one or more interim results”
Claims 3,14 are recommended to be amended to each recite, among others, and as an example only: the calculated one or more interim results.
Claims 7,10 are dependent and each recite, among others: “one or more of the constraint functions”, rendering each of said claims vague and indefinite because it is unclear if “one or more of the constraint functions”, as subsequently recited in said dependent claims 7,10 relate back to “one or more constraint functions” as antecedently recited at parent independent Claim 1.
Claims 7,10 are recommended be amended to each recite, among others, and as an example only: the “one or more constraint functions”
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 of planning namely “power grid planning” [MPEP 2106.04(a)(2) II A] within the broad Certain Method of Organizing Human Activities grouping implementable through equally abstract mathematical calculations and relationships expressed in words [MPEP 2106.04(a)(2) I A,C], evidenced 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 “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, 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 sub-set 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 a trial calculation, the method further including performing the trial calculation, the trial calculation indicating whether a complete solution is expected from the optimisation calculation defined by the model of the power grid and the input data” (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, represented by: “(iv) executing an optimisation calculation defined by the model of the power grid and the input data” (independent Claims 1,12 and dependent Claim 15); “calculating one or more interim results when the execution of the optimisation calculation returns, as a result, an indication that the optimisation calculation cannot be completed” (dependent Claims 2,13), “applying a decomposition method to the objective function and constraint function(s), so as to arrive at a plurality of sub-problems representing the objective function, wherein the plurality of sub-problems with the decomposed objective function and constraint function(s) represent the model of the power grid” (dependent Claim 5), “applying a constraint generation method to one or more of the 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 1).
- Here, as in MPEP 2106.04(a)(2) III C, the current claims perform a computer-aided judgment set forth by “indicating to a user that the optimisation calculation cannot be completed” (dependent Claim 3, and similarly at dependent Claim 14) and “performing the trial calculation, the trial calculation indicating whether a complete solution is expected from the optimisation calculation defined by the model of the power grid and the input data” (dependent Claim 11)
- Here, as in Electric Power Group supra, the current claims similarly recite, describe or set forth, displaying certain results of the collection and analysis as: “(v) displaying a result of the optimisation calculation” (independent Claims 1,12 and dependent Claim 15), “providing the calculated interim result(s) to the user” (dependent Claims 3,14)
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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 and possibly “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 already 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 “(v) displaying a result of the optimisation calculation” 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”, “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 etc.], performing repetitive calculations9 [“performing the trial calculation, the trial calculation indicating whether a complete solution is expected from the optimisation calculation defined by the model of the power grid and the input data”], arranging groups hierarchy, sorting10 and determining and estimated outcome11 [here optimisation of objective function] 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,13, 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,12,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: Xiaoming et al, US 20210334911 A1 hereinafter Xiaoming. As per,
Claims 1,12,15 Xiaoming teaches “A power grid planning support method, implemented on a computer, the method comprising steps of”: / “A power grid planning support system, the system comprising one or more processors and memory, the memory containing machine executable instructions which, when executed on the processor(s) cause the processor(s) to (Xiaoming ¶ [0077]): / A non-transitory computer-readable storage medium containing machine executable instructions which, when executed on one or more processors (Xiaoming ¶ [0077]), cause the processors to perform the method set out in claim 1
- (i) “receiving an objective function, the objective function representing a quantity or parameter associated with a power grid”; (Xiaoming ¶ [0002] 1st-2nd sentences: obtain generation resource and demand (price sensitive) commitment and dispatch in power grid of all generators over scheduling horizon to minimize total generation cost while meeting all system-wide constraints i.e system load balance, reserve requirements, individual unit operating constraints. For example, at ¶ [0023] 2nd-4th sentences: The goal of the resource allocation schedule is to clear market offer and bid while maximizing total welfare or minimize total cost. the goal may be to satisfy energy demand that minimizes energy production costs while being subject to constraints of reliability and emissions. In another example, the goal may be to maximize energy production profits, e.g. difference between revenues (from sales of electricity) and costs (from production of electricity). Also Fig.6, ¶ [0061] 2nd sentence noting: In block 503, the objective coefficient of dual sub-problems are updated according to Equation (3) and the LR dual sub-problems are solved)
- (ii) “receiving one or more constraint functions, the or each constraint function representing constraints on the power grid, the objective function and constraint function(s) together representing a model of the power grid”; (Xiaoming ¶ [0003] since a typical power grid is being driven to operate more and more close to its security margin, security-related transmission constraints are included to constrain the unit commitment. Thus, typical power system resources scheduling involves security constrained unit commitment (SCUC), where security constraints may be transmission line thermal capacity constraints for base case operating condition and contingent operating conditions. SCUC is used in day ahead, intra-day and real time power grid scheduling. In solving for security constrained unit commitment, minim-cost operation schedule for generators (e.g. power plants) is determined over a scheduling horizon. For example, a minimum-cost operation schedule is identified that satisfies operation constraints of each generator unit, the electric network constraints in the base case network topology, and various operator specified contingency scenarios. Also ¶ [0019] 4th sentence: Depending on power plant type, each of power resources 101 may be subject to complex technical and business constraints, such as minim up/down time, ramp up/down rate, modulation/stability (unit may not change its production level too many times), and start-up/shut-down ramp rate (when starting / stopping, a unit follows a specific power curve which depend on how long the plant has been offline/online.
Xiaoming ¶ [0023] 1st sentence: the resource allocation schedule are generated by solving the security constrained unit commitment system while taking into consideration of the operational info (various constraints) of power grid 100, such as the constraints of power resources 101 (e.g., generation capacity and operating margin including safe operating ranges), constraints of the transmission grid 103, market info (e.g. bidding info, cost info, predicted demand info, regulatory requirements such as emission target). Fig.2 and ¶ [0025], at block 10, a power grid resource allocation profile indicative of an operation of the power grid constrained by operational info of the power grid is generated by power management system (PMS) of the power grid. The power management system may be, a market management system (MMS) or emergency management system (EMS) of the power grid. In some embodiments, the operational info comprises info for constraining operation of the power grid and comprises security-related transmission constraint info and cost info. In some embodiments, generating the power grid resource allocation profile comprises formulating the power grid resource allocation profile as a Security Constrained Unit Commitment (SCUC) system (or problem) based on mixed integer programming (MIP). In the discussion herein, the term mixed integer programming (MIP) may be used interchangeably with mixed integer linear programming (MILP). mid-¶ [0037] finding decision vectors xi, i=1, 2,…N, that minimize the loss (or cost) function shown in Eq (1) while satisfying the various constraints.
Xiaoming ¶ [0043] 1st sentence: Typically, an MIP solver, through a series of branch-and-bound (B&B) operations and/or a series of branch-and-cut (B&C) operations, searches through the vector space of the decision vectors to find integer feasible solutions with lower and lower upper bounds, thereby gradually approach the optimum solution (e.g. a set of decision vectors xi that correspond to a minimum loss function). Also see ¶ [0066] 5th sentence noting setting the initial conditions. Other details at ¶ [0037]-¶ [0038],¶ [0056]-¶ [0057])
- (iii) “receiving input data related to the power grid”; (Xiaoming Fig.2, block 10, Fig.3 and
¶ [0035] 2nd sentence noting SCUC model 131 is defined by grid data 132 and market data applied to SCUC model 131. ¶ [0036] PMS 105 includes SCUC Solver 134, to generate SCUC Solution 135 (e.g. resource allocation schedule). SCUC Solver 134 implement blocks 20 and 30. ¶ [0043] 3rd sentence: MIP solver updates, in multiple iterations/steps, the values for the decision vectors such that the loss function decreases as time goes by, until MIP solver reaches a final solution, which is optimum solution of the security constrained unit commitment system or is close enough to the optimum solution.¶ [0060] Fig.6 illustrates flow chart for method 500 solving dual problem in Eq (2.2), which is Lagrangian Relaxation (LR) of security constrained unit commitment system of Eq (1). ¶ [0061] Referring to Fig.6, at block 501, the Lagrangian multiplier vector A is initialized. In block 503, the objective coefficient of the dual sub-problems are updated according to Eq (3) and the LR dual sub-problems are solved. A corresponding lower bound of the SCUC system is calculated. Note that LR sub-problem solvers may be used to solve the dual sub-problems in parallel. In block 505, a sub-gradient is calculated using current solution. In block 507, a correction value is calculated for Lagrangian multiplier vector A using calculated sub-gradient. In block 509, the algorithm checks if current solution satisfies the coupling constraints and calculates a corresponding upper bound for the SCUC system using the current solution. Note that if current solution does not satisfy all coupling constraints, the upper bound calculated may be a loose upper bound (either UB of positive infinity or finite UB depending on magnitude of slack variables needed to make the infeasible coupling constraints feasible, and penalty cost used for the slack variables.) In block 511, the LR optimizer checks if convergence has been achieved for the dual problem. If not, in block 515, the Lagrangian multiplier vector A is updated with the calculated correction value, and processing goes back to 503 for another iteration. If convergence of dual problem is achieved, processing proceeds to 513, wherein the algorithm checks if current solution to the dual problem is feasible solution to SCUC problem (e.g. satisfies coupling constraints). If the current solution is infeasible, an infeasibility correction step is performed to modify current solution so that the modified solution satisfies the constraints. An upper bound (tight upper bound) is calculated using the modified solution. Note that the final solution provided by the LR dual solver (after infeasibility correction step or after being confirmed as a feasible solution) is also a valid solution for the SCUC system, and may be referred to as primal feasible solution).
- “(iv) executing an optimisation calculation defined by the model of the power grid and the input data”; (Xiaomingprovides several examples starting with ¶ [0030] 2nd-3rd,6th-8th sentences: the second power grid resource allocation profile is a Lagrangian Relaxed (LR) function of the power grid resource allocation profile. For example, the LR function of the power grid resource allocation profile may be dual optimization problem (relaxed SCUC MIP problem) using relaxation techniques such as Lagrangian relaxation… In some embodiments, the dual optimization problem includes a set of smaller MIP problems resulting from the relaxation of the SCUC problem, which smaller MIP problems can be solved in parallel to reduce computation time. Fig.6 illustrates a flow chart of a method for solving a Lagrangian Relaxation (LR) of the security constrained unit commitment system, in an embodiment. Fig.7 illustrates a block diagram of parallel asynchronous collaborative primal dual solver 600 for solving the security constrained unit commitment system.
Xiaoming ¶ [0037] SCUC model 131 for the security constrained unit commitment system is formulated [or defined] as the following optimization problem…. eq (1) Ai,i x i≥ bi, i=1, 2…N, and Σi=1 N Ac,i xi ≥ bc here N is the number of power grid resources (e.g., number of power plants and loads in the power grid), i is the resource index, xi is the decision vector for resource i, ci is the cost coefficient vector for resource i, Ai,i is the constraint matrix for resource i, and Ac,i is the coupling constraint matrix for resource i. Therefore, in the illustrated embodiment, solving the security constrained unit commitment system is equivalent to finding the decision vectors xi, i=1, 2,…N, that minimize the loss function (or cost function) shown in Equation (1) while satisfying the various constraints, where the decision vector xi is (or includes information for) the resource allocation schedule for, e.g., the i-th power grid resource. Note that in Equation (1), a vector x is used to denote all of the decision vectors xi, i=1, 2,…, N.
Xiaoming ¶ [0038] 3rd sentence: In various embodiments, the security constrained unit commitment system is a large-scale, mixed integer, linear, non-convex optimization problem.
Xiaoming ¶ [0040] 2nd sentence: Each of primal solvers 609 is MIP solver (e.g. commercial available MIP solver) for solving the SCUC system of Equation (1) with the system constraints, and each of the dual solvers 607 is a solver for solving a dual optimization problem (e.g., a relaxed SCUC MIP problem) using relaxation techniques such as Lagrangian relaxation
Xiaoming ¶ [0043] 1st-3rd , 5th sentences: Typically, an MIP solver, through a series of branch-and-bound (B&B) operations and/or a series of branch-and-cut (B&C) operations, searches through the vector space of the decision vectors to find integer feasible solutions with lower and lower upper bounds, thereby gradually approach the optimum solution (e.g., a set of decision vectors xi that correspond to a minimum loss function for the security constrained unit commitment system). The initial condition may also be referred to as an initial condition configuration. The MIP solver computes and updates, in multiple iterations/steps, the values for the decision vectors such that the loss function decreases as time goes by, until the MIP solver reaches a final solution, which is the optimum solution of the security constrained unit commitment system or is close enough to the optimum solution…. When a difference between the UB and the LB is within a per-determined gap target, the SCUC problem is considered to be solved (e.g., the MIP solver is considered to have converged to the optimum solution).
Xiaoming ¶ [0046] 4th sentence: the MIP solver converges toward the final solution (e.g., optimum solution), the upper bound curve 301 decreases, the lower bound curve 311 increases, and the difference between the upper bound curve 301 and the lower bound curve 311 decreases.
Xiaoming ¶ [0047] 1st – 2nd sentences: In some embodiments, at a time instant (e.g., time To), the difference (also referred as gap) between the upper and the lower bound is computed and compared with a pre-determined threshold (e.g., a gap target, or a target gap value). If the computed difference is smaller than the pre-determined threshold, the MIP solver is considered to have converged to the final solution (e.g., optimum solution), and the MIP solver is stopped.
Xiaoming ¶ [0050] 1st-2nd sentences: To reduce convergence time, the present disclosure uses MIP solvers to solve the security constrained unit commitment system in parallel. Each of the plurality of MIP solvers (see, e.g., primal solvers 609 in FIG. 7) is executed with a different solver configuration, such that each MIP solver follows a different convergence path to the final solution (e.g., the optimum solution). Additional algorithmic details at ¶¶ [0055]- [0056], [0061] 9th sentence, [0063] 4th sentence, [0069] 3rd sentence, [0070] 5th sentence, [0071] last sentence, [0072] 3rd sentence, [0073] 3rd sentence, [0074] 3rd sentence, [0078] 2nd sentence) “and”
- “(v) displaying a result of the optimisation calculation”
(Xiaoming ¶ [0046] 3rd-4th sentences: in Fig.4, lower bound curve 311 is below the upper bound curve 301. In addition, as the MIP solver converges toward the final (e.g. optimum) solution, the upper bound curve 301 decreases, the lower bound curve 311 increases, and the difference between the upper bound curve 301 and the lower bound curve 311 decreases. Similarly, at
Xiaoming ¶ [0056] 1st-2nd sentences: Fig.5 illustrates a lower bound curve 415, which illustrates another lower bound of the loss function of the security constrained unit commitment system. The lower bound curve 415 is generated by solving a dual optimization problem of the security constrained unit commitment system, where the dual optimization problem (also referred to as a dual problem) is a relaxed SCUC problem using relaxation techniques such as Lagrangian Relaxation (LR). Similarly, Fig.8, ¶ [0069] 3rd sentence, ¶ [0070] 5th sentence: in the example of Fig.8, the dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant TD1, and the dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at time instant TD2. Also, see mid-¶ [0073])
Claims 2,13 Xiaoming teaches all limitations in claims 1,12 above. Further, Xiaoming teaches
- “calculating one or more interim results when the execution of the optimisation calculation returns, as a result, an indication that the optimisation calculation cannot be completed”.
(Xiaoming teaches several examples as follows:
Xiaoming ¶ [0043] last sentence: The decision vectors xi provided by the MIP solver at a particular time instant (e.g. at time To after a particular iteration) along the convergence path is considered a (temporary or tentative) [or interim] solution at the particular time instant (e.g. To).
Xiaoming ¶ [0047] 5th sentence: Before convergence of the MIP solver is detected or declared, the operation schedule formed using information from the (temporary) decision vectors xi may be referred to as a temporary or intermediate [or interim] resource allocation schedule.
Xiaoming ¶ [0048] 3rd sentence: the values of the upper and lower bound at 2 different, but close [or interim] time instants may be used to determine if MIP solver have converged.
Xiaoming ¶ [0061] 8th-10,12-13th sentences… if current solution does not satisfy all coupling constraints, the upper bound calculated may be loose upper bound (either UB of positive infinity or finite UB depending on magnitude of the slack variables needed to make infeasible coupling constraints feasible, and penalty cost used for slack variables.) In 511, LR optimizer checks if convergence was achieved for dual problem. If not, in 515, Lagrangian multiplier vector A is updated with calculated correction value, and processing goes back to block 503 for another iteration… If current solution is infeasible [or cannot be completed], an infeasibility correction step is performed to modify current solution, such that the modified solution satisfies the constraints. An upper bound (e.g. tight upper bound) is calculated using the modified solution. Note that final solution provided by LR dual solver (after infeasibility correction step) is also a valid solution for SCUC and may be referred to as primal feasible solution. ¶ [0064] the solution found by dual solver 607 provides a near [or intermediary] feasible solution for primal solver 609, used to warm start new instance of primal solver 609 (label MIP start in Fig.7). For example, the solution found by dual solver 607 may be used as initial guess of the solution to SCUC problem to start a new instance of primal solver 609, to achieve faster convergence.
Xiaoming ¶ [0070] 2nd-6th sentences… solution found does not satisfy the constraints of the dual problem. In Fig.8, dual solver 711 performed 3 iterations to find solution at time TD1, where each iteration is illustrated as a ladder shape with 2 vertical lines and a plurality of rungs (e.g., arrows) in between. The rungs (or arrows) of the ladder shape indicates the number of parallel LR sub-problem solvers instantiated. Therefore, in Fig.8, the dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant [or interim] TD1, and dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at time instant [or interim] TD2. Note that the solutions at time instants TD1 and TD2 may not be feasible solutions (e.g., do not satisfy all the constraints of the LR dual problem) but corresponds to very tight [or interim] lower bounds [or interim to] the SCUC system.
Xiaoming ¶ [0073] 4th sentence: As yet another example, after each dual solver 607 finds a (temporary) [or interim] solution after each iteration but before the infeasibility repair, the lower bound provided by the dual solver 607 at this stage may be used to find the BLB, and the BLB is compared with the BUB for detecting convergence
Xiaoming ¶ [0078] 5th-7th sentences: provide tolerance of failure of a particular solution path (e.g., convergence path of a particular solver), due to minimum value of the upper bounds and maximum value of the lower bounds being used in detecting convergence. For example, a failed solution path may have much higher upper bound value than other properly working solution paths, and therefore, would be ignored by the min() function used to find the minimum value of the upper bounds. Further, the near feasible solution of the dual problem found by a dual solver 607 may be used to warm start (e.g., MIP start) a primal solver 609 to reduce convergence time. Xiaoming ¶ [0079] Variations and modifications to the disclosed embodiments are possible and are fully intended to be included within the scope of the present disclosure. For example, in the discussion above, the best upper bound (BUB) is determined by taking the minimum value of the upper bounds. In alternative embodiments, the BUB is determined by taking, e.g., the 2nd [or intermediary] minimum value, or 3rd [or intermediary] minimum value, etc., of the upper bounds. In fact, the BUB may be determined by arbitrarily taking an upper bound value from the plurality of upper bounds. Similarly, in the discussion above, the best lower bound (BLB) is determined by taking the maximum value of the plurality of lower bounds. In alternative embodiments, the BLB is determined by taking, e.g., the 2nd maximum [or interim] value, or 3rd [or interim] maximum value etc., of the plurality of lower bounds. In fact, the BLB may be determined by arbitrarily taking a lower bound value from the plurality of lower bounds. However, these modifications may not have all of the advantages of the embodiments discussed above. For example, the convergence time may not be as fast, or the tolerance of a failed solution path may not be as strong)
Claim 4. Xiaoming teaches all limitations in in claim 1 above. Furthermore, Xiaoming teaches
- “receiving one or more invalidations and/or edits to the constraint(s) received in step (ii), such that step (iv) is performed without the invalidated constraint(s) and/or with the edited constraint(s)” (Xiaoming ¶ [0061] 8th-13th sentences: Note that if the current solution does not satisfy all the coupling constraints, the upper bound calculated may be a loose upper bound (either [upper bound] UB of positive infinity or finite UB depending on the magnitude of the slack variables needed to make the infeasible coupling constraints feasible, and the penalty cost used for the slack variables.) In block 511, the LR optimizer checks if convergence has been achieved for the dual problem. If not, in block 515, the Lagrangian multiplier vector A is updated [or edited] with the calculated correction value, and processing goes back to block 503 for another iteration. If convergence of the dual problem is achieved, processing proceeds to block 513, wherein the algorithm checks if the current solution to the dual problem is a feasible solution to the SCUC problem (e.g., satisfies the coupling constraints). If the current solution is infeasible, an infeasibility correction step is performed to modify [or edit] the current solution, such that the modified solution satisfies the coupling constraints. An upper bound (e.g. tight upper bound) is calculated using the modified solution. Note that the final solution provided by the LR dual solver (e.g., after the infeasibility correction step or after being confirmed as a feasible solution) is also a valid solution for the SCUC system, and may be referred to as a primal feasible solution
Xiaoming ¶ [0064] the solution found by a dual solver 607 provides a near feasible solution for the primal solver 609, and may be used to warm start a new instance of primal solver 609 (see label MIP start in Fig.7). For example, the solution found by a dual solver 607 may be used as an initial guess of the solution to the SCUC problem to start a new instance of primal solver 609, which new instance of primal solver 609 may achieve faster convergence.
Xiaoming ¶ [0070] Fig.8 illustrates 2 dual solvers 711/713 being instantiated to solve the dual problem of the security constrained unit commitment system along different convergence paths. Processing of each dual solver includes finding a solution to the dual problem (e.g., processing blocks between blocks 501 and 511 in Fig.6), and performing an additional step of infeasibility repair (e.g., block 513 in Fig.6) if the solution found does not satisfy the constraints of the dual problem. In Fig.8, the dual solver 711 performed 3 iterations to find a solution at time TD1, where each iteration is illustrated as a ladder shape with 2 vertical lines and a plurality of rungs (arrows) in between. The rungs (arrows) of the ladder shape indicates the number of parallel LR sub-problem solvers instantiated. Thus, in Fig.8, the dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant TD1, and the dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at time instant TD2. Note that the solutions at time instants TD1 and TD2 may not be feasible solutions (e.g. do not satisfy all constraints of the LR dual problem) but corresponds to very tight lower bounds of the SCUC system. After the infeasibility repair (block 513 in Fig.6), a primal feasible solution (e.g. a solution for SCUC system) is achieved by each of the dual solvers 711/713 at time TF1 and TF2, respectively. Additional details at ¶ [0071]- ¶ [0073] for reaching the feasible solution).
Claim 5. Xiaoming teaches all limitations in in claim 1 above. Furthermore, Xiaoming teaches
- “applying a decomposition method to the objective function and constraint function(s), so as to arrive at a plurality of sub-problems representing the objective function, wherein the plurality of sub-problems with the decomposed objective function and constraint function(s) represent the model of the power grid” (Xiaoming ¶ [0056] 2nd-6th sentences: The lower bound curve 415 is generated by solving a dual optimization problem of the security constrained unit commitment system, where dual optimization problem (also referred as dual problem) is relaxed SCUC problem using relaxation techniques such as Lagrangian Relaxation (LR). For example, the dual problem of (e.g., LR of) the security constrained unit commitment system of Eq (1) may be formulated as:
PNG
media_image1.png
66
328
media_image1.png
Greyscale
(2.1)
PNG
media_image2.png
40
278
media_image2.png
Greyscale
(2.2) subject to following constraints: Ai,i xi ≥ bi, i=1, 2,…, N. Note that by rewriting dual problem in (2.1) into (2.2), the dual problem of Equation 2.1 is decomposed into plurality of dual sub-problems:
PNG
media_image3.png
38
148
media_image3.png
Greyscale
subject to the following constraint: Ai,i xi ≥ bi. As discussed below with reference to Fig.6, an iterative algorithm may be used by LR dual optimizer (also referred to as an LR dual solver, or dual solver) to solve the dual problem in Equation (2.2), and the dual sub-problems in Equation (3) may be solved in parallel by a plurality of LR sub-problem optimizers (also referred as LR sub-problem solvers) to reduce the computation time needed to approach the final (e.g., optimum) solution of the dual problem. In other words, each of the LR sub-problem optimizer (an MIP solver in an example embodiment) solves one or more (and different) LR sub-problems.
Xiaoming ¶ [0061] Referring to Fig. 6, at block 501, the Lagrangian multiplier vector A is initialized. In block 503, the objective coefficient of the plurality of dual sub-problems are updated according to Eq (3) and the LR dual sub-problems are solved. A corresponding lower bound of SCUC system is calculated. Note that a plurality of LR sub-problem solvers may be used to solve the plurality of dual sub-problems in parallel. In block 505, a sub-gradient is calculated using the current solution. In block 507, a correction value is calculated for the Lagrangian multiplier vector A using the calculated sub-gradient. In block 509, the algorithm checks if the current solution satisfies the coupling constraints and calculates a corresponding upper bound for the SCUC system using the current solution. Note that if the current solution does not satisfy all coupling constraints, the upper bound calculated may be a loose upper bound (either UB of positive infinity or finite UB depending on magnitude of slack variables needed to make the infeasible coupling constraints feasible, and penalty cost used for the slack variables.) In block 511 the LR optimizer checks if convergence has been achieved for the dual problem. If not, in block 515, the Lagrangian multiplier vector A is updated with the calculated correction value, and processing goes back to block 503 for another iteration. If convergence of the dual problem is achieved, processing proceeds to block 513, wherein the algorithm checks if the current solution to the dual problem is a feasible solution to the SCUC problem (e.g. satisfies the constraints). If the current solution is infeasible, an infeasibility correction step is performed to modify the current solution, such that the modified solution satisfies the coupling constraints. An upper bound (e.g., a tight upper bound) is calculated using the modified solution. Note that the final solution provided by the LR dual solver (e.g., after the infeasibility correction step or after being confirmed as a feasible solution) is also a valid solution for the SCUC system, and may be referred to as a primal feasible solution.
Xiaoming ¶ [0065] Still referring to Fig.7, PACPDS 600 includes an upper bound (UB) server 605 and lower bound (LB) server 603. The UB server 605 and the LB server 603 manage publications and subscriptions to the LB and UB. For example, the UB server 605 collects the upper bounds from the plurality of primal solvers, finds the minimum value UB of the upper bounds, and publishes the minimum value UB of the upper bounds as the “best upper bound (BUB).” Similarly, the LB server 603 collects the lower bounds from, e.g., the plurality of dual solvers 607, finds the maximum value LB of the lower bounds, and publishes the maximum value LB of the lower bounds as the “best lower bound (BLB).” ¶ [0066] The BLB and BUB are sent to a Solution Supervisor 601 of the PACPDS 600. The Solution Supervisor 601 monitors the BLB and BUB, and determines whether convergence of the SCUC solution has been reached. For example, if the difference between the BUB and BLB is smaller than a pre-determined threshold (e.g., the gap target), the Solution Supervisor 601 declares that convergence has been achieved, and stops the primal solvers 609 and the dual solvers 607. The resource allocation schedule of the power grid 100 is then obtained from the solution of the security constrained unit commitment system (e.g., provided by a primal solver 609) that has the lowest upper bound value.
Xiaoming ¶ [0070] 3rd-5th sentences: FIG. 8, the dual solver 711 performed three iterations to find a solution at time TD1, where each iteration is illustrated as a ladder shape with two vertical lines and a plurality of rungs (e.g., arrows) in between. The rungs (or arrows) of the ladder shape indicates the number of parallel LR sub-problem solvers instantiated. Therefore, in the example of FIG. 8, the dual solver 711 has five LR sub-problem optimizers and runs three iterations to converge to a solution at time instant TD1, and the dual solver 713 has five LR sub-problem optimizers and runs five iterations to converge to a solution at time instant TD2).
Claim 6. Xiaoming teaches all limitations in in claim 1 above. Furthermore, Xiaoming teaches
- “wherein step (ii) includes receiving a plurality of constraint functions, and the method further comprises receiving an order in which the constraint functions are to be applied”.
(Xiaoming teaches several examples starting with ¶ [0037] 2nd sentence: solving security constrained unit commitment system is equivalent to finding the decision vectors [ordered as] xi, i=1, 2,…, N, that minimize loss (i.e. cost) function in Eq (1) while satisfying the various constraints.
Xiaoming ¶ [0056] 3rd-4th sentence noting the constraints: Ai,ixi≥bi, in order i=1,2.…N.
As will be discussed with reference to Fig.6, an iterative [repetitive or ordering] algorithm may be used by LR dual optimizer…
Xiaoming ¶ [0040] 4th-8th sentences: PACPDS 600 obtains upper bounds from primal solver instances 609 with different initial condition configurations (MIP solver parameter settings, MIP starts etc). PACPDS 600 obtains lower bounds from dual solver instances 607. In addition, PACPDS 600 obtain lower bounds from primal solver instances 609, e.g., by solving the SCUC system with integer relaxation of SCUC system, done within MIP solver. Further, PACPDS 600 may obtain upper bounds from the dual solver instances 607. In some embodiments, the PACPDS 600 uses the best upper and lower bounds from a plurality of asynchronously running processes to determine if a primal feasible solution (generated by primal solver instance 609 or Lagrangian dual solver instance 607 corresponding to best upper bound has met the solution gap target. Details of the PACPDS 600 are discussed hereinafter with reference to Figs.5-8.
Xiaoming ¶ [0043] 3rd sentence: The MIP solver computes and updates, in multiple iterations/steps [or order], the values for the decision vectors such that the loss function decreases as time goes by, until the MIP solver reaches a final solution, which is the optimum solution of the security constrained unit commitment system or is close enough to the optimum solution.
Xiaoming ¶ [0048] for detecting convergence and for stopping the MIP solver checks the difference between the upper and lower bound at same time instant To…. In other embodiments, the values of upper and lower bound at 2 different, but close (e.g., within a few seconds, or a few minutes) time instants may be used to determine if the MIP solver have converged. For example, the difference between the upper bound T1 and lower bound at T2 may be compared with the pre-determined threshold, and if the difference is smaller than the pre-determined threshold, then a solution to the security constrained unit commitment system provided by the MIP solver at a time instant T between T1 and T2 (e.g. T1≤T≤T2) may be used as final solution to provide the resource allocation schedule. As another example, the difference between the upper bound at time instant T2 and lower bound at time instant T1 may be compared with the pre-determined threshold, and if the difference is smaller than the pre-determined threshold, then a solution to the security constrained unit commitment system provided by the MIP solver at a time instant T2 may be used as the final solution to provide the resource allocation schedule.
Xiaoming ¶ [0053] 2nd-5th sentences: The difference between minimum value UB of the upper bounds (or lowest of upper bounds) and maximum value LB of the lower bounds (or highest of lower bounds) are compared with a pre-determined threshold (e.g. target gap value between upper bound and lower bound). If the difference is smaller than the pre-determined threshold, convergence of the solution to the security constrained unit commitment system is detected, and MIP solvers may be stopped. The solution (decision vectors xi) of the convergence path having the lowest upper bound value is then used as final solution, and the resource allocation schedule of the power grid is obtained (e.g. extracted) from the final solution. On the other hand, if the difference between minimum value UB of upper bounds and maximum value LB of lower bounds are larger than pre-determined threshold, the MIP solvers continues to search for better solutions, until convergence is detected.
Xiaoming ¶ [0069] In Fig.8, 3 primal solvers 701/703/705 (MIP solvers) are instantiated to solve the security constrained unit commitment system in parallel along different convergence paths. The horizontal line corresponding to each instance of the primal solvers 701/703/705 represents the computation time. If left alone, each of primal solvers 701/703/705 will run through its own course until the solution convergences to the optimum solution at time TP1,TP2, and TP3, respectively, as illustrated by the dots labeled as Gap target reaches at the end of each line.
Xiaoming ¶ [0094] wherein if the 1st instant is before the 2nd instant, the 3rd instant is between the 1st and 2nd instant, is a same as the 1st instant, or is a same as the 2nd instant)
Claim 7 Xiaoming teaches all limitations in in claim 1 above. Furthermore, Xiaoming teaches
- “applying a constraint generation method to one or more of the constraint functions, the constraint generation method applying a sub-set of constraints and adding additional constraints sequentially” (Xiaoming ¶ [0028] 1st sentence: generating resource allocation schedule comprises choosing intermediate resource allocation schedule of the convergence path associated with the value of the upper bounds as the resource allocation schedule that is feasible for all constraints in SCUC MIP problem. ¶ [0043] 5th-7th sentences: the path (e.g. vector) space traversed by MIP solver) from the initial condition to final solution is said to be a convergence path [or sequence] of MIP solver (or of SCUC system), and the MIP solver is said to converge to the final solution along this convergence path. Note that different initial conditions (which include any solver parameters, and/or initial guess(es) of the SCUC solution (also referred to as MIP starts) that affect the convergence behavior of the MIP solver) generally result in different convergence paths for MIP solver. The decision vectors xi provided by the MIP solver at a particular time instant (e.g., at time To after a particular iteration) along the convergence path is considered a (temporary or tentative) solution at the particular time instant (e.g., at time To). ¶ [0054] 2nd-3rd sentences: Similar to the discussion above with reference to Fig.4, convergence may be detected using the minimum value UB of the upper bounds and the maximum value LB of the lower bounds generated at two different time instants (e.g.T1, T2), where the min() and max() functions are taken at the 2 different time instants using upper bound values and lower bound values at the corresponding time instants. One of ordinary skill, upon reading discussion at Fig. 4, would readily apply the principle discussed above with reference to Fig.4 for the discussion here with referenced to Fig.5. For example, at
Xiaoming ¶ [0056] 4th-6th sentences: by rewriting dual problem in (2.1) into (2.2), the dual problem of Eq 2.1 is decomposed into dual sub-problems:
PNG
media_image3.png
38
148
media_image3.png
Greyscale
subject to constraints: Ai,i xi ≥bi. As will be discussed below with reference to Fig.6, an iterative [or sequential] algorithm may be used by LR dual optimizer (also referred as LR dual solver, or dual solver) to solve the dual problem in Eq (2.2), and the dual sub-problems [or sub-set] in Equation (3) may be solved in parallel by a plurality of LR sub-problem optimizers (also referred to as LR sub-problem solvers) to reduce the computation time needed to approach the final solution (e.g., the optimum solution) of the dual problem. ¶ [0058] 2nd sentence: In Fig.5, the upper bound curve 405 is not a tight upper bound at the beginning portion of upper bound curve 405, but provides a tighter upper bound as the LR dual solver converges (e.g. after some iterations [interpreted as computation sequences]).
Xiaoming ¶ [0058] 3rd sentence: the upper bound provided by LR dual solver may also be used (e.g, in addition to the upper bounds provided by MIP solvers) in determining the minimum value UB of the upper bounds.
Xiaoming ¶ [0061] 9th-10th sentences: In block 511, LR optimizer checks if convergence was achieved for the dual problem. If not, in block 515, Lagrangian multiplier vector A is updated with the calculated correction value, and processing goes back to block 503 for another iteration.
Xiaoming ¶ [0063] 4th-6th sentences: Each of dual solvers 607 include a plurality of LR sub-problem optimizers to solve in parallel the LR sub-problems (eq. 3). Each of dual solvers 607 provides a different lower bound curve (see, e.g., lower bound curve 415 in Fig.5). In other words, each of dual solvers 607 finds the final solution along a different convergence path [or sequence].
Xiaoming ¶ [0070] 2nd-5th sentences: Processing of each dual solver includes finding a solution to the dual problem (see, e.g., processing blocks between blocks 501 and 511 in Fig.6), and performing an additional step of infeasibility repair (see, e.g., block 513 in Fig.6) if the solution found does not satisfy the constraints of the dual problem. Fig.8, dual solver 711 performed 3 iterations to find a solution at time TD1, where each iteration is illustrated as a ladder shape with 2 vertical lines and a plurality of rungs (e.g. arrows) in between. The rungs (or arrows) of the ladder shape indicates the number of parallel LR sub-problem solvers instantiated. Therefore, in Fig.8, the dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant TD1, and the dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at time instant TD2. ¶ [0071] 1st-4th sentences: As illustrated in Fig.8, the dual solvers 711 provides a lower bound value of the SCUC system to the UB server 605 (see FIG. 7) after each iteration (see the arrows labeled New LB after each iteration) and before the infeasibility repair, which lower bound value is used by the UB server 605 to find the “best lower bound” (BLB) (the maximum value of all the currently reported lower bounds). Similarly, the dual solver 713 also provides a lower bound value after each iteration to the UB server 605. To avoid clutter, Fig.8 only illustrates one submission of the lower bound value from the dual solver 713 to the UB server at time TD2, with the understanding that the lower bound value after each iteration of the dual solver 713 may be sent to the UB server 605 for finding the BLB. The best lower bound BLB is then compared with the upper bounds of all the primal solvers (e.g. 701, 703, and 705) to detect convergence).
Claim 8 Xiaoming teaches all limitations in claim 7 above. Furthermore, Xiaoming teaches
- “receiving a priority for the sub-set of constraints” (Xiaoming ¶ [0040] 4th-8th sentences: PACPDS 600 obtains upper bounds from primal solver instances 609 with different initial condition configurations (e.g. MIP solver parameter settings, MIP starts, etc.). In some embodiments, the PACPDS 600 obtains lower bounds from dual solver instances 607. In addition, the PACPDS 600 may obtain lower bounds from the primal solver instances 609, e.g., by solving the SCUC system with integer relaxation of SCUC system, which is done within MIP solver. Further, the PACPDS 600 may obtain upper bounds from the dual solver instances 607. In some embodiments, the PACPDS 600 uses the best upper and lower bounds from a plurality of asynchronously running processes to determine if a primal feasible solution (generated by primal solver instance 609 or Lagrangian dual solver instance 607 corresponding to the best upper bound) has met the solution gap target. Details of the PACPDS 600 are discussed hereinafter with reference to Figs.5-8.
Xiaoming ¶ [0056] 4th-6th sentences: by rewriting dual problem in (2.1) into (2.2), the dual problem of Eq 2.1 is decomposed into plurality of dual sub-problems:
PNG
media_image3.png
38
148
media_image3.png
Greyscale
subject to constraints: Ai,i xi ≥bi. the plurality of dual sub-problems in Eq (3) by a plurality of LR sub-problem optimizers (referred as LR sub-problem solvers) to reduce computation time to approach the final (optimum) solution of the dual problem. In other words, each of LR sub-problem optimizer (MIP solver) solves different LR sub-problems. ¶ [0061], ¶ [0063] 4th-6th sentences: Each of dual solvers 607 include a plurality of LR sub-problem optimizers to solve in parallel the LR sub-problems (eq. 3). Each of dual solvers 607 provides a different lower bound curve (see, e.g., lower bound curve 415 in Fig.5). In other words, each of dual solvers 607 finds the final solution along a different convergence path. ¶ [0070] 4th-6th sentences: The rungs (or arrows) of the ladder shape indicates number of parallel LR sub-problem solvers instantiated. Therefore, in Fig.8, dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant TD1, and dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at time instant TD2), “and/or a maximum number of constraints to be generated at once”.
Claim 9. Xiaoming teaches all limitations in claim 1 above. Furthermore, Xiaoming teaches
- “wherein step (i) includes receiving definitions of one or more variables” (Xiaoming ¶ [0035] 2nd sentence: PMS 105 formulates [defines] SCUC problem as MIP representation 133 by using SCUC model 131 and applying market and grid data 132 to SCUC model 131), “definitions of one or more constants” (Xiaoming teaches several examples as follows: ¶ [0027] 3rd sentence:
each of the primal problem solver instances is initialized with a solver parameters [or constants].
¶ [0031] In some embodiments, the first instant, the second instant, and the third instant are a same [or constant] instant. ¶ [0048] The example described above for detecting convergence and for stopping the MIP solver checks the difference between the upper bound and the lower bound at a same [or constant] time instant (e.g., time To). ¶ [0054] 1st sentence: The above discussion regarding detecting convergence uses upper bound values and lower bound values at a same [or constant] instant, which is merely a non-limiting example) “and definitions of one or more data sets” (Xiaoming ¶ [0025] 4th sentence: generating power grid resource allocation profile comprises formulating [or defining] the power grid resource allocation profile as Security Constrained Unit Commitment (SCUC) system based on mixed integer programming (MIP))
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
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:
Xiaoming as applied to parent claims 2,13 above, and in view of
Slutsker et al, US 20140278817 A1 hereinafter Slutsker. As per,
Claims 3,14 Xiaoming teaches all the limitations in claims 2,13 above. Further, Xiaoming teaches
- “indicating
(Xiaoming ¶ [0061] 8th-10, 12-13th sentences… if current solution does not satisfy all coupling constraints, the upper bound calculated may be loose upper bound (either UB of positive infinity or finite UB depending on magnitude of the slack variables needed to make the infeasible coupling constraints feasible, and the penalty cost used for the slack variables.) In block 511, LR optimizer checks if convergence has been achieved for the dual problem. If not, in block 515, Lagrangian multiplier vector A is updated with calculated correction value, and processing goes back to 503 for another iteration… If current solution is infeasible [cannot complet], an infeasibility correction step is performed to modify the current solution… An upper bound (tight upper bound) is calculated using the modified solution. Note that the final solution provided by the LR dual solver (e.g. after the infeasibility correction step or after being confirmed as a feasible solution) is also a valid solution for the SCUC system, and may be referred to as a primal feasible solution.
Xiaoming ¶ [0070] 2nd-6th sentences … solution found does not satisfy the constraints of the dual problem. In Fig.8, dual solver 711 performed 3 iterations to find solution at TD1, where each iteration is illustrated as a ladder shape with 2 vertical lines and a plurality of rungs (arrows) in between. The rungs (arrows) of the ladder shape indicates number of parallel LR sub-problem solvers instantiated. Thus in Fig.8, dual solver 711 has 5 LR sub-problem optimizers and runs 3 iterations to converge to a solution at time instant TD1, and dual solver 713 has 5 LR sub-problem optimizers and runs 5 iterations to converge to a solution at TD2. Note that the solutions at time instants TD1 and TD2 may not be feasible solutions (e.g., do not satisfy all constraints of LR dual problem) but corresponds to very tight lower bounds the SCUC system), “and”
- “providing the calculated interim result(s) ” (Xiaoming Fig.8 and ¶ [0070] 6th sentence: Note that the solutions at time instants TD1 and TD2 may not be feasible solutions (e.g., do not satisfy all constraints of LR dual problem) but corresponds to very tight lower bounds [or interim to] the SCUC system. ¶ [0078] 5th-7th sentences: the disclosed embodiments provide tolerance of failure of a particular solution path (e.g. convergence path of a particular solver), due to minimum value of upper bounds and maximum value of lower bounds being used in detecting convergence. For example, a failed solution path may have much higher upper bound value than other solution paths, and thus, would be ignored by min() function used to find the minimum value of the upper bounds. Further, the near feasible solution of the dual problem found by a dual solver 607 may be used to warm start (e.g., MIP start) a primal solver 609 to reduce convergence time)
* However *
Xiaoming might suggest certainly but does not explicitly recite to clearly anticipate the “indicating to a user” and “providing to the user” features as required by explicit recitation of:
- “indicating to a user that the optimisation calculation cannot be completed”
- “providing the calculated interim result(s) to the user” as claimed.
* Nevertheless *
Slutsker in analogous art of managing energy generation teaches or at least suggests:
- “indicating to a user that the optimisation 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 calculated interim result(s) 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 Xiaoming’s method / system to have included the teachings or suggestions of Slutsker in order to have more rigorously improved upon computation accuracy or efficiency of the Xiaoming’s approximation algorithms (i.e. Lagrangian Relaxation) (Slutsker ¶ [0018]-¶ [0021] in view of MPEP 2143 G and/or F) by further 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). The 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 Xiaoming ¶ [0102] in view of 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 Xiaoming 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
Xiaoming as applied to parent claim 1 above, and in view of
Ye et al, US 20240330396 A1 hereinafter Ye. As per,
Claim 10. Xiaoming teaches all the limitations in claim 1 above. Furthermore, Xiaoming teaches
- “ (Xiaoming Fig.2, ¶ [0003],[0025] 1st,3rd sentences:
at block 10, power grid resource allocation profile indicative of operation of power grid constrained by operational information of the power grid is generated by a power management system (PMS) of the power grid. In some embodiments, the operational information comprises information for constraining operation of the power grid and comprises security-related transmission constraint info and cost info. Additional details at ¶ [0037]-¶ [0039] etc.)
Xiaoming does not explicitly recite to clearly anticipate: “reinforcement learning” as in
- “wherein a reinforcement learning system provides one or more of the constraint functions and/or constraint applying methods” as explicitly claimed. However,
Ye in analogous energy management problem of a microgrid teaches or suggests:
- “wherein a reinforcement learning system provides one or more of the constraint functions and/or constraint applying methods” as explicitly claimed.
(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 Xiaoming’s method to have included Ye’s teachings or suggestions 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 Xiaoming ¶ [0102] in view Ye ¶ [0038], ¶ [0048].
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Claim 11 is rejected under 35 U.S.C. 103 as being unpatentable over:
Xiaoming as applied to parent claim 1 above, and in view of
Jezewski; Joni US 20230060139 A1 hereinafter Jezewski. As per,
Claim 11 Xiaoming teaches all the limitations in claim 1 above. Furthermore, Xiaoming teaches
- “receiving a request, before executing the optimisation calculation, to perform a (Xiaoming ¶ [0047] 5th sentence: before convergence of MIP solver is detected or declared, the operation schedule formed using info from temporary decision vectors xi is referred to as temporary or intermediate resource allocation schedule) “the method further including”
- “performing the (Xiaoming ¶ [0035] 2nd sentence noting SCUC [security constrained unit commitment] model 131 is defined by grid data 132 and market data, exemplified at ¶ [0023] 1st -2nd sentences as: cost, predicted demand info, regulatory requirements (emission target). ¶ [0043] 3rd-6th sentences: MIP [mixed integer programming] solver computes and updates, in multiple iterations steps, values for the decision vectors such that the loss function decreases as time goes by, until MIP solver reaches a final [or complete] solution, which is optimum solution of security constrained unit commitment system. For example, the MIP solver find feasible solutions which correspond to upper bounds (UBs) of the SCUC problem, and may find solutions to integer relaxed SCUC problem which correspond to lower bounds (LBs) of the SCUC problem. When a difference between UB and LB is within a per-determined gap target, the SCUC problem is considered solved (e.g. MIP solver is considered to have converged to optimum solution). The path (e.g., vector space traversed by the MIP solver) from the initial condition to the final [or complete] solution is said to be a convergence path of the MIP solver (or of SCUC system), and the MIP solver is said to converge to the final [or complete] solution along this convergence path.
Xiaoming ¶ [0046] 4th sentence: as MIP solver converges toward the final [or complete] solution (optimum solution), the upper bound curve 301 decreases, lower bound curve 311 increases and difference between upper bound curve 301 and lower bound curve 311 decreases.
Xiaoming ¶ [0047] at time instant To, the difference (or gap) between the upper and lower bound is computed and compared with a pre-determined threshold (a gap target, or target gap value). If the computed difference is smaller than the pre-determined threshold, the MIP solver is considered to have converged to the final [or complete] solution (e.g. optimum solution), and the MIP solver is stopped. The solution of the (stopped) MIP solver then provides the solution to the SCUC system. The decision vectors xi of the final solution include information regarding the operation schedule of the power grid resources (e.g. power plants) of the power grid, which information can be extracted from the decision vectors xi to form the resource allocation schedule for the power grid. Before convergence of the MIP solver is detected or declared, the operation schedule formed using information from the (temporary) decision vectors xi may be referred to as a temporary or intermediate resource allocation schedule.
Xiaoming ¶ [0048] The example described above for detecting convergence and for stopping the MIP solver checks the difference between the upper bound and the lower bound at same time instant To. This is simply a non-limiting example. In other embodiments, the values of the upper bound and the lower bound at two different, but close (e.g., within a few seconds, or a few minutes) time instants may be used to determine if the MIP solver have converged. For example, the difference between the upper bound at time instant T1 and the lower bound at time instant T2 may be compared with the pre-determined threshold, and if the difference is smaller than the pre-determined threshold, then a solution to the security constrained unit commitment system provided by the MIP solver at a time instant T between time instants T1 and T2 (e.g., T1≤T≤T2) may be used as final [or complete] solution to provide the resource allocation schedule. As another example, the difference between the upper bound at time instant T2 and the lower bound at time instant T1 may be compared with the pre-determined threshold, and if the difference is smaller than the pre-determined threshold, then a solution to the security constrained unit commitment system provided by the MIP solver at a time instant T2 may be used as the final [or complete] solution to provide the resource allocation schedule.
Xiaoming ¶ [0050] To reduce the convergence time, the present disclosure uses a plurality of MIP solvers to solve the security constrained unit commitment system in parallel. Each of the plurality of MIP solvers (see, e.g., primal solvers 609 in FIG. 7) is executed with a different solver configuration, such that each MIP solver follows a different convergence path to the final solution (e.g., the optimum solution). In other words, each of the MIP solvers solves the same security constrained unit commitment system, but follows a different convergence path, e.g., due to different solver configurations and MIP starts. Here the initial conditions include any suitable parameter settings (time allocation, solution strategy, MIP starts, etc.) that perturb the solution behavior of the solver, such that a different convergence path is obtained for each initial condition. For example, besides setting different initial values for the decision vectors xi, other ways to set different initial conditions may include setting different emphasis strategies for the MIP solvers 134, setting different time allocations (e.g., the longest computation time allowed) for the MIP solvers 134, and/or setting different gap targets).
Xiaoming does not explicitly refers to its calculated temporary or intermediary solution as
- a “trial calculation” as explicitly recited. However
Jezewski however in analogous art of solution automation and interface analysis, such as solution automation workflows and their variables, teaches or at least suggests:
- a “trial calculation” (Jezewski ¶ [0548] solutions can be designed by applying differences to the solutions of this problem where the solution of trial and error is required, differences in solutions that match the differences in problem structures ¶ [0549] example: ¶ [0550] if a particular random function has known error structures making it non-random, those error structures can be used to reduce the sections of the sequence that are considered actually random, thus reducing the number of values that need to be checked with the trial and error (if an error structure in a particular random function is an occasional non-random sequence with identifiable attributes, those sequences can be checked for & their bounds can be checked, invalidating the need to check every value in the error sequence section, reducing the total number of operations) ¶ [0551] so the non-random error structures can be used to reduce the search/solution space of ‘random sequences to apply trial and error to).
It would have been obvious to one skilled in the art, before the effective filling date of the claimed invention, to have modified Xiaoming’s “method” to have included Jezewski’s teachings
to have provided a more rigorous algorithm that would have reduced the number of values need to be checked (Jezewski ¶ [0548]-[0551] 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 Xiaoming ¶ [0102] in view of Jezewski ¶ [0713], ¶ [0723])
Further, the claimed invention could have also been viewed as a mere combination of old elements in a similar analytical field of endeavor. In such combination each element merely would have performed same analytical function as it did separately. Thus, one of ordinary skill in the art would have recognized that, given existing technical ability to combine the elements as evidenced by Xiaoming in view of Jezewski, the to be combine elements would have fitted together like pieces of a puzzle in a logical, complementary and/or technologically feasible manner. Thus, it would have been reasoned that the results of the combination would have been predictable.
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Conclusion
Following prior 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
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
February 26th, 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