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 .
Note on Prior art
US20220414184A1 to Bagherbeik et al teaches claim 1. In Claim 2, Bagherbeik teaches the holding circuit configured to hold values for the plurality of multi-valued variables in para 120, “Each bit in a binary state matrix (X or S) has a cached local field. When a proposal for an assignment change is accepted, an n-by-n matrix (hereinafter, cache matrix) based on the local fields is updated in time proportional to n2. Note that ΔC is calculated in time that does not depend on n.” However, Claim 2 requires that cache to hold on to the change amount for each of the variables, and Bagherbeik para 120 specifically says it doesn’t keep the change amount because, “ΔC is calculated in time that does not depend on n.” Therefore claims 2-9 don’t have a prior art rejection.
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-11 rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea of a mathematical relationship without significantly more. The claims recite the abstract idea of:
1. …
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables;
calculating, for each of the plurality of multi-valued variables, a change amount of the values of the evaluation function associated with a transition to the transition destination candidates, based on the evaluation function information;
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates.
2. …
a holding … that holds the change amount associated with the transition of each of the plurality of multi-valued variables;
a calculation …that calculates, for each of the plurality of multi-valued variables, a difference value of the change amount associated with a change in the values of the multi-valued variables for which the transition is accepted; and
an update … that updates the change amount by using the difference value.
3. … according to claim 2, wherein
the combinatorial optimization problem is an assignment problem represented by using a flow matrix and a distance matrix,
the memory includes:
a first … configured to store a first matrix that is one of the flow matrix and the distance matrix;
a second … configured to store a second matrix that is the other of the flow matrix and the distance matrix and includes matrix elements arrayed based on the values of the plurality of multi-valued variables; and
a third … configured to store a third matrix that is the other of the flow matrix and the distance matrix and includes the matrix elements arrayed based on the values of the transition destination candidates of the plurality of multi-valued variables, and
the calculation … is configured to calculate the difference value, based on: first matrix elements of the first matrix designated by identification numbers of the multi-valued variables for which the transition is accepted; second matrix elements of the second matrix and third matrix elements of the third matrix designated by the values before the transition of the multi-valued variables for which the transition is accepted; and fourth matrix elements of the second matrix and fifth matrix elements of the third matrix designated by the values after the transition of the multi-valued variables.
4. The data processing… according to claim 3, wherein
either rows or columns of the second matrix and the third matrix are designated by the values of the multi-valued variables for which the transition is accepted or the values after the transition of the multi-valued variables, and
the second matrix elements, the third matrix elements, the fourth matrix elements, or the fifth matrix elements included in the designated rows or columns are read from the second memory or the third memory.
5. The data processing … according to claim 3, wherein
the second matrix elements and the third matrix elements are read in parallel from the second memory and the third memory at a first read timing, and
the fourth matrix elements and the fifth matrix elements are read in parallel from the second memory and the third memory at a second read timing.
6. The data processing … according to claim 3, wherein
the first to fifth matrix elements are read from the first …, the second …, or the third … at different read timings from each other, by using a common read path, and
the calculation … is configured to input the first to fifth matrix elements to a common arithmetic circuit to calculate the difference value.
7. The data processing device according to claim 3, wherein
the processor is configured to interchange, between the second matrix and the third matrix, columns or rows of the second matrix and the third matrix designated by the identification numbers of the multi-valued variables for which the transition is accepted.
8. The data processing … according to claim 3, wherein
the transition destination candidates include first transition destination candidates and second transition destination candidates for each of the plurality of multi-valued variables,
the third matrix is arrayed based on the values of the first transition destination candidates, and
the storage unit further includes a fourth memory that stores a fourth matrix that is the other of the flow matrix and the distance matrix and includes the matrix elements arrayed based on the values of the second transition destination candidates.
9. The data processing … according to claim 2, wherein
the combinatorial optimization problem is an assignment problem represented by using a flow matrix and a distance matrix,
the … includes:
a first … configured to store a first matrix that is one of the flow matrix and the distance matrix; and
a second … configured to store a fourth matrix that includes matrix elements expressed by differences between: the values of the matrix elements of a second matrix that is the other of the flow matrix and the distance matrix and is arrayed based on the values of the plurality of multi-valued variables; and the values of a third matrix that is the other of the flow matrix and the distance matrix and is arrayed based on the values of the transition destination candidates of the plurality of multi-valued variables, and
the calculation … is configured to calculate the difference value, based on: first matrix elements of the first matrix designated by identification numbers of the multi-valued variables for which the transition is accepted; second matrix elements of the fourth matrix designated by the values before the transition of the multi-valued variables for which the transition is accepted; and third matrix elements of the fourth matrix designated by the values after the transition of the multi-valued variables.
10. A … program for causing a computer to perform processing comprising:
obtaining evaluation function information stored in a storage unit of the computer, the evaluation function information indicating an evaluation function of a combinatorial optimization problem represented by using a plurality of multi-valued variables; and
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables;
calculating, for each of the plurality of multi-valued variables, a change amount of the values of the evaluation function associated with a transition to the transition destination candidates, based on the evaluation function information;
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates.
11. A data processing method implemented by a computer, the data processing method comprising:
obtaining evaluation function information stored in a storage unit of the computer, the evaluation function information indicating an evaluation function of a combinatorial optimization problem represented by using a plurality of multi-valued variables; and
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables;
calculating, for each of the plurality of multi-valued variables, a change amount of the values of the evaluation function associated with a transition to the transition destination candidates, based on the evaluation function information;
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates.
This judicial exception is not integrated into a practical application because the claims are merely linked to a computer to execute the abstract idea. The claims do not include additional elements that are sufficient to amount to significantly more than the judicial exception because the additional element of a “processing device”, various circuits and memories are generic computer parts; and mere instructions to apply an abstract idea to a generic computer does not amount to significantly more than the abstract idea. MPEP 2106.05(f)
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.
Claim 8 recites the limitation "the storage unit". There is insufficient antecedent basis for this limitation in the claim. Claim 1 is missing the claimed “storage unit” from claims 10 and 11.
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, 10 and 11 are rejected under 35 U.S.C. 103 as being unpatentable over US20220414184A1 to Bagherbeik et al and A Hybrid Method of Combinatorial Search and Coordinate Descent for Discrete Optimization to Yuan et al.
Bagherbeik teaches claim 1. A data processing device comprising:
a memory configured to store evaluation function information indicating an evaluation function of a combinatorial optimization problem represented by using a plurality of multi-valued variables; and (Bagherbeik abs “A storage unit stores a flow matrix representing the flows between a plurality of entities to be assigned to a plurality of destinations, and a distance matrix representing the distances between the plurality of destinations.” Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged.”)
a processor coupled to the memory, the processor being configured to perform processing including: (Bagherbeik fig. 4)
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables; (Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged. The change in the evaluation function (equation (1)) resulting from the exchange of the destinations (identified by IDs=φ(a) and φ(b)) of the two entities (identified by IDs=a and b) is given by equation…”)
calculating, for (Bagherbeik para 179 “Then, a ΔCS rel value for the assignment of the entity with ID=a to the destination with ID=1 is calculated…”)
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and (Bagherbeik para 165-168 “determined whether Pacc is greater than a random number rand( ) in the range of 0 to 1… If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange … After step S39 is executed, if Pacc>rand( ) is not obtained at step S34, or if C<Cmin is not obtained at step S38, the process is repeated from step S31 until i reaches I.”)
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates. (Bagherbeik para 166 “If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange …”)
Bagherbeik doesn’t teach calculating, for each of the plurality of multi-valued variables, a change amount.
However, Yuan teaches calculating, for each of the plurality of multi-valued variables, a change amount. (Yuan p. 3 “we pick top-k coordinates that lead to the greatest descent when one variable is changed and the rest variables are fixed based on the current solution xt…. For J, we compute the decrease for each coordinate j ∈ J of xt when changing from nonzero to exactly zero…” The calculation is shown below.)
PNG
media_image1.png
28
293
media_image1.png
Greyscale
Yuan, Bagherbeik and the claims are all related to assignment vectors. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to include Yuan’s greedy coordinate-selection for each value so that Bagherbeik’s local search finds the coordinate with “the greatest descent…” Yuan p. 3.
Bagherbeik teaches claim 10. A non-transitory computer-readable recording medium storing a program for causing a computer to perform processing comprising:
obtaining evaluation function information stored in a storage unit of the computer, the evaluation function information indicating an evaluation function of a combinatorial optimization problem represented by using a plurality of multi-valued variables; and (Bagherbeik abs “A storage unit stores a flow matrix representing the flows between a plurality of entities to be assigned to a plurality of destinations, and a distance matrix representing the distances between the plurality of destinations.” Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged.”)
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables; (Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged. The change in the evaluation function (equation (1)) resulting from the exchange of the destinations (identified by IDs=φ(a) and φ(b)) of the two entities (identified by IDs=a and b) is given by equation…”)
calculating, for (Bagherbeik para 179 “Then, a ΔCS rel value for the assignment of the entity with ID=a to the destination with ID=1 is calculated…”)
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and (Bagherbeik para 165-168 “determined whether Pacc is greater than a random number rand( ) in the range of 0 to 1… If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange … After step S39 is executed, if Pacc>rand( ) is not obtained at step S34, or if C<Cmin is not obtained at step S38, the process is repeated from step S31 until i reaches I.”)
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates. . (Bagherbeik para 166 “If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange …”)
Bagherbeik doesn’t teach calculating, for each of the plurality of multi-valued variables, a change amount.
However, Yuan teaches calculating, for each of the plurality of multi-valued variables, a change amount. (Yuan p. 3 “we pick top-k coordinates that lead to the greatest descent when one variable is changed and the rest variables are fixed based on the current solution xt…. For J, we compute the decrease for each coordinate j ∈ J of xt when changing from nonzero to exactly zero…” The calculation is shown below.)
PNG
media_image1.png
28
293
media_image1.png
Greyscale
Yuan, Bagherbeik and the claims are all related to assignment vectors. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to include Yuan’s greedy coordinate-selection for each value so that Bagherbeik’s local search finds the coordinate with “the greatest descent…” Yuan p. 3.
Bagherbeik teaches claim 11. A data processing method implemented by a computer, the data processing method comprising:
obtaining evaluation function information stored in a storage unit of the computer, the evaluation function information indicating an evaluation function of a combinatorial optimization problem represented by using a plurality of multi-valued variables; and (Bagherbeik abs “A storage unit stores a flow matrix representing the flows between a plurality of entities to be assigned to a plurality of destinations, and a distance matrix representing the distances between the plurality of destinations.” Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged.”)
generating, based on the evaluation function information, transition destination candidates that are a part of respective transitionable ranges of values of the plurality of multi-valued variables; (Bagherbeik para 79 “One local search method for QAP is a pairwise exchange of entities. In this technique, two entities are selected and their destinations are exchanged. The change in the evaluation function (equation (1)) resulting from the exchange of the destinations (identified by IDs=φ(a) and φ(b)) of the two entities (identified by IDs=a and b) is given by equation…”)
calculating, for (Bagherbeik para 179 “Then, a ΔCS rel value for the assignment of the entity with ID=a to the destination with ID=1 is calculated…”)
specifying the multi-valued variables for which the transition is accepted, from among the plurality of multi-valued variables, based on the change amount; and (Bagherbeik para 165-168 “determined whether Pacc is greater than a random number rand( ) in the range of 0 to 1… If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange … After step S39 is executed, if Pacc>rand( ) is not obtained at step S34, or if C<Cmin is not obtained at step S38, the process is repeated from step S31 until i reaches I.”)
causing the values of the specified multi-valued variables to transition to the values of the transition destination candidates. (Bagherbeik para 166 “If Pacc>rand( ) is obtained, the a-th and b-th columns of DX are swapped (DX *,a, DX *,b←DX *,b, DX *,a) (step S35). In addition, the assignment state is updated according to the destination exchange …”)
Bagherbeik doesn’t teach calculating, for each of the plurality of multi-valued variables, a change amount.
However, Yuan teaches calculating, for each of the plurality of multi-valued variables, a change amount. (Yuan p. 3 “we pick top-k coordinates that lead to the greatest descent when one variable is changed and the rest variables are fixed based on the current solution xt…. For J, we compute the decrease for each coordinate j ∈ J of xt when changing from nonzero to exactly zero…” The calculation is shown below.)
PNG
media_image1.png
28
293
media_image1.png
Greyscale
Yuan, Bagherbeik and the claims are all related to assignment vectors. It would have been obvious to a person having ordinary skill in the art, at the time of filing, to include Yuan’s greedy coordinate-selection for each value so that Bagherbeik’s local search finds the coordinate with “the greatest descent…” Yuan p. 3.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Austin Hicks whose telephone number is (571)270-3377. The examiner can normally be reached Monday - Thursday 8-4 PST.
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, Mariela Reyes can be reached at (571) 270-1006. 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.
/AUSTIN HICKS/ Primary Examiner, Art Unit 2142
Prosecution Insights