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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 12-13-2023 is in compliance
with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
Claim Rejections - 35 USC § 103
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 (i.e., changing from AIA to pre-AIA ) 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.
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.
Claim(s) 1, 3, 4, 6-10 are rejected under 35 U.S.C. 103 as being unpatentable over Takano et al. (US 2022/0335323 A1) in view of Yamada et al. (“Optimization of Combinatorial Testing by Incremental SAT Solving”)
Regarding claim 1, Takano explicitly teaches:
A simulated annealing device comprising: (Takano, ¶[0008]: “the solution of the combinatorial optimization problem is obtained by simulated annealing using a general computer with the energy function in the Ising model or in QUBO as input .”)
a memory configured to store instructions; and (Takano, ¶[0143]: “The
computer 1000 includes a CPU 1001 , a main memory device 1002 , an auxiliary memory device 1003 , an interface 1004 , and an input device 1005 .”)
a processor configured to execute the instructions to: (Takano, ¶[0143]: “The
computer 1000 includes a CPU 1001 , a main memory device 1002 , an auxiliary memory device 1003 , an interface 1004 , and an input device 1005 .”)
to obtain sets of values of multiple variables of the combinatorial optimization problem that satisfy the one or more constraints, (Takano, ¶[0032]: “wherein the energy function is corresponding to a combinatorial optimization problem to be solved ; and a simulated annealing unit that obtains a state of each spin corresponding to a solution of the combinatorial optimization problem by performing simulated annealing when the energy function is input , wherein , in a process of the simulated annealing , the simulated annealing unit selects a spin , selects a set to which the spin belongs , and changes the states of one or more spins including the spin while a condition where the set satisfies a constraint is maintained , when the set satisfies the predetermined constraint and the state of the spin is determined to be changed .”)
which are candidate solutions to the combinatorial optimization problem. (Takano, ¶[0032]: “the simulated annealing unit selects a spin , selects a set to which the spin belongs , and changes the states of one or more spins including the spin while a condition where the set satisfies a constraint is maintained , when the set satisfies the predetermined constraint and the state of the spin is determined to be changed .”, ¶[0119]: “Next , the SA unit 3 selects one spin as a candidate to flip ( step S2 ) .”)
Takano fails to teach:
solve a SAT (Boolean Satisfiability Testing) expressed in a CNF (Conjunctive Normal Form) form with constraint information indicating one or more constraints imposed on a combinatorial optimization problem converted,
However, Yamada explicitly teaches:
solve a SAT (Boolean Satisfiability Testing) expressed in a CNF (Conjunctive Normal Form) form with constraint information indicating one or more constraints imposed on a combinatorial optimization problem converted, (Yamada, Pg. 2, Col. 1, Section II.A: “Satisfiability (SAT) [5] solvers are tools that decide if a boolean formula over a set X of boolean variables can be true under some assignment α on the boolean variables, i.e., a mapping α : X→{TRUE,FALSE}. An assignment α satisfies a formula φ, written α |= φ, iff φ evaluates to TRUE after replacing every variable x in φ by α(x). Standard SAT solvers accept a boolean formula in conjunctive normal form (CNF). To simplify the discussion, we assume that SAT solvers can accept arbitrary boolean formulas; cf. the well-known transformation by Tseitin”, Pg. 2, Col. 2, ¶[1]: “The constraints 1), 2), and 3) in the introduction are expressed by the following SUT constraint:
PNG
media_image1.png
99
360
media_image1.png
Greyscale
. A test case is a choice of values of parameters that does not violate the given constraint.”)
The combination of Takano and Yamada are analogous art because they are in the same field of training time series data. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, having the teachings of Takano and Yamada before them, to modify the teachings of Takano to include the teachings of Yamada to optimize test suites using incremental SAT solving and improve the speed of test case generation
Regarding claim 3, the combination of Takano and Yamada discloses all the limitations of claim 1 (as shown in the rejections above).
Takano in view of Yamada further discloses:
The simulated annealing device according to claim 1, wherein the processor is further configured to execute the instructions to:
select one candidate variable to be flipped from variables included in a tentative solution to the combinatorial optimization problem being solved by a simulated annealing method; and (Takano, ¶[0119]: “Next , the SA unit 3 selects one spin as a candidate to flip ( step S2 ) . The spin selected in step S2 is hereinafter referred to as the selected spin .”, ¶[0140]: “As described above , the SA unit 3 repeats the process of steps S2 to S15 . Then , for example , in the iterative process , the SA unit 3 moves to step S13 each time , and if the determination result of not accepting the state transition in step S13 is continues for a predetermined number of times in succession , the SA unit 3 may determine that the state of each spin at that time is a state corresponding to a solution of the combinatorial optimization problem . In other words , it may be determined that the state of each spin when the energy is minimized has been obtained . In that case , the output unit 4 outputs the state of each spin . For example , a user of the solution system 1 may refer to the state of each spin and interpret the solution of the combinational optimization problem .”)
solve the SAT after changing a value of the selected candidate variable to obtain candidate solutions to the combinatorial optimization problem. (Takano, ¶[0052]: “The input unit 2 receives input of an energy function in QUBO , which is an energy function corresponding to a combinatorial optimization problem to be solved . This energy function is obtained by converting the expression representing the energy in the combinatorial optimization problem .”, ¶[0076]: “If the selected set does not satisfy the constraint defined for the set , the SA unit 3 determines whether or not to change the state of the selected spin . If it is determined that the state of the selected spin is be changed , the SA unit 3 changes the state of the selected spin .”, ¶[0077]: “The SA unit 3 repeats the operation after the operation of selecting one spin . Then , for example , when the decision not to change the state of a spin occurs for a predetermined number of times in succession , the SA unit 3 determines that the state of each spin at that time is the state corresponding to the solution of the combinatorial optimization problem .”)
Regarding claim 4, the combination of Takano and Yamada discloses all the limitations of claim 1 (as shown in the rejections above).
Takano in view of Yamada further discloses:
The simulated annealing device according to claim 1, wherein the processor is further configured to execute the instructions to:
search for nodes that have not yet been generated in a search tree consisting of one or more nodes that indicate sets of values of multiple variables generated when a tentative solution to the combinatorial optimization problem being solved by a simulated annealing method is obtained by solving the SAT; and (Takano, fig.11:
PNG
media_image2.png
436
315
media_image2.png
Greyscale
, ¶[0027]: “FIG . 11 is a schematic diagram showing the search candidates in the solution method specialized for the traveling salesman problem . As can be seen from FIG . 11 , the number of search candidates in this example is 6 .”, ¶[0141]: “Here , changing the condition of a set from a condition where the set satisfies the constraint to a condition where the set does not satisfy the constraint means searching for search candidates that do not satisfy the constraints in the combinatorial optimization problem , in the first place .”)
obtain the sets indicated by the searched nodes as candidate solutions. (Takano, ¶[0028]: “FIG . 12 is a schematic diagram showing the search candidates in the method of applying the energy function in QUBO to simulated annealing . When there are four cities , the number of spins is 42 = 16 . Each spin takes the value of either 1 or 0. Therefore , the number of search candidates in this example is 216. In the case of the Ising model , each spin takes the value of either 1 or -1 , and the number of search candidates is 216 as in the case of QUBO”)
Regarding claim 6, the combination of Takano and Yamada discloses all the limitations of claim 3 (as shown in the rejections above).
Takano in view of Yamada further discloses:
wherein the processor is further configured to execute the instructions to: determine whether to accept flipping of candidate variables to be flipped that are included in the candidate solutions. (Takano, ¶[0126-0127]: “Next , the SA unit 3 determines whether or not to accept the state transition based on the transition probability calculated in step S7 ( step S8 ) . If the state transition is accepted ( Yes in step S8 ) , the SA unit 3 flips the selected spin ( Step S9 ) .”)
Regarding claim 7, the combination of Takano and Yamada discloses all the limitations of claim 6 (as shown in the rejections above).
Takano in view of Yamada further discloses:
wherein the processor is further configured to execute the instructions to:flip the candidate variables to be flipped that are determined to accept the flipping; and (Takano, ¶[0126-0127]: “Next , the SA unit 3 determines whether or not to accept the state transition based on the transition probability calculated in step S7 ( step S8 ) . If the state transition is accepted ( Yes in step S8 ) , the SA unit 3 flips the selected spin ( Step S9 ) .”)
update the tentative solution to the candidate solution. (Takano, ¶[0134]: “Next to step S10 , the SA unit 3 calculates the energy change when the selected spin and the spin identified in step S10 are flipped ( step S11 ) . As described above , it is possible that no spin other than the selected spin is identified in step S10 . In that case , the SA unit 3 may calculate the energy change when the selected spin is flipped , in step S11”)
Regarding claim 8, the combination of Takano and Yamada discloses all the limitations of claim 1 (as shown in the rejections above).
Takano in view of Yamada further discloses:
wherein the combinatorial optimization problem is a nurse shift scheduling problem. (Takano, ¶[0090]: “the combinatorial optimization problem of creating an optimal work shift table for five days is used as an example . Let the date be represented by the variable d , and let the personnel be represented by the variable m. It is also assumed that there are three personnel , A , B , and C.”) [Examiner’s note: “a nurse” is being interpreted as personnel A, B, or C]
Independent claims 9-10 are rejected under the same rationale with Claim 1, because they are analogous claims.
Claim(s) 2, 5 are rejected under 35 U.S.C. 103 as being unpatentable over Takano et al. (US 2022/0335323 A1) in view of Yamada et al. (“Optimization of Combinatorial Testing by Incremental SAT Solving”) and further in view of Een & Sorensson (“Translating Pseudo-Boolean Constraints into SAT”)
Regarding claim 2, the combination of Takano and Yamada discloses all the limitations of claim 1 (as shown in the rejections above).
Takano in view of Yamada fails to disclose:
wherein the processor is further configured to execute the instructions to: convert the constraint information into the SAT
However, Een explicitly discloses:
wherein the processor is further configured to execute the instructions to: convert the constraint information into the SAT. (Een, Pg. 5, ¶[4]: “Simply stated, arc-consistency means that whenever an assignment could be propagated on the original constraint, the SAT-solver’s unit propagation, operating on our translation of the constraint, should find that assignment too. More formally: Definition. Let x = (x1,x2,...,xn) be a set of constraint variables, t = (t1, t2, . . . , tm) a set of introduced variables. A satisfiability equivalent CNF translation φ(x,t) of a constraint C(x) is said to be arc-consistent under unit propagation iff for every partial assignment σ, performing unit propagation on φ(x,t) will extend the assignment to σ such that every unbound constraint variable xi in σ can be bound to either True or False without the assignment becoming inconsistent with C(x) in either case.”)
The combination of Takano, Yamada and Een are analogous art because they are in the same field of training time series data. Therefore, it would have been obvious to one of ordinary skill in the art before the effective filling date of the claimed invention, having the teachings of Takano, Yamada and Een before them, to modify the teachings of Takano and Yamada to include the teachings of Een to solve pseudo-boolean constraint optimization problems more simply and efficiently.
Regarding claim 5, the combination of Takano and Yamada discloses all the limitations of claim 3 (as shown in the rejections above).
Takano in view of Yamada further discloses:
set the variable whose value has been changed from the initial value among the variables included in the candidate solutions obtained as a candidate variable to be flipped. (Takano, ¶[0133]: “Then , in step S10 , the SA unit 3 may identify auxiliary spins whose values are to be changed according to flip result of the flip of the basic spin .”, ¶[0135-0137]: “Next , the SA unit 3 calculates the transition probability based on the energy change calculated in step S11 and the temperature in simulated annealing ( Step S12 , see FIG .7 ) . Next , the SA unit 3 determines whether or not to accept the state transition based on the transition probability calculated in step S12 ( step S13 ) . If the state transition is accepted ( Yes in step S13 ) , the SA unit 3 flips the selected spin and the spin identified in step S10 ( step S14 ) .”)
Takano in view of Yamada fails to disclose:
wherein the processor is further configured to execute the instructions to: use values of the tentative solution as initial values of the variables; and
However, Een explicitly discloses:
wherein the processor is further configured to execute the instructions to: use values of the tentative solution as initial values of the variables; and (Een , Pg. 4, Section 4: “First run the solver on the set of constraints (without considering the objective function) to get an initial solution f(x0) = k, then add the constraint f(x) < k and run again. If the problem is unsatisfiable, k is the optimum solution. If not, the process is repeated with the new smaller solution.”)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to AMY TRAN whose telephone number is (571)270-0693. The examiner can normally be reached Monday - Friday 7:30 am - 5:00 pm EST.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, David Yi can be reached at (571) 270-7519. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/AMY NMN TRAN/Examiner, Art Unit 2126
/DAVID YI/Supervisory Patent Examiner, Art Unit 2126
Prosecution Insights