DETAILED ACTION
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 .
This Action is non-final and is in response to the claims filed November 23, 2022. Claims 1-10 are pending, of which claims 1-10 are currently rejected.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 12/28/2022 and 02/28/2024 are in compliance with the provisions of 37 CFR 1.97. It has been placed in the application file, and the information referred to therein has been considered as to the merits.
Drawings
The drawings are objected to because Figure 8 S102 should be “divide input minimization problem” instead of “divid input minimization problem”.
Corrected drawing sheets in compliance with 37 CFR 1.121(d) are required in reply to the Office action to avoid abandonment of the application. Any amended replacement drawing sheet should include all of the figures appearing on the immediate prior version of the sheet, even if only one figure is being amended. The figure or figure number of an amended drawing should not be labeled as “amended”. If a drawing figure is to be canceled, the appropriate figure must be removed from the replacement sheet, and where necessary, the remaining figures must be renumbered and appropriate changes made to the brief description of the several views of the drawings for consistency. Additional replacement sheets may be necessary to show the renumbering of the remaining figures. Each drawing sheet submitted after the filing date of an application must be labeled in the top margin as either “Replacement Sheet” or “New Sheet” pursuant to 37 CFR 1.121(d). If the changes are not accepted by the examiner, the applicant will be notified and informed of any required corrective action in the next Office action. The objection to the drawings will not be held in abeyance.
In addition to Replacement Sheets containing the corrected drawing figure(s), applicant is required to submit a marked-up copy of each Replacement Sheet including annotations indicating the changes made to the previous version. The marked-up copy must be clearly labeled as “Annotated Sheets” and must be presented in the amendment or remarks section that explains the change(s) to the drawings. See 37 CFR 1.121(d)(1). Failure to timely submit the proposed drawing and marked-up copy will result in the abandonment of the application.
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 2-4 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 applications subject to pre-AIA 35 U.S.C. 112, the applicant), regards as the invention.
Claim 2 recites the limitation “a relaxation problem” on line 4. It is unclear if this mention of “a relaxation problem” is the same relaxation problem as recited on line 6 of claim 1 or some other relaxation problem. For examination purposes, the relaxation problem of claim 2 will be construed to be the relaxation problem of claim 1. Appropriate correction is required.
Because claims 3-4 depend upon claim 2, claims 3-4 are additionally rejected under 35 U.S.C. 112(b) or 35 U.S.C. 112 (pre-AIA ), second paragraph, as being indefinite.
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-10 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Regarding claim 1, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Claim language recites solving of a combinatorial optimization problem and a relaxation problem while making use of an upper and lower bound. Below are the limitations of claim 1 that recite an abstract idea under mathematical concepts or mental steps:
solve a combinatorial optimization problem by an annealing method; (mathematical concepts)
solve a relaxation problem, which is a problem generated by relaxing constraints imposed on the combinatorial optimization problem; (mathematical concepts)
calculate, if the combinatorial optimization problem is a minimization problem, a lower bound of a minimization target in the minimization problem by solving the relaxation problem generated from the combinatorial optimization problem; and (mathematical concepts)
calculate, if the combinatorial optimization problem is a maximization problem, an upper bound of a maximization target in the maximization problem by solving the relaxation problem generated from the combinatorial optimization problem. (mathematical concepts)
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, these are the additional elements recited in claim 1:
A solution accuracy guaranteeing annealing calculation device
A memory configured to store instructions; and
A processor configured to execute the instructions
The processor and memory are generic computer components and do not integrate the judicial exception into a practical application of the exception. See MPEP 2106.05(f). All additional elements represent no more than mere instructions to apply the judicial exception on a computer. 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.
There are insignificant extra-solution activities that must be made of note:
A memory configured to store instructions (insignificant extra-solution activity)
At Step 2B, there are no additional elements claimed that amount to significantly more than the recited judicial exception. These additional elements are 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.
In regards to the insignificant extra-solution activity found in this limitation “configured to store instructions”, this action describes mere data gathering that is recited at a high level of generality. Per MPEP 2106.05(d)(II), the courts have recognized the following computer functions as well‐understood, routine, and conventional functions when they are claimed in a merely generic manner (e.g., at a high level of generality) or as insignificant extra-solution activity: iv. Storing and retrieving information in memory, Versata Dev. Group, Inc. v. SAP Am., Inc., 793 F.3d 1306, 1334, 115 USPQ2d 1681, 1701 (Fed. Cir. 2015); OIP Techs., 788 F.3d at 1363, 115 USPQ2d at 1092-93. This limitation therefore remains well, understood, routine and conventional even upon reconsideration. Thus, this limitation does not amount to significantly more.
Even when considered in combination, these additional elements represent mere instructions to apply an exception, which do not provide an inventive concept. The claim is not eligible.
Regarding claim 2, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 2 that recite an abstract idea under mathematical concepts or mental steps:
generate a relaxation problem from the combinatorial optimization problem. (mathematical concepts).
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, there are no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 3, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 3 that recite an abstract idea under mathematical concepts or mental steps:
By solving the combinatorial optimization problem, and the calculated lower bound or the calculated upper bound. (mathematical concepts)
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, these are the additional elements recited in claim 1:
Output a solution to the calculated combinatorial optimization problem (insignificant extra-solution activity)
All additional elements represent no more than mere instructions to apply the judicial exception on a computer. 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.
There are insignificant extra-solution activities that must be made of note:
Output a solution to the calculated combinatorial optimization problem (insignificant extra-solution activity)
At Step 2B, there are no additional elements claimed that amount to significantly more than the recited judicial exception. These additional elements are 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.
In regards to the insignificant extra-solution activity found in this limitation “output a solution to the calculated combinatorial optimization problem”, this action describes data outputting that is recited at a high level of generality. As is known in the art, outputting of data is a basic function of underlying hardware in any computer (Patterson, David A., and John L. Hennessy. Computer Organization and Design: The Hardware/Software Interface, edited by Peter J Ashenden, Elsevier Science & Technology, 2007, hereinafter “Patterson”: Pg. 15 Section 1.3 Lines 2-4). This limitation therefore is well understood, routine and conventional activity even upon reconsideration. Thus, this limitation does not amount to significantly more.
Even when considered in combination, these additional elements represent mere instructions to apply an exception, which do not provide an inventive concept. The claim is not eligible.
Regarding claim 4, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 4 that recite an abstract idea under mathematical concepts or mental steps:
Which is the calculated minimization problem (mathematical concepts)
Is substituted, or a value of the maximization target to which the solution to the combinatorial optimization problem, (mathematical concepts)
Which is the calculated maximization problem is substituted. (mathematical concepts)
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, these are the additional elements recited in claim 1:
Output a value of the minimization target to which the solution to the calculated combinatorial optimization problem (insignificant extra-solution activity)
All additional elements represent no more than mere instructions to apply the judicial exception on a computer. 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.
There are insignificant extra-solution activities that must be made of note:
Output a value of the minimization target to which the solution to the calculated combinatorial optimization problem (insignificant extra-solution activity)
At Step 2B, there are no additional elements claimed that amount to significantly more than the recited judicial exception. These additional elements are 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.
In regards to the insignificant extra-solution activity found in this limitation “output a value of the minimization target to which the solution to the calculated combinatorial optimization problem”, this action describes data outputting that is recited at a high level of generality. As is known in the art, outputting of data is a basic function of underlying hardware in any computer (Patterson: Pg. 15 Section 1.3 Lines 2-4). This limitation therefore is a well understood, routine, and conventional activity even upon reconsideration. Thus, this limitation does not amount to significantly more.
Even when considered in combination, these additional elements represent mere instructions to apply an exception, which do not provide an inventive concept. The claim is not eligible.
Regarding claim 5, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 2 that recite an abstract idea under mathematical concepts or mental steps:
the combinatorial optimization problem is a problem described in Ising model form. (mathematical concepts).
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, there are no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 6, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 6 that recite an abstract idea under mathematical concepts or mental steps:
the combinatorial optimization problem is a problem described in QUBO (Quadratic Unconstrained Binary Optimization). (mathematical concepts).
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, there are no additional elements beyond those recited in claim 1.
The claim is not eligible.
Regarding claim 7, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 7 that recite an abstract idea under mathematical concepts or mental steps:
the annealing method is a simulated annealing method (mathematical concepts).
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, there are no additional elements beyond those recited in claim 5.
The claim is not eligible.
Regarding claim 8, at Step 1, the claim is directed to a statutory category of invention (machine).
At Step 2A, Prong 1, Examiner notes that the claim recites an abstract idea. Below are the limitations of claim 8 that recite an abstract idea under mathematical concepts or mental steps:
The combinatorial optimization problem is a problem described in transverse magnetic field Ising model form, and (mathematical concepts)
The annealing method is a quantum annealing method (mathematical concepts).
All limitations as indicated describe “mathematical concepts” or “mental steps”.
At Step 2A Prong 2, there are no additional elements beyond those recited in claim 1.
The claim is not eligible.
Claim 9 recites the method practiced by the apparatus of claim 1 and is therefore rejected for the same reasons therein.
Claim 10 recites the non-transitory computer readable medium having stored thereon the instructions of the method practiced by the apparatus of claim 1 and is therefore rejected for the same reasons therein.
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-4, and 9 are rejected under 35 U.S.C. 103 as being unpatentable over D. Abramson et al. ("A simulated annealing code for general integer linear programs" 1999) (hereinafter “Abramson”), further in view of S. Boyd et al. (“Branch and Bound Methods”, 2018) (hereinafter “Boyd”).
Regarding claim 1, Abramson teaches:
A solution accuracy guaranteeing annealing calculation device (Abramson: code run on IBM RS6000 Model 590 Pg. 17 last line) comprising:
solve a combinatorial optimization problem by an annealing method (Abramson: Abstract combinatorial optimization problem needed to be solved by simulated annealing method; Pg. 4 first and second paragraph after bullet points GPSIMAN used for solving a wide range of combinatorial optimization problems);
a relaxation problem, which is a problem generated by relaxing constraints imposed on the combinatorial optimization problem (Pg. 4 first paragraph, relaxations imposed on constraints of relaxation problem, yielded from combinatorial problem; also discussed in Pg. 12 first paragraph);
calculate, if the combinatorial optimization problem is a minimization problem, by solving the relaxation problem generated from the combinatorial optimization problem (Abramson: detection of maximization or minimization problem for relaxation problem subject to relaxed constraints (Pg. 5 Section 2.1), Pg. 6 first paragraph GPSIMAN used for same purposes as branch and bound solver, also discussed in Pg. 20 Conclusion first paragraph); and
calculate, if the combinatorial optimization problem is a maximization problem, by solving the relaxation problem generated from the combinatorial optimization problem (Abramson: detection of maximization or minimization problem for relaxation problem subject to relaxed constraints (Pg. 5 Section 2.1), Pg. 6 first paragraph GPSIMAN used for same purposes as branch and bound solver, also discussed in Pg. 20 Conclusion first paragraph).
While Abramson does not explicitly teach a memory for storing instructions and a processor, Abramson does teach the code for the simulated annealing being disclosed being run on an IBM RS6000 Model 590 (Abramson: Pg. 17 last line), and the code would need to run on a processor having a memory storing instructions.
It would be obvious for Abramson to have a memory storing code to be run by a processor as all code requires such components in order to be run, as would be known by a person of ordinary skill in the art.
While Abramson does teach the branch and bound method (Pg. 6 first paragraph; Pg. 20 Conclusion first paragraph), Abramson does not explicitly teach calculating a lower bound for minimization problems, or an upper bound for maximization problems in order to determine an optimal solution.
However, Boyd teaches calculating a lower bound for minimization problems, or an upper bound for maximization problems in order to determine an optimal solution (Boyd: Pg. 9 Section 3 minimizing requires finding lower bounds, maximizing requires finding upper bounds for optimal solutions).
It would be obvious before the effective filing date of the claimed invention to combine the upper and lower bound calculation as taught by Boyd with the solution accuracy guaranteeing annealing calculation device as taught by Abramson as both references are directed towards annealing methods for combinatorial optimization problems. One with ordinary skill in the art would be motivated to combine the teachings because it would be obvious to substitute a known method.
Therefore, Abramson in view of Boyd teaches:
A solution accuracy guaranteeing annealing calculation device comprising:
a memory configured to store instructions; and
a processor configured to execute the instructions to:
solve a combinatorial optimization problem by an annealing method;
solve a relaxation problem, which is a problem generated by relaxing constraints imposed on the combinatorial optimization problem;
calculate, if the combinatorial optimization problem is a minimization problem, a lower bound of a minimization target in the minimization problem by solving the relaxation problem generated from the combinatorial optimization problem; and
calculate, if the combinatorial optimization problem is a maximization problem, an upper bound of a maximization target in the maximization problem by solving the relaxation problem generated from the combinatorial optimization problem.
Regarding claim 2, Abramson in view of Boyd teaches:
The solution accuracy guaranteeing annealing calculation device according to claim 1, wherein the processor is further configured to execute the instructions to:
generate a relaxation problem from the combinatorial optimization problem (Abramson: Pg. 4 first paragraph, relaxations imposed on constraints of relaxation problem, yielded from combinatorial problem; also discussed in Pg. 12 first paragraph).
Regarding claim 3, while Abramson teaches outputting a solution to the calculated combinatorial optimization problem by solving the combinatorial optimization problem (Abramson: detection of maximization or minimization problem for relaxation problem subject to relaxed constraints (Pg. 5 Section 2.1), Pg. 6 first paragraph GPSIMAN used for same purposes as branch and bound solvers, and both look for upper or lower bounds depending on if it’s a maximization or minimization problem, also discussed in Pg. 20 Conclusion first paragraph), Abramson does not explicitly teach outputting the calculated lower bound or the calculated upper bound.
However, Boyd teaches minimizing that requires finding lower bounds, and maximizing that requires finding upper bounds which would need to be outputted for the finding of optimal solutions (Boyd: Pg. 9 Section 3).
The motivation to combine with respect to claim 1 applies equally to claim 3.
Regarding claim 4, Abramson in view of Boyd further teaches:
The solution accuracy guaranteeing annealing calculation device according to claim 3, wherein the processor is further configured to execute the instructions to:
output a value of the minimization target to which the solution to the combinatorial optimization problem, which is the calculated minimization problem, is substituted, or a value of the maximization target to which the solution to the combinatorial optimization problem, which is the calculated maximization problem is substituted (Abramson: Pg. 14 Section 3.2 solving using simulated annealing entails solving for bounds for min or max problems, and later finding a set of values for outputting so that the value is substituted in the target i.e., objective function and determined to not violate constraints or bounds).
Claim 9 recites the method practiced by the apparatus of claim 1 and is therefore rejected for the same reasons therein.
Claims 5-8 are rejected under 35 U.S.C. 103 as being unpatentable over Abramson, in view of Boyd, further in view Tomita (US 2020/0380065 A1) (hereinafter “Tomita”).
Regarding claim 5, while Abramson in view of Boyd teaches the solution accuracy guaranteeing annealing calculation device according to claim 1, Abramson in view of Boyd does not explicitly teach the combinatorial optimization problem being described in Ising model form.
However, Tomita teaches quantum annealing method used for combinatorial problem converted into Ising model form (Tomita: ¶ 0004).
It would be obvious before the effective filing date of the claimed invention to combine the Ising model representation as taught by Tomita, with the solution accuracy guaranteeing annealing calculation device as taught by Abramson in view of Boyd because all teachings are directed towards annealing methods for solving combinatorial optimization problems. One with ordinary skill in the art would be motivated to combine the teachings because combinatorial optimization problems are commonly used to solve Ising models (Tomita: ¶ 0004).
Regarding claim 6, while Abramson in view of Boyd teaches the solution accuracy guaranteeing annealing calculation device according to claim 1, Abramson in view of Boyd does not explicitly teach the combinatorial optimization problem being described in QUBO form.
However, Tomita teaches the combinatorial optimization problem being described in QUBO form (Tomita: ¶ 0031).
It would be obvious before the effective filing date of the claimed invention to combine the QUBO representation as taught by Tomita, with the solution accuracy guaranteeing annealing calculation device as taught by Abramson in view of Boyd because all teachings are directed towards annealing methods for solving combinatorial optimization problems. One with ordinary skill in the art would be motivated to combine the teachings because combinatorial optimization problems are commonly used to solve Ising models, which are commonly represented in QUBO form (Tomita: ¶ 0004, ¶ 0031).
Regarding claim 7, Abramson in view of Boyd in view of Tomita teaches:
The solution accuracy guaranteeing annealing calculation device according to claim 5, wherein the annealing method is a simulated annealing method (Abramson: Abstract).
Regarding claim 8, while Abramson in view of Boyd teaches the solution accuracy guaranteeing annealing calculation device according to claim 1, Abramson in view of Boyd does not explicitly teach the combinatorial optimization problem being described in a transverse magnetic field Ising model form the method being a quantum annealing method.
However, Tomita teaches that the combinatorial optimization problem is a quantum annealing method used for combinatorial problem converted into Ising model form (Tomita: ¶ 0004).
The motivation to combine with respect to claim 5 applies equally to claim 8.
Claim 10 is rejected under 35 U.S.C. 103 as being unpatentable over Abramson, in view of Boyd, further in view of IBM (“IBM RM/6000 User Manual”, 2001) (hereinafter “IBM”).
While claim 10 recites instructions for performing the method practiced by the apparatus of claim 1 (claim lines 4-15) which is taught by Abramson in view of Boyd as discussed with respect to claim 1, claim 10 also recites these instructions being stored on a non-transitory computer-readable recording medium, which is not explicitly taught by Abramson in view of Boyd.
However, as evidenced by IBM, the IBM RS6000 Model 590 (the device that is used to run the method as taught by Abramson Pg. 17 last line) has a CD-ROM drive, through which CD-ROMs i.e., a non-transitory computer readable recording medium can be provided in order for instructions that are stored thereon to be run by the processor Pg. 14 Section “Using the CD-ROM Drive”.
It would be obvious to one of ordinary skill in the art before the effective filing date of the claimed invention to provide a non-transitory computer storage recording medium to the device as taught by Abramson in view of Boyd, having stored thereon instructions to perform the method practiced by the apparatus of claim 1 because Abramson in view of Boyd teaches the use of this architecture and doing so would be merely using known components of the architecture for their intended purpose as set forth in Abramson in view of Boyd.
Prior Art Made of Record
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
D. Connolly ("General Purpose Simulated Annealing", 1992) teaches an algorithm for general purpose simulated annealing for integer linear programs, using technologies such as SCICONIC and GPSIMAN.
B. Gendron ("Revisiting Lagrangian relaxation for network design", 2018) teaches different relaxation techniques for constraints of mixed-integer linear programs.
Parizy et al. (US 2021/0256179 A1) teaches an information processing system for calculating an optimal solution of an energy function, executing repeated searches based on previous solutions found.
Irie et al. (US 2021/0232657 A1) teaches an information processing system for solving combinatorial optimization problems having two optimization systems that work in collaboration as well as an extraction system.
Harrigan et al. (11574030) teaches solving of an optimization problem on a hybrid computing system using a branch and bound method whilst executing a quantum approximate optimization algorithm (QAOA).
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to MARIA DE JESUS RIVERA whose telephone number is (571)272-2793. The examiner can normally be reached Monday-Friday 7:30AM-5PM.
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, James Trujillo can be reached at (571) 272-3677. 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.D.R./Examiner, Art Unit 2151 /EMILY E LAROCQUE/ Primary Examiner, Art Unit 2182
Prosecution Insights