Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 112
The following is a quotation of 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-7 rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being incomplete for omitting essential structural cooperative relationships of elements, such omission amounting to a gap between the necessary structural connections. See MPEP § 2172.01. Regarding claim 1, it is unclear how the "storage unit" is claimed with regards to its relationship with the processing unit. It is unclear how the storage unit at claim 1 line 5 cooperates with the processing unit since the storage unit is not discussed in the remainder of the claim after line 5. Only the processing unit’s functions are discussed. No cooperation between the processing unit is set forth in the remainder of the claim. Claims 2-7 are rejected by virtue of their dependency on claim 1.
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 a search for an optimal solution of a constrained mixed-binary quadratic programming problem, which is a mathematical concept.
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.
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 two 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.
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 medium 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-9, 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".
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, paragraph 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; executes 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), and 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 different from the predetermined optimization algorithm (Algorithm 2, Second block update); and repeatedly executes 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 (). Gambella, however, does not disclose the components of a classical computer.
Von Neumann discloses a processing unit (2.3) in cooperation with a memory (2.5). 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, paragraph 1).
Regarding claim 3, Gambella discloses the information processing system disclosed in claim 1, wherein the processing unit searches 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 a local solution search algorithm (Section VII A, Local Search (LS) Operator); and newly searches 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).
Regarding claim 6, Gambella discloses the information processing system disclosed in claim 3, wherein the processing unit updates 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 executes the first search process and the second search process for the augmented Lagrange function to which the updated Lagrange multiplier is applied, to newly 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 processing unit repeatedly executes 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 medium claims that implement the device implemented in claims 1, 3 and 6-7, respectively. They are rejected for the same reasons.
Claims 2 and 10 are rejected under 35 U.S.C. 103 as being unpatentable over Gambella and von Neumann as applied to claim 1 above, and 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.
Regarding claim 2, Gambella discloses that the other algorithm is a continuous optimization algorithm (Algorithm 2, Second block update), but the combination of Gambella and von Neumann does not disclose the specific predetermined optimization algorithm. 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). Okuyama does not disclose a conversion process of converting the unconstrained mixed-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 annealing algorithm is 247 times faster at finding an approximate solution compared to simulated annealing (Section I, paragraph 3).
Regarding claim 10, it is a computer-readable medium claim that implements the device implemented in claim 2 and is rejected for the same reasons.
Claims 4-5 and 12-13 are rejected under 35 U.S.C. 103 as being unpatentable over Gambella and von Neumann 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 and von Neumann 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, paragraph 1).
Regarding claims 12 and 13, they are computer-readable medium claims that implement the device implemented in claims 4 and 5, respectively. They are rejected for the same reasons.
Discussion of Pertinent Prior Art
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure. Osogami et al., "Local Search Algorithms for the Bin Packing Problem and Their Relationships to Various Construction Heuristics", discloses local search in relation to bin packing problems. Ronagh et al. (CA 2,881,033) discloses a transformation of a constrained quadratic mixed-binary problem into a Lagrangian dual, which can then be solved via an annealer. Chang et al., "On Hybrid Quantum and Classical Computing Algorithms for Mixed-Integer Programming", discloses solving mixed-integer problems by transforming the problem into a QUBO. Okuyama et al. (WO2022/044184) discloses a device that translates mixed-binary quadratic programming problems into more easily solvable forms.
Conclusion
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