DETAILED ACTION
Claims 1-14 are presented for examination.
This Office Action is in response to submission of documents on December 26, 2023.
Rejection of claims 1-14 under 35 U.S.C. 101 for being directed to unpatentable subject matter.
Rejection of claims 1-14 under 35 U.S.C. 102(a)(1) as being anticipated by Tanahashi.
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 .
Priority
Applicant’s claim for the benefit of a prior-filed application under 35 U.S.C. 119(e) or under 35 U.S.C. 120, 121, 365(c), or 386(c) is acknowledged.
Receipt is acknowledged of certified copies of papers required by 37 CFR 1.55.
Information Disclosure Statement
The information disclosure statements (IDS) submitted on 12/6/2022 and 12/26/2023 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statements are being considered by the examiner.
Specification
The title of the invention is not descriptive. A new title is required that is clearly indicative of the invention to which the claims are directed.
The following title is suggested: “Method and Computer Readable Medium for Solving an Optimization Problem.” See e.g., Specification at [0005].
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.
Claim 14 is 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 14 recites the limitation "the computer." There is insufficient antecedent basis for this limitation in the claim.
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-14 are rejected under 35 U.S.C. 101 because the claimed invention is directed to judicial exceptions without significantly more. The claims recite mathematical calculations and mental processes. This judicial exception is not integrated into a practical application because the additional elements that are recited in the claims are extra-solution activities that do not integrate the judicial exceptions into a practical application. The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception because courts have found that the steps of acquiring and storing information are not significantly more than a judicial exception.
Claim 1
Step 1: The claim is directed to a process, falling under one of the four statutory categories of invention.
Step 2A, Prong 1: The claim 1 limitations include (bolded for abstract idea identification):
Claim 1
Mapping Under Step 2A Prong 1
A method for converting a mathematical optimization problem into an object program for a mathematical programming problem, the method comprising causing a processor to:
acquire information on a mathematical expression representing a mathematical model corresponding to the mathematical optimization problem;
deblock the mathematical expression into components and
store information on each component in an object, the components constituting the mathematical expression; and
for the components of the mathematical expression, associate objects with each other through a connecting node as a data structure that is a tree structure in which an object corresponding to the mathematical model is taken as a root node and an object pertaining to each component from the deblocked mathematical expression is taken as a leaf node.
Abstract Idea: Mental Process
Converting a mathematical problem into a program is a mental process that can be carried out by a human using a programming environment to code a program that encapsulates the problem. See MPEP § 2106.04(a)(2), Subsection III.
Abstract Idea: Mental Process
Separating (i.e., “deblocking” an equation into component parts is a mental process that can include splitting the equation into smaller segments to that be evaluated separately and combined into a result. See MPEP § 2106.04(a)(2), Subsection III.
Abstract Idea: Mental Process
Associating objects in a tree structure can include using knowledge of, for example, object oriented programming and known data structures, to construct a tree structure comprised of objects. See MPEP § 2106.04(a)(2), Subsection III.
Step 2A, Prong 2: The claim 1 limitations recite (bolded for additional element identification):
Claim 1
Mapping Under Step 2A Prong 2
A method for converting a mathematical optimization problem into an object program for a mathematical programming problem, the method comprising causing a processor to:
acquire information on a mathematical expression representing a mathematical model corresponding to the mathematical optimization problem;
deblock the mathematical expression into components and
store information on each component in an object, the components constituting the mathematical expression; and
for the components of the mathematical expression, associate objects with each other through a connecting node as a data structure that is a tree structure in which an object corresponding to the mathematical model is taken as a root node and an object pertaining to each component from the deblocked mathematical expression is taken as a leaf node.
The limitation is directed to the extra-solution activity of data gathering. The limitation does not impose meaningful limits on the claim and thus is minimally or tangentially related to the invention. See MPEP 2106.05(g).
Providing data (i.e., sending data to be stored) is an extra-solution activity that does not integrate the judicial exception into a practical application. The limitation does not recite, with specificity, how the data is provided and therefore does not improve the functioning of a computer. See MPEP 2106.05(d)(II).
Step 2B: Regarding Step 2B, the inquiry is whether any of the additional elements (i.e., the elements that are not the judicial exception) amount to significantly more than the recited judicial exception.
Courts have found that the extra-solution activity of data gathering is insignificantly more than the recited judicial exception. See, e.g., In re Grams, 888 F.2d 835, 839-40; 12 USPQ2d 1824, 1827-28 (Fed. Cir. 1989); In re Meyers, 688 F.2d 789, 794; 215 USPQ 193, 196-97 (CCPA 1982); OIP Technologies, 788 F.3d at 1363, 115 USPQ2d at 1092-93; CyberSource v. Retail Decisions, Inc., 654 F.3d 1366, 1375, 99 USPQ2d 1690, 1694 (Fed. Cir. 2011).
Transmitting data is an extra-solution activity that courts have found does not amount to significantly more than the recited judicial exception. See Intellectual Ventures I v. Symantec, 838 F.3d at 1321, 120 USPQ2d at 1362 (utilizing an intermediary computer to forward information); TLI Communications LLC v. AV Auto. LLC, 823 F.3d 607, 610, 118 USPQ2d 1744, 1745 (Fed. Cir. 2016) (using a telephone for image transmission); OIP Techs., Inc., v. Amazon.com, Inc., 788 F.3d 1359, 1363, 115 USPQ2d 1090, 1093 (Fed. Cir. 2015) (sending messages over a network); buySAFE, Inc. v. Google, Inc., 765 F.3d 1350, 1355, 112 USPQ2d 1093, 1096 (Fed. Cir. 2014) (computer receives and sends information over a network).
Courts have found that the extra-solution activity of data gathering is insignificantly more than the recited judicial exception. See, e.g., In re Grams, 888 F.2d 835, 839-40; 12 USPQ2d 1824, 1827-28 (Fed. Cir. 1989); In re Meyers, 688 F.2d 789, 794; 215 USPQ 193, 196-97 (CCPA 1982); OIP Technologies, 788 F.3d at 1363, 115 USPQ2d at 1092-93; CyberSource v. Retail Decisions, Inc., 654 F.3d 1366, 1375, 99 USPQ2d 1690, 1694 (Fed. Cir. 2011).
Accordingly, claim 1 is rejected for being directed to unpatentable subject matter.
Claim 2
Claim 2 recites wherein the object of the leaf node constituting the tree structure includes meta information about the component. The claim adds limitations to the type of data that is stored in an object. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 2 is rejected for being directed to unpatentable subject matter.
Claim 3
Claim 3 recites wherein the meta information is associated with a component of the mathematical expression that is stored in at least one object sharing the connecting node. The claim adds limitations to the type of data that is stored in an object. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 3 is rejected for being directed to unpatentable subject matter.
Claim 4
Claim 4 recites wherein an object of a leaf node that is subordinate to the connecting node includes a component constituting a term pertaining to a constraint condition in the mathematical expression, and the meta information includes information about the constraint condition. The claim adds limitations to the type of data that is stored in an object. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 4 is rejected for being directed to unpatentable subject matter.
Claim 5
Claim 5 recites wherein the constraint condition includes at least either of a condition pertaining to an equality constraint and a condition pertaining to an inequality constraint. The claim adds limitations to the type of conditions that are included with an object. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 5 is rejected for being directed to unpatentable subject matter.
Claim 6
Claim 6 recites wherein a component of the mathematical expression includes at least either of an operator and a literal expression, and the meta information includes information about subscripts appended to at least either of the operator and the literal expression, respectively. The claim adds limitations to a mathematical expression that has previously been identified as a judicial exception. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 6 is rejected for being directed to unpatentable subject matter.
Claim 7
Claim 7 recites wherein a component of the mathematical expression includes a literal expression that defines data representing an indicator of an optimization target in the mathematical optimization problem, and a set of the data on the indicator that is defined by the literal expression is provided in a data structure that is different from the tree structure in which information on the literal expression is stored in a leaf. The claim adds limitations to a mathematical expression that has previously been identified as a judicial exception. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 7 is rejected for being directed to unpatentable subject matter.
Claim 8
Claim 8 recites wherein the mathematical programming problem includes a binary optimization problem. The claim only specifies the type of problem that is acquired. Acquiring a mathematical problem has previously been identified as an additional element of data gathering and therefore the claim does not add any other additional elements that would integrate the other recited judicial exceptions into a practical application. According, claim 8 is rejected for being directed to unpatentable subject matter.
Claim 9
Claim 9 recites wherein the binary optimization problem includes at least any one of a QUBO (unconstrained quadratic binary optimization problem), a PUBO (polynomial unconstrained binary optimization problem), a HUBO (high-order unconstrained binary optimization problem), and a constrained binary optimization problem. The claim only specifies the type of problem that is acquired. Acquiring a mathematical problem has previously been identified as an additional element of data gathering and therefore the claim does not add any other additional elements that would integrate the other recited judicial exceptions into a practical application. Accordingly, claim 9 is directed to unpatentable subject matter.
Claim 10
Claim 10 recites wherein the data structure is a data structure to be subjected to processing for solving the mathematical optimization problem in at least any one of a simulated annealing machine, a quantum annealing machine, and a quantum gate computer. The claim is directed to the intended use of the data structure, which is an idea of a solution that is not recited with specificity as to how the solution is accomplished. See MPEP 2106.05(f)(1). See Electric Power Group, LLC v. Alstom, S.A., 830 F.3d 1350, 1356, 119 USPQ2d 1739, 1743-44 (Fed. Cir. 2016); Intellectual Ventures I v. Symantec, 838 F.3d 1307, 1327, 120 USPQ2d 1353, 1366 (Fed. Cir. 2016); Internet Patents Corp. v. Active Network, Inc., 790 F.3d 1343, 1348, 115 USPQ2d 1414, 1417 (Fed. Cir. 2015). Accordingly, claim 10 is directed to unpatentable subject matter.
Claim 11
Claim 11 recites wherein the object corresponding to the mathematical model to be stored in the root node includes an object related to a mathematical expression representing the mathematical model or an object related to a cost function corresponding to the mathematical model. The claim adds limitations to the type of information that is stored in the data structure. The claim does not recite additional elements and therefore does not integrate the judicial exceptions into a practical application. Accordingly, claim 11 is directed to unpatentable subject matter.
Claim 12
Claim 12 recites wherein the acquired mathematical expression representing the mathematical model corresponding to the mathematical optimization problem includes a mathematical expression corresponding to a constrained optimization problem, and the method further comprises converting the data structure into a data structure corresponding to a binary optimization problem. Converting from one data structure to another data structure is an abstract idea that can either be a mental process (i.e., selecting a new data structure and transferring data to the new data structure) or a mathematical concept (i.e., algorithmically converting data to accommodate a new data structure). See MPEP 2106.04(a)(2). Accordingly, claim 12 is directed to unpatentable subject matter.
Claim 13-14
Claim 15 recites non-transitory computer readable medium that performs a method that is substantially the same as the method of claim 1. The limitation of non-transitory computer readable medium is a generic computer component and the claims are essentially judicial exceptions with the addition of “apply it.” Accordingly, for at least the same reasons as claim 1, claims 13 and 14 are rejected under 35 U.S.C. 101 for being directed to unpatentable subject matter.
Claim Rejections - 35 USC § 102
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 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.
(a)(2) the claimed invention was described in a patent issued under section 151, or in an application for patent published or deemed published under section 122(b), in which the patent or application, as the case may be, names another inventor and was effectively filed before the effective filing date of the claimed invention.
Claims 1-14 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Tanahashi, et al., (“Application of Ising Machines and a Software Development for Ising Machines,” hereinafter Tanahashi).
Claim 1
Tanahashi discloses:
A method for converting a mathematical optimization problem into an object program for a mathematical programming problem, the method comprising causing a processor to:
To consider the complicated combinatorial optimization problem, we start with a simple Hamiltonian to obtain the first stage of a proof-of-principle result. Tanahashi at pg. 8, col. 1.
With PyQUBO, we can define a Hamiltonian with spin or binary objects in a more straightforward way. We demonstrate construction of the QUBO matrix for the number partitioning problem with PyQUBO (Table II). Tanahashi at pg. 8, col. 1.
acquire information on a mathematical expression representing a mathematical model corresponding to the mathematical optimization problem;
After the reduction of higher-order interactions, we obtain the QUBO matrix corresponding to the combinatorial optimization problem we want to solve. Tanahashi at pg. 7, col. 2.
deblock the mathematical expression into components and
Thus, if we represent the equality/ inequality constraints in the original combinatorial optimization problem using only linear and quadratic terms of 0–1 binary variables, we can reformulate the combinatorial optimization problem using the Ising model or the QUBO. Tanahashi at pg. 2, col. 2-pg. 3, col. 1.
Representing an optimization problem using only linear terms is analogous to “deblocking the mathematical problem” because the resulting equation has terms separated by addition/subtraction.
store information on each component in an object, the components constituting the mathematical expression; and
The Hamiltonian in PyQUBO is internally represented as a tree. For example, the Hamiltonian for the number partitioning problem is represented as a tree shown in the left panel of Fig. 3. The compilation process of PyQUBO is shown in the right panel of Fig. 3. Tanahashi at pg. 8, col. 1.
In Fig. 3, each node includes a part of the numerical expression, the representation of the node in the code being analogous to an object.
PNG
media_image1.png
435
1166
media_image1.png
Greyscale
for the components of the mathematical expression, associate objects with each other through a connecting node as a data structure that is a tree structure in which an object corresponding to the mathematical model is taken as a root node and an object pertaining to each component from the deblocked mathematical expression is taken as a leaf node.
The Hamiltonian in PyQUBO is internally represented as a tree. For example, the Hamiltonian for the number partitioning problem is represented as a tree shown in the left panel of Fig. 3. The compilation process of PyQUBO is shown in the right panel of Fig. 3. Tanahashi at pg. 8, col. 1.
Claim 2
Tanahashi discloses:
wherein the object of the leaf node constituting the tree structure includes meta information about the component.
See Fig. 3, wherein the leaf nodes (objects) include information about the portion of the mathematical expression represented by the node.
PNG
media_image2.png
588
1166
media_image2.png
Greyscale
Claim 3
Tanahashi discloses:
wherein the meta information is associated with a component of the mathematical expression that is stored in at least one object sharing the connecting node.
PNG
media_image3.png
596
684
media_image3.png
Greyscale
Tanahashi at ph. 2, col. 2.
The “spin” is part of the mathematical expression and is represented in the tree structure as metadata for a leaf node:
PNG
media_image2.png
588
1166
media_image2.png
Greyscale
Claim 4
Tanahashi discloses:
wherein an object of a leaf node that is subordinate to the connecting node includes a component constituting a term pertaining to a constraint condition in the mathematical expression, and the meta information includes information about the constraint condition.
Here, we consider combinatorial optimization problems with equality constraints and represent them using the Ising model or QUBO. Tanahashi at pg. 3 at col. 1.
Claim 5
Tanahashi discloses:
wherein the constraint condition includes at least either of a condition pertaining to an equality constraint and a condition pertaining to an inequality constraint.
Here, we consider combinatorial optimization problems with equality constraints and represent them using the Ising model or QUBO. Tanahashi at pg. 3 at col. 1.
Claim 6
Tanahashi discloses:
wherein a component of the mathematical expression includes at least either of an operator and a literal expression, and the meta information includes information about subscripts appended to at least either of the operator and the literal expression, respectively.
See FIG. 3, labeled below:
PNG
media_image4.png
453
838
media_image4.png
Greyscale
Claim 7
Tanahashi discloses:
wherein a component of the mathematical expression includes a literal expression that defines data representing an indicator of an optimization target in the mathematical optimization problem, and a set of the data on the indicator that is defined by the literal expression is provided in a data structure that is different from the tree structure in which information on the literal expression is stored in a leaf.
Optimization problems pertain to finding conditions that minimize a given function, called cost function, under some given constraints. A mathematical expression of these problems are given by
PNG
media_image5.png
57
359
media_image5.png
Greyscale
where x is the vector representing the decision variables, fðxÞ is the cost function that is real-valued, and S is the set of decision variables satisfying the given constraints, in other words, the set of feasible solutions. When x is a discretized vector, the above optimization problem is called a combinatorial optimization problem. Tanahashi at pg. 2, col. 1.
The min of a function is a target for optimizing the function.
Claim 8
Tanahashi discloses:
wherein the mathematical programming problem includes a binary optimization problem.
Recently developed Ising machines specialize in searching better solutions to combinatorial optimization problems represented by an Ising model or a quadratic unconstrained binary optimization (QUBO) form. Tanahashi at pg. 1, col. 1.
To perform combinatorial optimization using Ising machines, we should prepare the Hamiltonian of the Ising model or the QUBO which corresponds to the cost function of the combinatorial optimization problem. Tanahashi at pg. 2, col. 2.
Claim 9
Tanahashi discloses:
wherein the binary optimization problem includes at least any one of a QUBO (unconstrained quadratic binary optimization problem), a PUBO (polynomial unconstrained binary optimization problem), a HUBO (high-order unconstrained binary optimization problem), and a constrained binary optimization problem.
Recently developed Ising machines specialize in searching better solutions to combinatorial optimization problems represented by an Ising model or a quadratic unconstrained binary optimization (QUBO) form. Tanahashi at pg. 1, col. 1.
To perform combinatorial optimization using Ising machines, we should prepare the Hamiltonian of the Ising model or the QUBO which corresponds to the cost function of the combinatorial optimization problem. Tanahashi at pg. 2, col. 2.
Claim 10
Tanahashi discloses:
wherein the data structure is a data structure to be subjected to processing for solving the mathematical optimization problem in at least any one of a simulated annealing machine, a quantum annealing machine, and a quantum gate computer.
In this section, we show the result of our study on the optimization of online advertisement allocation using a quantum annealing machine. Tanahashi at pg. 4, col. 2.
Claim 11
Tanahashi discloses:
wherein the object corresponding to the mathematical model to be stored in the root node includes an object related to a mathematical expression representing the mathematical model or an object related to a cost function corresponding to the mathematical model.
PNG
media_image6.png
291
675
media_image6.png
Greyscale
PNG
media_image7.png
153
660
media_image7.png
Greyscale
Tanahashi at pp. 3-4, col. 1.
Claim 12
Tanahashi discloses:
wherein the acquired mathematical expression representing the mathematical model corresponding to the mathematical optimization problem includes a mathematical expression corresponding to a constrained optimization problem, and the method further comprises converting the data structure into a data structure corresponding to a binary optimization problem.
The Hamiltonian in PyQUBO is internally represented as a tree. For example, the Hamiltonian for the number partitioning problem is represented as a tree shown in the left panel of Fig. 3. The compilation process of PyQUBO is shown in the right panel of Fig. 3. Firstly, the Hamiltonian is converted to a higher-order polynomial by folding the tree. Then, a higher order polynomial is reduced to a second-order polynomial by introducing auxiliary variables. Finally, the QUBO matrix is created from the coefficients of the second-order polynomial. In the next section, some features of PyQUBO are introduced, including placeholder and automatic validation of constraints. Tanahashi at pg. 8, col. 2.
Claims 13-14
Claims 13-14 disclose
non-transitory computer medium
See, e.g., Table II, illustrating code to generate the tree structure, wherein the code is stored in memory for later execution.
that stores components and instructions to perform a method that is substantially the same as the method disclosed in claim 1. Accordingly, for at least the same reasons and based on the same prior art as claim 1, claims 13-14 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Tanahashi.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure:
U.S. Pat. Pub. No. 2020/0175413, “QUANTUM COMPUTATION FOR OPTIMIZATION IN EXCHANGE SYSTEMS.”
WIPO Pub. No. 2017/152289, “METHODS AND SYSTEMS FOR QUANTUM COMPUTING.”
Communication
Any inquiry concerning this communication or earlier communications from the examiner should be directed to JOSEPH MORRIS whose telephone number is (703)756-5735. The examiner can normally be reached M-F 8:30-5:00.
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, Ryan Pitaro can be reached at (571) 272-4071. 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.
JOSEPH MORRIS
Examiner
Art Unit 2188
/JOSEPH P MORRIS/Examiner, Art Unit 2188
/RYAN F PITARO/Supervisory Patent Examiner, Art Unit 2188
Prosecution Insights