DETAILED ACTION
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Interpretation
The following is a quotation of 35 U.S.C. 112(f):
(f) Element in Claim for a Combination. – An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The following is a quotation of pre-AIA 35 U.S.C. 112, sixth paragraph:
An element in a claim for a combination may be expressed as a means or step for performing a specified function without the recital of structure, material, or acts in support thereof, and such claim shall be construed to cover the corresponding structure, material, or acts described in the specification and equivalents thereof.
The claims in this application are given their broadest reasonable interpretation using the plain meaning of the claim language in light of the specification as it would be understood by one of ordinary skill in the art. The broadest reasonable interpretation of a claim element (also commonly referred to as a claim limitation) is limited by the description in the specification when 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is invoked.
As explained in MPEP § 2181, subsection I, claim limitations that meet the following three-prong test will be interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph:
(A) the claim limitation uses the term “means” or “step” or a term used as a substitute for “means” that is a generic placeholder (also called a nonce term or a non-structural term having no specific structural meaning) for performing the claimed function;
(B) the term “means” or “step” or the generic placeholder is modified by functional language, typically, but not always linked by the transition word “for” (e.g., “means for”) or another linking word or phrase, such as “configured to” or “so that”; and
(C) the term “means” or “step” or the generic placeholder is not modified by sufficient structure, material, or acts for performing the claimed function.
Use of the word “means” (or “step”) in a claim with functional language creates a rebuttable presumption that the claim limitation is to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites sufficient structure, material, or acts to entirely perform the recited function.
Absence of the word “means” (or “step”) in a claim creates a rebuttable presumption that the claim limitation is not to be treated in accordance with 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph. The presumption that the claim limitation is not interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, is rebutted when the claim limitation recites function without reciting sufficient structure, material or acts to entirely perform the recited function.
Claim limitations in this application that use the word “means” (or “step”) are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action. Conversely, claim limitations in this application that do not use the word “means” (or “step”) are not being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, except as otherwise indicated in an Office action.
This application includes one or more claim limitations that do not use the word “means,” but are nonetheless being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, because the claim limitation(s) uses a generic placeholder that is coupled with functional language without reciting sufficient structure to perform the recited function and the generic placeholder is not preceded by a structural modifier. Such claim limitation is:
a combinatorial optimization problem device in claim 1.
Because this/these claim limitation(s) is/are being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, it/they is/are being interpreted to cover the corresponding structure described in the specification as performing the claimed function, and equivalents thereof.
In review of the specification, the combinatorial optimization problem solution device is interpreted to comprise a server, such as a cloud server storing a combinatorial optimization problem solution program stored in an auxiliary memory, wherein the combinatorial optimization problem solution device is separate from the combinatorial optimization problem information transmission device, and connected to, and including equivalents. See [0038], [0126], fig 1 device 2.
If applicant does not intend to have this/these limitation(s) interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph, applicant may: (1) amend the claim limitation(s) to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph (e.g., by reciting sufficient structure to perform the claimed function); or (2) present a sufficient showing that the claim limitation(s) recite(s) sufficient structure to perform the claimed function so as to avoid it/them being interpreted under 35 U.S.C. 112(f) or pre-AIA 35 U.S.C. 112, sixth paragraph.
Specification
The disclosure is objected to because of the following informalities: Paragraph [0027] [FIG. 3] recites "depict", this appears to be a typographical error and should possibly recite "depicts". Paragraph [0053] recites "COOdinate", this appears to be a typographical error and should possibly recite "COOrdinate".
Appropriate correction is required.
Claim Objections
Claim 3 objected to because of the following informalities: Claim 3 line 4 recites "COOdinate". This appears to be a typographical error and should possibly recite "COOrdinate". Appropriate correction is required.
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-6 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 1 lines 5-8 recite “calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time”. Lines 11-13 recite “transmit the difference matrix after compression to a combinatorial optimization problem solution device that finds a solution to the combinatorial optimization problem”. It is unclear whether the solution found in lines 11-13 is the same solution as the solution found in lines 5-8. For purposes of examination, Examiner interprets as a subsequent solution. Furthermore, it is unclear what is meant by a solution was found last time. It is unclear what time the last time is in reference to. Furthermore, with respect to lines 11-13, as to the transmitting to “a combinatorial problem solution device that finds a solution to the combinatorial optimization problem”, the finding of the solution is inferentially claimed. It is unclear whether the finding a solution is being positively claimed or not. For purposes of examination, Examiner interprets that the finding of the solution is a required element. Claims 2-4 inherit the same deficiency as claim 1 based on dependence.
Claim 4 lines 4-5 recite “when comparing the first matrix and the second matrix, elements of a row and column corresponding to the row”. It is unclear what is meant by the column corresponding to the row, because all columns will correspond to the row in some way.
Claim 4 lines 8-10 recite “wherein the row corresponds to a row whose elements are different between the first matrix and the second matrix, or a column of the difference matrix and an index of the column”. With the conditional word “or” it is unclear whether the device configures one or the other, or the device is configured to operate under both conditions. For purposes of examination, Examiner interprets as the device configures one or the other.
Claim 5 lines 4-5 recite “store a first matrix representing a combinatorial optimization problem for which a solution was found last time”. It is unclear what is meant by a solution was found last time. It is unclear what time the last time is in reference to.
Claim 6 lines 10-12 recite “calculate a difference matrix which is a difference between a first matrix representing the combinatorial optimization problem for which the solution was found last time”. It is unclear what is meant by a solution was found last time. It is unclear what time the last time is in reference to.
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-6 are rejected under 35 U.S.C. § 101 because the claimed invention is directed to a judicial exception (i.e., a law of nature, a natural phenomenon, or an abstract idea) without significantly more.
Regarding claim 1, under the Alice framework Step 2A prong 1, the claim recites Mathematical concepts. The claim recites mathematical calculations and mathematical relationships for calculating a difference matrix related to a solution to a combinatorial optimization problem. Specifically, the claim recites the following:
calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem;
compress the difference matrix; and
finds a solution to the combinatorial optimization problem.
For these reasons, these are steps in a mathematical calculation using mathematical relationships.
Under the Alice framework Step 2A prong 2 analysis, additional elements not reciting Mathematical equations and mathematical calculations thereof include: a combinatorial optimization information transmission device comprising: a memory configured to store instructions; and a processor configured to execute the instructions, and transmit the difference matrix after compression to a combinatorial optimization problem solution device. These additional elements do no more than generally link the additional element to the mathematical calculations in a manner that in effect merely recites “apply it” to the math, or recite mere instructions to apply the exception using generic computer components. Furthermore, the storing instruction and the transmitting to another device comprise an insignificant extra solution activity. For these reasons claim 1 is not integrated into a practical application.
Moreover, under the Alice Framework Step 2B analysis, the claim, considered individually and as an ordered combination does not include additional elements that are sufficient to amount to significantly more than the abstract idea. As discussed in the Step 2A prong 2 analysis, the claim merely generally links the additional element to the math. Furthermore, as stated in the Step 2A prong 2 analysis, the claims recite mere instructions to apply the exception using generic computer components. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. Furthermore, the storing instruction and the transmitting to another device are well understood, routine, and conventional activity. See MPEP 2106.05(d) i, iv. For these reasons claim 1 elements considered individually and as an ordered combination does not amount to significantly more than the abstract idea.
Claims 2-4 are rejected for at least the reasons cited with respect to the claim 1 analysis. Under the Step 2A prong 1 analysis, claims 2-4 merely further mathematically limit the claim 1 mathematical elements recited. Claims 2-4 contain no further additional elements that would require further consideration under Step 2A prong 2 or Step 2B.
Regarding claim 5, under the Alice framework Step 2A prong 1, the claim recites Mathematical concepts. The claim recites mathematical calculations and mathematical relationships for restoring a difference matrix, deriving a second matrix, and solving a combinatorial optimization problem. Specifically, the claim recites the following:
a difference matrix which is a difference between the first matrix and a second matrix representing the latest combinatorial optimization problem,
restore the difference matrix from the result of compression;
derive the second matrix based on the restored difference matrix and the first matrix;
find a solution to the combinatorial optimization problem using the derived second matrix.
For these reasons, these are steps in a mathematical calculation using mathematical relationships.
Under the Alice framework Step 2A prong 2 analysis, additional elements not reciting Mathematical equations and mathematical calculations thereof include: a combinatorial optimization information transmission device comprising: a memory configured to store instructions; and a processor configured to execute the instructions, receive a result of compression of a difference matrix and transmit the solution to the combinatorial optimization problem information transmission device. These additional elements do no more than generally link the additional element to the mathematical calculations in a manner that in effect merely recites “apply it” to the math, or recite mere instructions to apply the exception using generic computer components. Furthermore, the storing instruction, the receiving from another device that transmits information, and the transmitting to another device comprise an insignificant extra solution activity. For these reasons claim 5 is not integrated into a practical application.
Moreover, under the Alice Framework Step 2B analysis, the claim, considered individually and as an ordered combination does not include additional elements that are sufficient to amount to significantly more than the abstract idea. As discussed in the Step 2A prong 2 analysis, the claim merely generally links the additional element to the math. Furthermore, as stated in the Step 2A prong 2 analysis, the claims recite mere instructions to apply the exception using generic computer components. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. Furthermore, the storing instruction, the receiving from another device that transmits information, and the transmitting to another device comprise are well understood, routine, and conventional activity. See MPEP 2106.05(d) i, iv. For these reasons claim 5 elements considered individually and as an ordered combination does not amount to significantly more than the abstract idea.
Regarding claim 6, under the Alice framework Step 2A prong 1, the claim recites Mathematical concepts. The claim recites mathematical calculations and mathematical relationships for calculating a difference matrix related to a solution to a combinatorial optimization problem restoring a difference matrix, deriving a second matrix, and solving a combinatorial optimization problem. Specifically, the claim recites the following:
calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem;
compress the difference matrix; and
restore the difference matrix from the result of compression;
derive the second matrix based on the restored difference matrix and the first matrix;
find a solution to the combinatorial optimization problem using the derived second matrix.
For these reasons, these are steps in a mathematical calculation using mathematical relationships.
Under the Alice framework Step 2A prong 2 analysis, additional elements not reciting Mathematical equations and mathematical calculations thereof include: a solution system comprising: a combinatorial optimization information transmission device that transmits information on a combinatorial optimization problem; and a combinatorial optimization problem solution device comprising: a first memory configured to store instructions; and a first processor configured to execute the instructions, transmit the difference matrix after compression to the combinatorial optimization problem solution device, a second memory configured to store instructions; and a second processor configured to execute the instructions to: store the first matrix, receive the difference matrix after compression, and transmit the solution to the combinatorial optimization problem information transmission device. These additional elements do no more than generally link the additional element to the mathematical calculations in a manner that in effect merely recites “apply it” to the math, or recite mere instructions to apply the exception using generic computer components. Furthermore, the storing instruction, the receiving from another device that transmits information, and the transmitting to another device comprise an insignificant extra solution activity. For these reasons claim 6 is not integrated into a practical application.
Moreover, under the Alice Framework Step 2B analysis, the claim, considered individually and as an ordered combination does not include additional elements that are sufficient to amount to significantly more than the abstract idea. As discussed in the Step 2A prong 2 analysis, the claim merely generally links the additional element to the math. Furthermore as stated in the Step 2A prong 2 analysis, the claims recite mere instructions to apply the exception using generic computer components. Mere instructions to apply an exception using generic computer components cannot provide an inventive concept. Furthermore, the storing instruction, the receiving from another device that transmits information, and the transmitting to another device comprise are well understood, routine, and conventional activity. See MPEP 2106.05(d) i, iv. For these reasons claim 6 elements considered individually and as an ordered combination does not amount to significantly more than the abstract idea.
Allowable Subject Matter
Claims 1-6 would be allowable if rewritten to overcome the rejections under 35 USC 112(b), and 35 USC 101, and with respect to claim 3, the claim objection.
The following is a statement of reasons for the indication of allowable subject matter. Applicant claims apparatus for solving a combinatorial optimization problem including compressing and decompressing a matrix based on a difference matrix, wherein the apparatus as in claim 6 comprises:
a combinatorial optimization problem information transmission device that transmits information on a combinatorial optimization problem; and
a combinatorial optimization problem solution device that finds a solution to the combinatorial optimization problem,
wherein the combinatorial optimization problem information transmission device comprises:
a first memory configured to store instructions; and
a first processor configured to execute the instructions to:
calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem;
compress the difference matrix; and
transmit the difference matrix after compression to the combinatorial optimization problem solution device, and
wherein the combinatorial optimization problem solution device comprises:
a second memory configured to store instructions; and
a second processor configured to execute instructions to:
store the first matrix;
receive the difference matrix after compression from the first processor of the combinatorial optimization problem information transmission device;
restore the difference matrix from the result of compression;
derive the second matrix based on the restored difference matrix and the first matrix;
find a solution to the combinatorial optimization problem using the derived second matrix; and
transmit the solution to the combinatorial optimization problem information transmission device.
The primary reasons for indication of allowable subject matter is the combination of the limitations with respect to calculating a difference matrix representing a combinatorial optimization problem, compressing the difference matrix as to claim 1 and 6, and restoring the difference matrix, deriving the second matrix and finding the solution to the combinatorial optimization problem as to claims 5 and 6 in combination with the remaining limitations and as highlighted above.
US 20120130928 A1 Bell, JR. et al., (hereinafter “Bell”) discloses an apparatus that calculates candidate solutions to an optimization problem including compression of candidate solutions to minimize memory space consumed to compute a solution to an optimization problem (abstract, fig 1). Bell further discloses generating a difference comparison key (fig 1, [0016]). Bell does not, however, teach or suggest to calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem; compress the difference matrix; or to derive the second matrix based on the restored difference matrix and the first matrix; find a solution to the combinatorial optimization problem using the derived second matrix.
US 20150379054 A1 Kernert et al., (hereinafter “Kernert”) discloses storing sparse matrices in memory, including dynamic matrix manipulate operations including a compressed sparse row representation to allow performing linear operations on large, sparse matrices (abstract, fig 13A, 13B). Kernert does not, however, teach or suggest to calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem; compress the difference matrix; or to derive the second matrix based on the restored difference matrix and the first matrix; find a solution to the combinatorial optimization problem using the derived second matrix.
US 20230004852 A1 Ide et al., (hereinafter “Ide”) discloses converting an objective function of a combinatorial optimization into another form by replacing a first variable to be optimized with a second variable to be optimized (abstract, fig 2, fig 3, fig 6). Ide does not, however, teach or suggest to calculate a difference matrix which is a difference between a first matrix representing a combinatorial optimization problem for which a solution was found last time and a second matrix representing the latest combinatorial optimization problem; compress the difference matrix; or to derive the second matrix based on the restored difference matrix and the first matrix; find a solution to the combinatorial optimization problem using the derived second matrix.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to EMILY E LAROCQUE whose telephone number is (469)295-9289. The examiner can normally be reached on 10:00am - 1200pm, 2:00pm - 8pm ET M-F.
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 on 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 an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/EMILY E LAROCQUE/Primary Examiner, Art Unit 2182
Prosecution Insights