Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 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 an abstract idea without significantly more.
Regarding claim 1, the claim recites ".
This judicial exception is not integrated into a practical application because the claim recites the additional element of a processing unit configured to perform the mathematical concepts. The processing unit is recited so generically, it represents no more than mere instructions to apply the judicial exception to a general-purpose computer. Another additional element is a storage unit. The storage unit represents mere memory and is recited at a high level of generality. Thus, the storage unit is insignificant extra-solution activity. Additionally, the claims recite the additional elements of the processing unit "causing execution, on a first arithmetic device of the plurality of arithmetic devices" and "causing execution, on a second arithmetic device of the plurality of arithmetic devices, different from the first arithmetic device", which is incidental to the claim and is therefore insignificant extra-solution activity.
Even when viewed in combination, these additional elements do not integrate the recited judicial exception into a practical application and the claim is directed to the judicial exception.
The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. As explained above, there are three additional elements. The first is the processing unit. As explained before, the processing unit is at best the equivalent of merely adding the words "apply it" to the judicial exception. Mere instructions to apply an exception cannot provide an inventive concept. See MPEP 2106.05(f). The second additional element is the storage unit, which was previously explained as insignificant extra-solution activity. The courts have recognized that storing and retrieving information in memory is considered well-understood, routine and conventional per MPEP 2106.05(d)(II)(iv). Thus, this limitation does not amount to significantly more than the judicial exception. Third is the processing unit causing the arithmetic devices to execute their respective optimization algorithm, previously described as insignificant extra-solution activity. A scheduler dispatching computational tasks for specific processors to perform is well-understood, routine and conventional. See Patterson et al., Computer Organization and Design: The Hardware/Software Interface, Fourth Edition, hereinafter Patterson, Figure A.4.2; Hennessy et al., Computer Architecture - A Quantitative Approach, Fifth Edition, Figures 4.19, 4.20.
Even when considered in combination, these additional elements represent mere instructions to apply an exception and insignificant extra-solution activity, which do not provide an inventive concept. The claim is not eligible.
Regarding claims 2-7, all of the limitations merely further limit the mathematical concept of claim 1. Even when considered in combination, none of these limitations amount to significantly more than the abstract idea. The claims are not eligible.
Regarding claim 8, it is a method claim that recites the same abstract idea as apparatus claim 1 and is not eligible for the same reasons.
Regarding claims 9-15, they are computer-readable media claims that correspond to apparatus claims 1-7, respectively. They are rejected for the same reasons.
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 1-3, 6-11 and 14-15 are rejected under 35 U.S.C. 103 as being unpatentable over Gambella et al., "Multiblock ADMM Heuristics for Mixed-Binary Optimization on Classical and Quantum Computers", hereinafter Gambella, in view of von Neumann, "First Draft of a Report on the EDVAC", further in view of Okuyama et al., "Binary optimization by momentum annealing", hereinafter Okuyama, further in view of the Quantum Computing Stack Exchange question "How to convert QUBO problem to Ising Hamiltonian?", hereinafter Stack Exchange, further in view of Patterson, and further in view of IBM ILOG CPLEX Optimization Studio, CPLEX User’s Manual, hereinafter CPLEX.
Regarding claim 1, Gambella discloses an information processing system for performing search for an optimal solution of a constrained mixed-binary quadratic programming problem (Abstract), the information processing system comprising a classical computer (Section VIII, ¶ 1), wherein a classical computer executes a conversion process of converting the constrained mixed-binary quadratic programming problem to an augmented Lagrange function that includes an objective function of the constrained mixed-binary quadratic programming problem (Algorithm 2), a constraint expression of the constrained mixed-binary quadratic programming problem (Algorithm 2, η-) and a penalty term (Algorithm 2, ϱ) based on the constraint expression, with a first variable vector (Algorithm 2, x) and a second variable vector (Algorithm 2, x̄) as variables; causing execution, on a first arithmetic device of the plurality of arithmetic devices, a first search process of performing search for an optimal solution of the first variable vector that optimizes the augmented Lagrange function in an alternating direction method of multipliers, using a predetermined optimization algorithm of an unconstrained mixed-binary quadratic programming problem (Algorithm 2, First block update); causing execution, on a second arithmetic device of the plurality of arithmetic devices execution of a second search process of performing search for an optimal solution of the second variable vector that optimizes the augmented Lagrange function in the alternating direction method of multipliers, using another algorithm that is different from the predetermined optimization algorithm (Algorithm 2, Second block update); and causing repeated execution of the second search process performed using the optimal solution of the first variable vector determined by the first search process and the first search process performed using the optimal solution of the second variable vector determined by the second search process (Algorithm 2).
Gambella does not disclose the components of a classical computer, a plurality of plurality of arithmetic devices that are communicably connected to each other, the second arithmetic device being different from the first, and the second algorithm being a linear solver algorithm.
Von Neumann discloses a processing unit (2.3) in communication with a storage unit (2.5), , the storage unit storing a program executable by the processing unit for causing the processing unit to perform operations (2.4(b)). It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to have used a von Neumann computer to run the algorithm disclosed by Gambella as Gambella’s argument can be run on a classical von Neumann architecture computer (Gambella, Section VIII, ¶ 1).
The combination of Gambella and von Neumann does not disclose a plurality of plurality of arithmetic devices that are communicably connected to each other, the second arithmetic device being different from the first, and the second algorithm being a linear solver algorithm.
Okuyama discloses a second arithmetic device of the plurality of arithmetic devices, different from the first arithmetic device (Abstract, Gambella CPU; Okuyama GPU).
Okuyama does not disclose a conversion process of converting the unconstrained binary quadratic programming (also known as QUBO) problem to an Ising model.
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to use the momentum annealing model disclosed by Okuyama in the algorithm disclosed by Gambella because Stack Exchange discloses that QUBO problems can be expressed as Ising Hamiltonians (Davit Khachatryan’s answer) that can be solved via annealing, and Okuyama’s GPU annealing algorithm is 247 times faster at finding an approximate solution compared to simulated annealing on a CPU (Section I, ¶ 3).
The combination of Gambella, von Neumann, Okuyama and Stack Exchange does not disclose the arithmetic devices being communicably connected to each other and the second algorithm being a linear solver algorithm.
Patterson discloses a plurality of arithmetic devices that are communicably connected to each other (Figure A.2.2(a)).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system disclosed by Gambella, von Neumann, Okuyama and Stack Exchange to include the PCI-Express (PCIe) interconnection between the CPU and GPU disclosed by Patterson because PCIe is the standard by which GPUs receive instructions from CPUs and GPUs send back data to CPUs.
The combination of Gambella, von Neumann, Okuyama, Stack Exchange and Patterson does not disclose the second algorithm being a linear solver algorithm.
CPLEX discloses a linear solver (p. xiii, ¶ 3).
It would have been obvious for one of ordinary skill in the art before the effective filing date of the claimed invention to modify the system disclosed by Gambella, von Neumann, Okuyama, Stack Exchange and Patterson to include the linear solver disclosed by CPLEX because Gambella explicitly uses CPLEX for solving the non-QUBO (Figure 6; Section VII, ¶ 1).
Regarding claim 2, Gambella discloses that the other algorithm is a continuous optimization algorithm (Algorithm 2, Second block update), and Okuyama discloses wherein the predetermined optimization algorithm is an algorithm including: a quadratic programming problem indicated by an objective function that includes a product of a first state variable vector (Equation 4, w), a predetermined matrix (Equation 5, J) and a second state variable vector (Equation 4, γ); and a state update process of performing stochastic update (Algorithm 1, line 10) of the first state variable vector and the second state variable vector by repeating a process (Algorithm 1) of calculating a first vector by multiplying the predetermined matrix and the first state variable vector (Equation 5), performing stochastic update of the second state variable vector based on a stochastic distribution that includes a parameter based on the first vector (Algorithm 1, line 10), calculating a second vector by multiplying the predetermined matrix and the second state variable vector (Equation 3) and performing stochastic update of the first state variable vector based on a stochastic distribution that includes a parameter based on the second vector (Algorithm 1, line 11).
Regarding claim 3, Gambella discloses the information processing system disclosed in claim 1, wherein the operations further comprise: causing, by the processing unit, the execution of a search for feasible optimal solution candidates of the constrained mixed-binary quadratic programming problem based on the optimal solution of the first variable vector and the optimal solution of the second variable vector, using the local solution search algorithm (Section VII A, Local Search (LS) Operator); and causing execution of additional searching for an optimal solution of the first variable vector and an optimal solution of the second variable vector using the feasible optimal solution candidates, in the first search process and the second search process (Section VII A, Local Search (LS) Operator); while Patterson discloses using a third arithmetic device of the plurality of arithmetic devices (Figure A.4.1, first and third arithmetic devices as SP).
Regarding claim 6, Gambella discloses the information processing system disclosed in claim 3, wherein the operations further comprise: updating, by the processing unit, a Lagrange multiplier (Algorithm 2, λk) of the augmented Lagrange function based on the optimal solution of the first variable vector and the optimal solution of the second variable vector (Algorithm 2, Dual variable update); and causing, by the processing unit, the first search process and the second search process for the augmented Lagrange function to which the updated Lagrange multiplier is applied, to additionally search for an optimal solution of the first variable vector and an optimal solution of the second variable vector (Algorithm 2, while loop).
Regarding claim 7, Gambella discloses the information processing system disclosed in claim 6, wherein the operations further comprise: causing, the processing unit, repeated execution of the first search process and the second search process while updating the Lagrange multiplier and the feasible optimal solution candidates until a predetermined end condition is satisfied (Algorithm 2, line 1).
Regarding claim 8, it is a method claim corresponding to apparatus claim 1 and is rejected for the same reasons.
Regarding claim 9-11 and 14-15, they are computer-readable media claims that implement the device implemented in claims 1-3 and 6-7, respectively. They are rejected for the same reasons.
Claims 4-5 and 12-13 are rejected under 35 U.S.C. 103 as being unpatentable over Gambella, von Neumann, Okuyama, Stack Exchange, Patterson and CPLEX as applied to claim 3 above, and further in view of Alvim et al., “Local Search for the Bin Packing Problem”, hereinafter Alvim.
Regarding claim 4, the combination of Gambella, von Neumann, Okuyama, Stack Exchange, Patterson and CPLEX fails to disclose the specifics of the local search process.
Alvim discloses a search (Figure 3.1) for such feasible optimal solution candidates of the first variable vector (Figure 3.1, i) and feasible optimal solution candidates of the second variable vector (Figure 3.1, j) that a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector is the shortest (Figure 1, line 8), within a range of observing the constraint expression (Figure 3.1, line 10).
It would have been obvious to one of ordinary skill in the art before the effective filing date of the claimed invention because Alvim’s local search is the method used by Gambella (Section VII A 2).
Regarding claim 5, Alvim discloses a search (Figure 3.1) for such feasible optimal solution candidates of the first variable vector (Figure 3.1, i) and feasible optimal solution candidates of the second variable vector (Figure 3.1, j) that a weighted sum of a distance between the optimal solution of the first variable vector and the optimal solution of the second variable vector and the objective function of the constrained mixed-binary quadratic programming problem is minimized (Figure 1, line 8), within a range of observing the constraint expression (Figure 3.1, line 10).
Regarding claims 12 and 13, they are computer-readable media claims that implement the device implemented in claims 4 and 5, respectively. They are rejected for the same reasons.
Response to Arguments
Applicant’s arguments, see p. 14, filed July 30, 2026, with respect to the rejections of claims 1-7 under 35 U.S.C. § have been fully considered and are persuasive. Therefore, the rejection has been withdrawn.
Applicant's arguments, see pp. 14-24, with respect to the rejection of claims 1-15 under 35 U.S.C. have been fully considered but they are not persuasive.
Applicant asserts under the Step 2A, Prong Two analysis that the claims as amended recite an arithmetic device as a particular machine that integrates the judicial exception into a practical application (Remarks, pp. 14-18), pointing to the specification to describe various features of the arithmetic device (Remarks, pp. 19-20).
Examiner respectfully disagrees. The claims do not cite any particular machine as an arithmetic device. Importing limitations from the specification into the claims is improper. See MPEP § 2111.01. Furthermore, the assertion that the claimed arithmetic devices are a particular machine is inconsistent with the specification, which does not define an arithmetic device:
[0092] The arithmetic device 17 is a device that executes a process related to search of an optimal solution of a combinatorial optimization problem. [emphasis added] The processor 17 may be, for example, in a form of an expansion card attached to the information processing apparatus 10, like a GPU (graphical processing unit). The arithmetic device 17 is configured, for example, with hardware such as a CMOS (complementary metal oxide semiconductor) circuit, an FPGA or an ASIC.
[0093] The arithmetic device 17 includes a control device, a storage device, an interface for connecting to the system bus 18 and the like and performs transmission/reception of commands and information to/from the processor 11 via the system bus 18. The arithmetic device 17 may be, for example, communicably connected to other arithmetic devices 17 to operate in cooperation with the other arithmetic devices 17. A function realized by the arithmetic device 17 may be realized, for example, by causing a processor (a CPU, a GPU or the like) to execute a program. [emphasis added]
For those reasons, the claims are directed to an abstract idea and are not integrated in a practical application.
Applicant further asserts that under the Step 2B analysis that the claims recite elements that taken as whole amount to more than the judicial exception (Remarks, pp. 20-21), because the claims portray several additional elements that are not well-understood, routine and conventional.
Examiner respectfully disagrees. Regarding the “arithmetic devices that are communicably connected to each other”, this interconnection is a consequence of the mathematical algorithms used by the claims. The specification supports this assertion. Formula 21 [0072] depends on the results from Formula 20 [0070]: “However, x here [in Formula 21] is x that determined from the first formula of Formulas 19 [rewritten as Formula 20] immediately before” [0071]. The arithmetic devices have to communicate with each other to perform the optimization algorithm. Regarding the processing unit causing execution on arithmetic devices, it is addressed in the 35 U.S.C. § 101 rejection above. Regarding the “using [of a] a linear solver algorithm”, the use of one specific kind of mathematical algorithm is still a mathematical concept.
What is arguably not well-understood, routine and conventional is the method of optimization problem solving itself, the mathematical concept. “However, it is important to keep in mind that an improvement in the abstract idea itself (e.g. a recited fundamental economic concept) is not an improvement in technology” (MPEP § 2106.05(a)(II)).
Applicant’s arguments, see pp. 24-30, with respect to the rejections of claim(s) 1-15 under 35 U.S.C. have been fully considered and are persuasive. Therefore, the rejection has been withdrawn. However, upon further consideration, a new grounds of rejection is made in the 35 U.S.C. § 103 rejection above.
Conclusion
Applicant's amendment necessitated the new ground(s) of rejection presented in this Office action. Accordingly, THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any nonprovisional extension fee (37 CFR 1.17(a)) pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the mailing date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Matthew Strapp whose telephone number is (571)272-9343. The examiner can normally be reached Monday-Friday 8:00 AM-4:00 PM.
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, Andrew Caldwell can be reached at (571)272-3702. 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.
/M.S./
Matthew StrappExaminer, Art Unit 2182
571-272-9343
/ANDREW CALDWELL/Supervisory Patent Examiner, Art Unit 2182
Prosecution Insights