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 .
Priority
The present application, 18169230, filed 02/15/2023 claims foreign priority to JP2022-090013, filed 06/02/2022.
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 02/15/2023, 11/14/2023, 03/02/2026 and 09/11/2026 are in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner. The IDS submitted on 02/11/2026 is not being considered by examiner because it contains typographical error (See Miscellaneous Letter submitted by Applicant on 03/02/2026).
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 and 5-7 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Huang et al. (NPL – “QROSS: QUBO Relaxation Parameter Optimization via Learning Solver Surrogates”), hereinafter Huang.
Regarding claim 1, Huang teaches
a computer program that causes a computer to execute a process comprising (page 6 top “We use shgo optimiser from scipy to search parameter search. The search is based on the solver surrogate and does not involve QUBO solver. The search can be done on the CPU within a few seconds”; computer - CPU):
generating, for combinatorial optimization processing that searches for an optimum value of a solution vector including a plurality of variables each taking a discrete value based on an evaluation value calculated from the solution vector and a coefficient matrix with rows and columns corresponding to the plurality of variables, feature data from the coefficient matrix (abstract; page 1 introduction second paragraph “Many combinatorial optimization problems can be expressed in the form of … he conversion of such problem into a QUBO form is straightforward where the problem can be rewritten as … where A is referred as the relaxation parameter”; page 4 section 3.2 “We have two inputs for the solver surrogate: the problem instance, denoted as g, and relaxation parameter, denoted as A … Learning from g is tricky because the size of an instance could vary largely. We use an feature extraction layer that handle problems of different sizes. After the feature extraction, instances of different sizes are converted into fixed-size feature vectors”; Figure 2; and section 4.1; solution vector/ evaluation value –
x
in
x
T
Q
x
; coefficient matrix –
or
H
B
(
x
)
and
H
A
(
x
)
in Equations (4-6); Figure 7 and Appendix G; feature data – feature vectors of g);
generating parameter data representing one candidate value amongst a plurality of candidate values for a parameter controlling a search method of a solver that executes the combinatorial optimization processing by annealing (abstract “this relaxation introduces hyper-parameters that balance the objective and penalty terms for the constraints … tuning these parameters is an important problem”; introduction “A is referred as the relaxation parameter … Hence, relaxation parameter optimisation is an important step in this problem-solving process … The solver surrogate in QROSS only models certain aspects of the original QUBO solver that are necessary for relaxation parameter tuning. Given a problem instance and a relaxation parameter, the solver surrogate predicts the probability that the QUBO solver finds a feasible solution, as well as the objective energies … Based on the solver surrogate, we propose two search strategies that will provide the trial values of the relaxation parameters”; section 3.1 and Figure 1; parameter data – relaxation parameter A);
calculating a predicted value representing a prediction of the evaluation value corresponding to the one candidate value by inputting the feature data and the parameter data to a machine learning model that has been trained (Figure 2 section 3.2 last paragraph “Given an instance g and a parameter A, we find the prediction and the ground truth of
P
f
,
E
a
v
g
, and
E
s
t
d
by QUBO solver and solver surrogate”; section 3.4; introduction fourth paragraph “We build the surrogate model using machine learning on data obtained from the QUBO solver when applied to solve instances of a problem”); and
determining a parameter value to be set for the parameter of the solver by repeating the generating of the parameter data and the calculating of the predicted value (Figure 1 and page 4 top “The red star-shaped marker is the bottom of the dip, where the optimal solution appears. The parameter that leads to near optimal solution is called optimal parameter”; section 3.4 “Parameter selection strategies try different A, until it finds a promising
A
^
”; section 3.4.2 “First, we propose Minimum Fitness Strategy (MFS), which attempts to predict the optimal relaxation parameter
A
^
that leads to minimum fitness”; section 3.4.2 “we can use
P
f
-based Strategy (PBS) to find promising parameters” parameter value -
A
^
).
Regarding claim 5, Huang teaches all the limitations of claim 1 as stated above. Further, Huang teaches the process further comprising: training the machine learning model using training data in which a plurality of coefficient matrices, a plurality of parameter values, and a plurality of evaluation values are mapped to each other (Figure 2 and section 3.3 “To train the solver surrogate, we prepare a dataset from past instances and solutions of a solver. Because heuristic QUBO solvers have a stochastic nature, it usually returns a batch of solutions and corresponding objective energy for an instance g and parameter A”).
Regarding claim 6, it is directed to a method corresponding to the computer program stored in the non-transitory computer-readable recording medium of claim 1. All steps performed by the method of claim 6 are included in the computer program stored in the non-transitory computer-readable recording medium of claim 1. Claim 1 analysis applies equally to claim 6.
Regarding claim 7, it is directed to an apparatus configured to execute the computer program stored in the non-transitory computer-readable recording medium of claim 1. All steps performed by the processor of claim 6 are included in the computer program stored in the non-transitory computer-readable recording medium of claim 1 that is executed by the computer. Claim 1 analysis applies equally to claim 7. Further, Huang teaches a memory configured to store a coefficient matrix having rows and columns corresponding to a plurality of variables each taking a discrete value and a machine learning model that has been trained (section 3.3 and 3.4 memory - component for storing the data to implement Figure 2).
Claim Rejections - 35 USC § 103
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 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 2-3 are rejected under 35 U.S.C. 103 as being unpatentable over Huang in view of Joshi et al. (NPL – “An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem”), hereinafter Joshi.
Regarding claim 2, Huang teaches all the limitations of claim 1 as stated above. Further, Huang teaches
wherein: the feature data includes graph data including a plurality of nodes corresponding to the plurality of variables and a plurality of feature vectors mapped to the plurality of nodes (Appendix G “The choice of the feature extraction layer depends on the representation of a problem. Possible choices are convolutional networks for matrix representations, graph convolutional networks for graph representations … Good examples for TSP are [30, 31], in which the authors take adjacency matrix of TSP as fully connected graph and apply graph convolutional neural network to extract features. Our experiments are based on the pre-trained model for feature extraction in [30]”).
Huang does not explicitly teach the machine learning model performs a convolution operation on the plurality of feature vectors based on a connection relationship of the plurality of nodes represented by the graph data.
However, on the same field of endeavor, Joshi teaches a machine learning model that performs a convolution operation on a plurality of feature vectors based on a connection relationship of the plurality of nodes represented by graph data (Joshi Figure 1; section 4.1; and Appendix B; feature vectors – xi).
Accordingly, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Huang and configure the machine learning model to perform a convolution operation on the plurality of feature vectors based on a connection relationship of the plurality of nodes represented by the graph data in order to apply graph convolutional neural network to extract the feature vectors which can be used for solving the Traveling Salesman Problem (Huang Appendix C and G). Further, Huang discloses using the model of Joshi (i.e., reference [30]) for feature extraction, therefore, it is obvious to combine the Huang and Joshi and use the feature extraction algorithm of Joshi.
Therefore, the combination of Huang as modified in view of Joshi teaches the machine learning model performs a convolution operation on the plurality of feature vectors based on a connection relationship of the plurality of nodes represented by the graph data.
Regarding claim 3, Huang as modified in view of Joshi teaches all the limitations of claim 2 as stated above. Further, Huang as modified in view of Joshi teaches
wherein: the coefficient matrix includes a constraint matrix which represents constraints on the discrete values taken by the plurality of variables and a cost matrix which represents a relationship between the plurality of variables, other than the constraints (Huang page 6 section 4.1; constraint matrix -
H
A
(
x
)
; cost matrix -
H
B
(
x
)
, and
the feature data includes first graph data (Huang Appendix C “[30] uses deep Graph Convolutional Networks to build TSP graph representations”; Appendix G).
Huang does not explicitly teach the feature data includes first graph data generated from the cost matrix and second graph data generated from the constraint matrix.
However, on the same field of endeavor, Joshi discloses that an input to a graph convolutional neural network is a graph (Joshi Fig. 1 and section 4 “Given a graph as an input, we train a graph ConvNet model to directly output an adjacency matrix corresponding to a TSP tour”).
Accordingly, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Huang and configure the feature data to include first graph data generated from the cost matrix and second graph data generated from the constraint matrix as input to the graph convolutional neural network. As discussed, the problem instance g includes a constraint matrix and a cost matrix as shown in the problem in Equations (4-6). Therefore, it would be obvious to generate corresponding graphs representing
H
A
(
x
)
and
H
B
(
x
)
because graphs are the input to the graph convolutional neural network (Joshi section 4).
Therefore, the combination of Huang as modified in view of Joshi teaches the feature data includes first graph data generated from the cost matrix and second graph data generated from the constraint matrix.
Claim 4 is rejected under 35 U.S.C. 103 as being unpatentable over Huang in view of Huang.
Regarding claim 4, Huang teaches all the limitations of claim 1 as stated above. Further, Huang teaches wherein: the determining includes performing candidate value to be tested next based on one or more tested candidate values and one or more calculated predicted values (section 3.4 “Parameter selection strategies try different A, until it finds a promising
A
^
”).
Huang does not explicitly teach wherein: the determining includes performing Bayesian optimization processing that selects a candidate value to be tested next based on one or more tested candidate values and one or more calculated predicted values.
However, Huang discloses that Bayesian optimization is famous search algorithm for finding an optimal solution with fewer trials (section 5.1 first paragraph).
Accordingly, it would have been obvious to a person of ordinary skill in the art before the effective filing date of the claimed invention to modify Huang and use Bayesian optimization for determining the parameter value to be set because it may find the optimal parameter value with fewer trials (Huang section 5.1 first paragraph).
Therefore, the combination of Huang as modified teaches wherein: the determining includes performing Bayesian optimization processing that selects a candidate value to be tested next based on one or more tested candidate values and one or more calculated predicted values.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicant's disclosure.
Dadkhahi et al. (US 20220284305 A1) generally related to a surrogate machine learning model in combinatorial optimization algorithms.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Carlo Waje whose telephone number is (571)272-5767. The examiner can normally be reached 9:00-6:00 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, 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.
/Carlo Waje/Examiner, Art Unit 2151 (571)272-5767
Prosecution Insights