DETAILED ACTION
This office action is in response to submission of application on 06/14/2023.
Claims 1-31 are presented for examination.
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 .
Information Disclosure Statement
The information disclosure statement (IDS) submitted on 08/14/2024 is in compliance with the provisions of 37 CFR 1.97. Accordingly, the information disclosure statement is being considered by the examiner.
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-31 are rejected under 35 U.S.C. 101 because the claimed invention is directed to an abstract idea without significantly more.
Claim 1:
Step 1: The claim is directed to a method, which falls within the statutory category of a process.
Step 2A Prong 1: The claim is directed to an abstract idea. Specifically, the claim recites:
generating, from the parameters of the MIP, an input representation; (Abstract idea – mental process. Generating an input representation of MIP parameters can practically be performed in the human mind or with the aid of pen and paper, for example, by drawing a bipartite graph on a sheet of paper, with nodes of the graph representing variables and constraints of the MIP. The courts have recognized that claims can recite a mental process even if they are claimed as being performed on a computer. See MPEP 2106.04(a)(2)(III).)
generating a plurality of partial assignments, comprising, for each of the partial assignments: selecting a respective second, proper subset of the first subset of variables; and (Abstract idea – mental process. Selecting a proper subset of a set of variables can practically be performed in the human mind or with the aid of pen and paper, for example, by mentally identifying the variables to be included in the subset. See MPEP 2106.04(a)(2)(III).)
for each of the variables in the respective second subset, generating, using at least the respective embedding for the variable, a respective additional constraint on the value of the variable; (Abstract idea – mental process. Generating additional constraints for the subset of variables can practically be performed in the human mind or with the aid of pen and paper, for example, by mentally determining that each variable in the subset must be equal to a certain value. See MPEP 2106.04(a)(2)(III).)
generating, for each of the plurality of partial assignments, a corresponding candidate final assignment that assigns a respective value to each of the plurality of variables starting from the additional constraints in the partial assignment; and (Abstract idea – mental process. Generating candidate final assignments based on the partial assignments can practically be performed in the human mind or with the aid of pen and paper, for example, by mentally assigning values to the unassigned variables of each partial assignment such that all constraints of the MIP are satisfied. See MPEP 2106.04(a)(2)(III).)
selecting, as a final assignment for the MIP, a candidate final assignment that (i) is a feasible solution to the MIP and (ii) has a smallest value of the objective of any of the candidate final assignments that are feasible solutions to the MIP. (Abstract idea – mental process. Selecting a candidate final assignment as the final assignment for the MIP can practically be performed in the human mind or with the aid of pen and paper, for example, by mentally determining which candidate final assignments satisfy all constraints and are thus feasible, mentally calculating the objective value for each feasible candidate final assignment, and mentally selecting the candidate final assignment with the smallest objective value. See MPEP 2106.04(a)(2)(III).)
Step 2A Prong 2: The additional elements recited in the claim do not integrate the abstract idea into a practical application, individually or in combination. Specifically, the claim recites the additional elements:
A method performed by one or more computers (Implementing the described method on one or more computers amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f).)
obtaining data specifying parameters of a mixed integer program (MIP) that requires assigning respective values to each of a plurality of variables to minimize an objective subject to a set of constraints, wherein a first subset of the plurality of variables are constrained to be integer-valued; (Obtaining data specifying parameters of a mixed integer program including variables, constraints, and an objective amounts to adding insignificant extra-solution activity (necessary data gathering) to the judicial exception – see MPEP2106.05(g).)
processing the input representation using an encoder neural network to generate a respective embedding for each of the variables in the first subset; (Processing input using a generic encoder neural network to generate an embedding is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f).)
Step 2B: The claim does not include additional elements that are sufficient to amount to significantly more than the judicial exception. Specifically, the claim recites the additional elements:
A method performed by one or more computers (Implementing the described method on one or more computers amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f).)
obtaining data specifying parameters of a mixed integer program (MIP) that requires assigning respective values to each of a plurality of variables to minimize an objective subject to a set of constraints, wherein a first subset of the plurality of variables are constrained to be integer-valued; (Obtaining data specifying parameters of a mixed integer program including variables, constraints, and an objective amounts to adding insignificant extra-solution activity (necessary data gathering) to the judicial exception – see MPEP2106.05(g). Further, the limitation is directed to receiving or transmitting data over a network, which the courts have found to be well-understood, routine, and conventional in the computer arts – see MPEP 2106.05(d).)
processing the input representation using an encoder neural network to generate a respective embedding for each of the variables in the first subset; (Processing input using a generic encoder neural network to generate an embedding is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f).)
Claims 2-31:
Claim 2 recites The method of claim 1, wherein the first subset is a proper subset of the plurality of variables. This limitation merely specifies that the subset of integer variables obtained in the data gathering step is a proper subset of the variables, and thus amounts to adding insignificant extra-solution activity (necessary data gathering) to the judicial exception (see MPEP2106.05(g)) which is well-understood, routine, and conventional in the computer arts (see MPEP 2106.05(d)). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 3 recites The method of claim 1, wherein generating, for each of the plurality of partial assignments, a corresponding candidate final assignment comprises generating the corresponding candidate final assignments in parallel. Generating candidate final assignments in parallel amounts to adding insignificant extra-solution activity to the judicial exception – see MPEP2106.05(g). Further, generating and solving partial assignments in parallel is well-understood, routine, and conventional in the field of mixed integer programming, per Munguía: “In the field of discrete optimization, Bader et al. [4] and Koch et al. [38] discuss potential applications of parallelism. The most widely used strategy entails exploring the branch-and-bound tree in parallel by solving multiple subproblems simultaneously. Due to its simplicity, most state-of-the-art MIP solvers incorporate this technique…” (Munguía et al., “Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs”, pg. 3, section 1.1). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 4 recites The method of claim 1, wherein the plurality of partial assignments are generated in parallel by respective neural networks which are configured to operate in parallel. Generating the partial assignments in parallel amounts to adding insignificant extra-solution activity to the judicial exception – see MPEP2106.05(g). Further, generating and solving partial assignments in parallel is well-understood, routine, and conventional in the field of mixed integer programming, as shown above in regard to claim 3. Generating the partial assignments using generic neural networks amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 5 recites The method of claim 1, wherein generating, for each of the plurality of partial assignments, a corresponding candidate final assignment comprises generating the corresponding candidate final assignment using a heuristic-based MIP solver conditioned on the parameters of the MIP and the additional constraints in the partial assignment. Generating candidate final assignments using a heuristic based MIP solver amounts to adding insignificant extra-solution activity to the judicial exception – see MPEP2106.05(g). Further, generating feasible solutions using a heuristic based solver is well-understood, routine, and conventional in the field of mixed integer programming, per Koc: “There are several other heuristics for finding feasible solutions for MILP problems that can be used as a part of a parallel implementation” (Koc, et al., “Generation of feasible integer solutions on a massively parallel computer using the feasibility pump”, pg. 653, section 1). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 6 recites The method of claim 1, wherein generating, from the parameters of the MIP, an input representation comprises: generating, from the parameters of the MIP, a representation of a bipartite graph, the bipartite graph having: (i) a plurality of nodes that include a first set of variable nodes each representing one of the plurality of variables and a second set of constraint nodes each representing one of the constraints, (iii) for each constraint node, a respective edge from the constraint node to each variable node that represents a variable that appears in the constraint represented by the constraint node, and the representation comprising: respective features for each of the plurality of nodes, and an adjacency matrix that represents connectivity between the variable nodes and the constraint nodes in the bipartite graph. Generating a bipartite graph representation of the MIP parameters can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process), for example, by drawing a bipartite graph on a sheet of paper, with nodes of the graph representing variables and constraints of the MIP and edges of the graph representing variables appearing in constraints, and writing out an adjacency matrix by hand whose entries represent the connectivity of the graph. See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 1, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 7 recites The method of claim 6, wherein: the encoder neural network is a graph neural network that is configured to process the features for each of the plurality of nodes through a sequence of one or more graph layers to generate the embeddings for the variables in the first subset; each graph layer is configured to receive as input a respective input embedding for each of the nodes in the graph and generate as output a respective output embedding for each of the nodes in the graph; the input embedding for each of the nodes in the graph for the first graph layer in the sequence includes the features for the nodes; and the embedding for each of the nodes in the first subset is the output embedding generated by the last graph layer in the sequence for the node representing the variable in the first subset. Processing node features through a generic sequence of graph neural network layers to generate output embeddings is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 8 recites The method of claim 7, wherein each graph layer is configured to: apply an update function to each of the input embeddings to generate an updated embedding; and apply the adjacency matrix to the updated embeddings to generate initial output embeddings. Applying an update function to embeddings and applying the adjacency matrix to the updated embeddings can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process), for example, by mentally calculating the result of inputting the embeddings to the update function, and mentally calculating the result of aggregating the updated embeddings between neighboring nodes according to the connectivity defined by the adjacency matrix. See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 7, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 9 recites The method of claim 8, wherein the initial output embeddings are the output embeddings for the graph layer. Designating the initial output embeddings as the output embeddings for the graph layer can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 8, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 10 recites The method of claim 8, wherein each graph layer is configured to: combine the initial output embeddings generated by the graph layer and the input embeddings for the graph layer to generate the output embeddings for the graph layer. Combining the initial output embeddings with the input embeddings can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process), for example, by mentally summing the initial output embeddings and the input embeddings to obtain the output embeddings. See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 8, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 11 recites The method of claim 8, wherein the update function is a multi-layer perceptron (MLP). Updating embeddings using a generic multi-layer perceptron model is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 12 recites The method of claim 6, wherein the adjacency matrix is an N x N matrix, wherein N is a total number of nodes in the graph, and wherein an entry (i,j) is: equal to 1 if a node with index i is connected to a node with index j by an edge; and equal to 0 if i is not equal to j and if the node with index i is not connected to the node with index j by an edge. This limitation merely specifies that the adjacency matrix generated by the mental process is of shape N x N and includes entries equal to 1 or 0 to indicate connectivity or non-connectivity between nodes. Therefore, the claim merges with the abstract idea recited in claim 6, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 13 recites The method of claim 6, wherein the adjacency matrix is an N x N matrix, wherein N is a total number of nodes in the graph, and wherein the entries in the adjacency matrix represent normalized coefficients in the constraints. This limitation merely specifies that the adjacency matrix generated by the mental process is of shape N x N and includes entries equal to the constraint coefficients. Therefore, the claim merges with the abstract idea recited in claim 6, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 14 recites The method of claim 1, wherein, for a particular partial assignment, the second subset includes a particular variable that is constrained to be a binary variable, and wherein generating the additional constraint for the binary variable comprises: generating, by processing at least the respective embedding for the binary variable using a prediction neural network head, a probability for the binary variable; sampling a value for the binary variable according to the probability; and generating an additional constraint that constrains the value of the binary variable to be equal to the sampled value. Generating a probability for a binary variable, sampling a value based on the probability, and generating a constraint based on the sampled value are evaluations that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the probability using a generic neural network head amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 1, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 15 recites The method of claim 1, wherein the first subset includes a particular variable that is constrained to be a binary variable, and wherein, for a particular partial assignment selecting the respective second, proper subset comprises: generating, by processing at least the respective embedding for the binary variable using a corresponding assignment neural network head, an assignment probability for the binary variable; and determining whether to include the binary variable in the respective second subset in accordance with the assignment probability. Generating an assignment probability for a binary variable and determining whether to include the variable in a subset based on the probability are evaluations that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the assignment probability using a generic neural network head amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 1, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 16 recites The method of claim 15, wherein different ones of the partial assignments are associated with different corresponding assignment neural network heads that have been trained to generate assignment probabilities that result in different expected coverages of the first subset. Generating assignment probabilities which result in different expected coverages for different partial assignments is an evaluation that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the assignment probabilities using generic neural network heads amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 15, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 17 recites The method of claim 1, wherein, for a particular partial assignment, the second subset includes a particular variable that is constrained to be a general integer variable that can take more than two possible values, and wherein generating the additional constraint for the general integer variable comprises: generating, by processing at least the respective embedding for the general integer variable using a prediction neural network head, a respective probability for one or more of the bits in a sequence of bits that represents a cardinality of the general integer variable; sampling a respective value for each of the one or more bits according to the probability for the bit; and generating an additional constraint that constrains the value of the general integer variable based on the sampled values. Generating probabilities for bits of an integer variable, sampling values for each bit based on the probabilities, and generating a constraint based on the sampled values are evaluations that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the probabilities using a generic neural network head amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 1, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 18 recites The method of claim 17, wherein the one or more bits include all of the bits in the sequence, wherein the sampled values define a single value for the general integer variable, and wherein the additional constraint constrains the general integer to have the single value. This limitation merely specifies that the integer bits, for which probabilities are generated, values are sampled, and constraints are generated via the mental process, include all bits in the sequence of bits representing the integer. Therefore, the claim merges with the abstract idea recited in claim 17, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 19 recites The method of claim 17, wherein the one or more bits include only a proper subset of the bits in the sequence that includes the one or more most significant bits in the sequence, wherein the sampled values define a range of values for the general integer variable, and wherein the additional constraint constrains the general integer to have a value that is in the range of values defined by the sampled values for the most significant bits. This limitation merely specifies that the integer bits, for which probabilities are generated, values are sampled, and constraints are generated via the mental process, include a subset of the bits in the sequence of bits representing the integer. Therefore, the claim merges with the abstract idea recited in claim 17, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 20 recites The method of claim 17, wherein, for the particular partial assignment selecting the respective second, proper subset comprises: generating, by processing at least the respective embedding for the general integer variable using a corresponding assignment neural network head, a respective assignment probability for each of one or more bits in the sequence of bits; and determining whether to include the general integer variable in the respective second subset in accordance with the assignment probability for the most significant bit in the sequence. Generating assignment probabilities for bits of an integer variable and determining whether to include the variable in a subset based on the probability for the most significant bit are evaluations that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the assignment probabilities using a generic neural network head amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 17, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 21 recites The method of claim 20, further comprising determining how many bits to include in the one or more bits for which values are sampled based on the respective assignment probabilities. Determining how many bits for which to sample values based on the probabilities is an evaluation that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 20, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 22 recites The method of claim 20, wherein different ones of the partial assignments are associated with different corresponding assignment neural network heads that have been trained to generate assignment probabilities that result in different expected coverages of the first subset. Generating assignment probabilities which result in different expected coverages for different partial assignments is an evaluation that can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). See MPEP 2106.04(a)(2)(III). Generating the assignment probabilities using generic neural network heads amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 20, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 23 recites The method of claim 1, wherein the encoder neural network is trained on feasible solutions to a data set of training MIPs generated by a heuristic-based MIP solver. Training a generic encoder neural network using training data is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 24 recites The method of claim 1, further comprising: generating optimality gap data defining an optimality gap proof for the final assignment. Generating optimality gap data for the final assignment can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process), for example, by mentally calculating the difference between the final assignment and an optimal solution. See MPEP 2106.04(a)(2)(III). Therefore, the claim merges with the abstract idea recited in claim 1, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 25 recites The method of claim 24, wherein generating the optimality gap data comprises: generating the optimality gap data using a branch-and-bound technique that recursively, over a plurality of steps, generates a search tree with partial integer assignments at each node of the search tree, wherein generating the search tree comprises, at each step: selecting a leaf node of the current search tree from which to branch; determining whether to expand the selected leaf node; and in response to determining to expand the selected leaf node: selecting a variable from a set of unfixed variables at the selected leaf node; and expanding the search tree by adding two child nodes to the search tree that each have a different domain for the selected variable. Generating optimality gap data using a branch-and-bound technique amounts to adding insignificant extra-solution activity to the judicial exception – see MPEP2106.05(g). Further, using the branch-and-bound method to find an optimal solution is well-understood, routine, and conventional in the field of mixed integer programming, per Gasse: “In practice, most combinatorial optimization problems can be formulated as mixed-integer linear programs (MILPs), in which case branch-and-bound (B&B) [35] is the exact method of choice” (Gasse et al., “Exact Combinatorial Optimization with Graph Convolutional Neural Networks”, pg. 1, section 1). Selecting a leaf node, determining whether to expand the leaf node, selecting an unfixed variable, and adding child nodes to the search tree are evaluations which can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). Therefore, the claim merges with the abstract idea recited in claim 24, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 26 recites The method of claim 25, wherein selecting a variable from a set of unfixed variables at the selected leaf node comprises: generating a new input representation of a sub-MIP defined by the selected leaf node; processing the new input representation using a second encoder neural network to generate a respective embedding for each of the unfixed variables; processing the respective embeddings using a branching neural network to generate a respective branching score for each of the unfixed variables; and selecting the variable using the respective branching scores. Generating an input representation of a sub-MIP, generating embeddings for the unfixed variables, generating branching scores for the unfixed variables, and selecting a variable based on the branching scores are evaluations which can practically be performed in the human mind or with the aid of pen and paper (i.e. mental process). Generating the embeddings using a generic encoder neural network and generating the branching scores using a generic neural network amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim merges with the abstract idea recited in claim 25, and does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 27 recites The method of claim 26, wherein the branching neural network has been trained through imitation learning to imitate an expert policy that generates branching decisions for the branch-and-bound technique. Training the branching neural network using imitation learning amounts to adding insignificant extra-solution activity to the judicial exception – see MPEP2106.05(g). Further, imitation learning of branching decisions for branch-and-bound is well-understood, routine, and conventional in the field of mixed integer programming, per Gasse: “First steps towards statistical learning of branching rules in B&B were taken by Khalil et al. [30], who learn a branching rule customized to a single instance during the B&B process, as well as Alvarez et al. [4] and Hansknecht et al. [24] who learn a branching rule offline on a collection of similar instances, in a fashion similar to us. In each case a branching policy is learned by imitation of the strong branching expert…” (Gasse, pg. 2, section 2). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 28 recites The method of claim 27, wherein the second encoder neural network has been trained jointly with the branching neural network. Jointly training a generic encoder neural network and a generic prediction neural network is standard in the field of machine learning, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 29 recites The method of claim 27, wherein the second encoder neural network is the same as the encoder neural network. This limitation merely specifies that the two generic encoder neural networks used to generate embeddings are the same, and thus amounts to adding the words “apply it” (or an equivalent) with the judicial exception, or mere instructions to implement an abstract idea on a computer, or merely using a computer as a tool to perform an abstract idea – see MPEP 2106.05(f). Therefore, the claim does not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 30 is a system claim containing substantially the same elements as method claim 1, and is rejected on the same grounds under 35 U.S.C. 101 as claim 1, mutatis mutandis. The additional components of A system comprising: one or more computers; and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising: are interpreted as a general-purpose computer and mere instructions to apply the judicial exception on the computer. Therefore, the claims do not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
Claim 31 is a product claim containing substantially the same elements as method claim 1, and is rejected on the same grounds under 35 U.S.C. 101 as claim 1, mutatis mutandis. The additional components of One or more computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising: are interpreted as a general-purpose computer and mere instructions to apply the judicial exception on the computer. Therefore, the claims do not recite additional elements that are sufficient to amount to significantly more than the abstract idea.
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-5, 14-15, 23-24, and 30-31 are rejected under 35 U.S.C. 103 as being unpatentable over
Ding et al. (hereinafter Ding), “Accelerating Primal Solution Findings for Mixed Integer Programs Based on Solution Prediction” (published 09/09/2019), in view of
Koc et al. (hereinafter Koc), “Generation of feasible integer solutions on a massively parallel computer using the feasibility pump” (published 10/19/2017).
Regarding Claim 1,
Ding teaches A method performed by one or more computers, the method comprising: (Pg. 5, section ‘Experimental Evaluations’: “All experiments were conducted on a cluster of three 4-core machines with Intel 2.2 GHz processors and 16 GB RAM.”)
obtaining data specifying parameters of a mixed integer program (MIP) that requires assigning respective values to each of a plurality of variables to minimize an objective subject to a set of constraints, wherein a first subset of the plurality of variables are constrained to be integer-valued; (Pg. 2, section ‘The Solution Framework’: “Consider an MIP [Mixed Integer Programming] problem instance
I
of the general form:
min
c
T
x
(1)
s.t.
A
x
≤
b
, (2)
x
j
∈
0,1
,
∀
j
∈
B
, (3)
x
j
∈
Z
,
∀
j
∈
Q
,
x
j
≥
0
,
∀
j
∈
P
,
(4)
where the index set of decision variables
U
∶
=
{
1
,
…
,
n
}
is partitioned into
(
B
,
Q
,
P
)
, and
B
,
Q
,
P
are the index set of binary, general integer and continuous variables, respectively.” The symbols above represent parameters of a mixed integer problem. Values are assigned to decision variables
U
in order to minimize the objective defined by objective function coefficients
c
, subject to the constraints defined by
A
x
≤
b
. The subset of decision variables represented by
B
are binary and thus constrained to be integer-valued.)
generating, from the parameters of the MIP, an input representation; (Pg. 3, section ‘Graph Representation for MIP’: “Our main idea is to use a tripartite graph
G
=
{
V
,
E
}
to represent an input MIP instance
I
. In particular, objective function coefficients
c
, constraint right-hand-side (RHS) coefficients
b
and coefficient matrix
A
information is extracted from
I
to build the graph… Vertices: 1) the set of decision variable vertices
V
V
, each of which corresponds to a binary variable in
I
. 2) the set of constraint vertices
V
C
, each of which corresponds to a constraint in
I
. 3) an objective function vertex
o
.” A graph (i.e. input representation) is generated based on the MIP parameters.)
processing the input representation using an encoder neural network to generate a respective embedding for each of the variables in the first subset; (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The graph (i.e. input representation) is processed using a graph neural network (i.e. an encoder neural network) to generate an embedding for each node, including the binary variable nodes (i.e. variables in the first subset).)
generating a [plurality of] partial assignments, comprising
selecting a respective second, proper subset of the first subset of variables; and (Pg. 4, section ‘Prediction-Based MIP Solving’: “Let
x
^
j
denote the predicted solution value of binary variable
x
j
,
j
∈
B
, and let
S
⊆
B
denote a subset of indices of binary variables… only those variables with high probability to take value 0 or 1 are included in
S
.”
S
is a second, proper subset of binary variables
B
(i.e. the first subset of variables).)
for each of the variables in the respective second subset, generating, using at least the respective embedding for the variable, a respective additional constraint on the value of the variable; (Pg. 4, section ‘Prediction-Based MIP Solving’: “A local branching initial cut to the model is defined… where
ϕ
is a problem parameter that controls the maximum distance from a new solution
x
to the predicted solution
x
^
. Adding cuts with respect to subset
S
rather than
B
is due to the unpredictable nature of unstable variables in MIP solutions… For the extreme case that
ϕ
equals
0
, the initial cut is equivalent to fixing variables with indices in
S
at their predicted values.” Each variable in subset
S
(i.e. in the second subset) is fixed (i.e. constrained) at its predicted value (i.e. based on its embedding).)
generating, [for each of the plurality of partial assignments], a corresponding candidate final assignment that assigns a respective value to each of the plurality of variables starting from the additional constraints in the partial assignment; and (Pg. 4, section ‘Prediction-Based MIP Solving’: “Next, we introduce how the solution value prediction results are utilized to improve MIP solving performance. One approach is to add a local branching [Fischetti and Lodi, 2003] type (invalid) global cut to the MIP model to reduce the search space of feasible solutions. This method aims to identify decision variables that are predictable and stable, and restrict the B&B [Branch and Bound] tree search on unpredictable variables to accelerate primal solution-finding.” Based on the global solution space cut (i.e. the additional constraints in the partial assignment), Branch and Bound tree search is used for MIP solution-finding (i.e. generating a candidate final assignment).)
Ding does not appear to explicitly disclose
generating a plurality of partial assignments,
generating, for each of the plurality of partial assignments, a corresponding candidate final assignment
selecting, as a final assignment for the MIP, a candidate final assignment that (i) is a feasible solution to the MIP and (ii) has a smallest value of the objective of any of the candidate final assignments that are feasible solutions to the MIP.
However, Koc teaches generating a plurality of partial assignments, (Pg. 652, section 1: “In this study we consider the problem of generating high quality feasible solutions for unstructured Mixed Integer Linear Programs (MILPs) in a parallel computational environment.” Pg. 653, section 2: “In our approach, we run multiple feasibility heuristics in parallel. We refer to the algorithms running in different processors as subroutines. Each parallel subroutine uses a different random number seed with different starting solutions.” Each subroutine’s different starting solution is a partial assignment.)
generating, for each of the plurality of partial assignments, a corresponding candidate final assignment (Pg. 653, section 2: “Whenever one of the subroutines finds a feasible solution, it broadcasts the objective function value to others via the master. Then, all subroutines continue their search with a new and better objective cut-off constraint.” The subroutines find feasible solutions (i.e. generate candidate final assignments) based on their starting solutions (i.e. partial assignments).)
selecting, as a final assignment for the MIP, a candidate final assignment that (i) is a feasible solution to the MIP and (ii) has a smallest value of the objective of any of the candidate final assignments that are feasible solutions to the MIP. (Pg. 653, section 2: “Whenever one of the subroutines finds a feasible solution, it broadcasts the objective function value to others via the master… The role of the master is distributing inputs to and collecting results from the slaves. The main algorithm that runs at the master is presented in Algorithm 2.1.” Algorithm 2.1 outputs “an integer solution to the above MILP”, where the final step, after the termination criteria are met, is to “[e]xit all the slaves and return best integer so far”. Each feasible integer solution generated by the subroutines/slaves is compared, and the best feasible solution (i.e. the candidate final assignment with the smallest objective value) is returned as the final solution assignment.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding and Koc. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. One of ordinary skill would have motivation to combine Ding and Koc because “starting FP from multiple rounded points in parallel outperforms using the same starting solution” (Koc, pg. 657, section 6).
Regarding Claim 2, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein the first subset is a proper subset of the plurality of variables. (Pg. 2, section ‘The Solution Framework’: “[T]he index set of decision variables
U
∶
=
{
1
,
…
,
n
}
is partitioned into
(
B
,
Q
,
P
)
, and
B
,
Q
,
P
are the index set of binary, general integer and continuous variables, respectively.” A mixed integer program includes a mix of both integer and continuous variables, and thus the subset of binary integer variables
B
is a proper subset of the full set of variables.)
Regarding Claim 3, Ding and Koc teach The method of claim 1, as shown above.
Koc also teaches wherein generating, for each of the plurality of partial assignments, a corresponding candidate final assignment comprises generating the corresponding candidate final assignments in parallel. (Pg. 653, section 2: “In our approach, we run multiple feasibility heuristics in parallel. We refer to the algorithms running in different processors as subroutines. Each parallel subroutine uses a different random number seed with different starting solutions… Whenever one of the subroutines finds a feasible solution, it broadcasts the objective function value to others via the master.” The subroutines find feasible solutions (i.e. generate candidate final assignments) for each starting solution (i.e. each partial assignment) in parallel.)
Regarding Claim 4, Ding and Koc teach The method of claim 1, as shown above.
Koc also teaches wherein the plurality of partial assignments are generated in parallel [by respective neural networks] which are configured to operate in parallel. (Pg. 653, section 2: “At each iteration of Algorithm 2.2, the slave subroutine receives relevant information from the master (if any), updates itself with the new information, creates a starting solution for the algorithms depending on the type of heuristic it is running and sends the integer solutions to the master, if any.” The starting solutions (i.e. partial assignments) are created by the parallel subroutines (i.e. generated in parallel).)
Ding teaches that the partial assignments are generated by neural networks (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages… 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The predicted values for the binary variables which are fixed in the partial assignment are generated by fully-connected layers (i.e. neural networks).)
Regarding Claim 5, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein generating, for each of the plurality of partial assignments, a corresponding candidate final assignment comprises generating the corresponding candidate final assignment using a heuristic-based MIP solver conditioned on the parameters of the MIP and the additional constraints in the partial assignment. (Pg. 1, Abstract: “The predicted solutions are used to generate a local branching type cut which can be either treated as a global (invalid) inequality in the formulation resulting in a heuristic approach to solve the MIP…” A heuristic approach to solve the MIP (i.e. generation of a candidate final assignment using a heuristic-based MIP solver) is conditioned on the parameters of the MIP and the global solution space cut based on the predicted solutions (i.e. the additional constraints in the partial assignment).)
Regarding Claim 14, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein, for a particular partial assignment, the second subset includes a particular variable that is constrained to be a binary variable, and (Pg. 4, section ‘Prediction-Based MIP Solving’: “Let
x
^
j
denote the predicted solution value of binary variable
x
j
,
j
∈
B
, and let
S
⊆
B
denote a subset of indices of binary variables.” Binary variable
x
j
is a particular binary variable of the subset of binary variables
S
(i.e. the second subset).)
wherein generating the additional constraint for the binary variable comprises:
generating, by processing at least the respective embedding for the binary variable using a prediction neural network head, a probability for the binary variable; (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The node embedding of a binary variable is processed by fully-connected layers and an output layer (i.e. a prediction neural network head) to output a probability for the binary variable.)
sampling a value for the binary variable according to the probability; and (Pg. 4, section ‘Prediction-Based MIP Solving’: “A local branching initial cut to the model is defined… where
ϕ
is a problem parameter that controls the maximum distance from a new solution
x
to the predicted solution
x
^
. Adding cuts with respect to subset
S
rather than
B
is due to the unpredictable nature of unstable variables in MIP solutions. Therefore, only those variables with high probability to take value 0 or 1 are included in
S
. For the extreme case that
ϕ
equals
0
, the initial cut is equivalent to fixing variables with indices in
S
at their predicted values.” For a binary variable in subset
S
, a value of 0 or 1 is sampled according to the associated probability.)
generating an additional constraint that constrains the value of the binary variable to be equal to the sampled value. (See the portion of pg. 4, section ‘Prediction-Based MIP Solving’ cited above. The binary variable is fixed (i.e. constrained) at its sampled predicted value.)
Regarding Claim 15, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein the first subset includes a particular variable that is constrained to be a binary variable, and (Pg. 4, section ‘Prediction-Based MIP Solving’: “Let
x
^
j
denote the predicted solution value of binary variable
x
j
,
j
∈
B
…” Binary variable
x
j
is a particular binary variable of the subset of binary variables
B
(i.e. the first subset).)
wherein, for a particular partial assignment selecting the respective second, proper subset comprises:
generating, by processing at least the respective embedding for the binary variable using a corresponding assignment neural network head, an assignment probability for the binary variable; and (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The node embedding of a binary variable is processed by fully-connected layers and an output layer (i.e. an assignment neural network head) to output an assignment probability for the binary variable.)
determining whether to include the binary variable in the respective second subset in accordance with the assignment probability. (Pg. 4, section ‘Prediction-Based MIP Solving’: “[L]et
S
⊆
B
denote a subset of indices of binary variables… only those variables with high probability to take value 0 or 1 are included in
S
.” The determination of whether to include a binary variable in the subset of binary variables
S
(i.e. the second subset) is made based on the assignment probability.)
Regarding Claim 23, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein the encoder neural network is trained on feasible solutions to a data set of training MIPs generated by a heuristic-based MIP solver. (Pg. 2, section ‘Introduction’: “Training data generation: For a certain type of CO problem, generate a set of
p
MIP instances
I
=
{
I
1
,
.
.
.
,
I
p
}
of similar scale from the same distribution
D
. For each
I
i
∈
I
, collect variable features, constraint features, and edge features, and use the iterated proximity search method to generate solution labels for each binary variable in
I
i
. GCN model training: For each
I
i
∈
I
, generate a tripartite graph from its MIP formulation. Train a Graph Convolutional Network (GCN) for binary variable solution prediction based on the collected features, labels and trigraphs.” The graph convolutional network (i.e. encoder) is trained on solution labels (i.e. feasible solutions) generated by iterated proximity search (i.e. a heuristic-based MIP solver) for a training data set of MIP instances.)
Regarding Claim 24, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches further comprising: generating optimality gap data defining an optimality gap proof for the final assignment. (Pg. 6, section ‘Comparisons of solution quality’: “Notice that the proposed approximate approach does not guarantee global optimality (i.e., does not provide a valid lower bound), we use the primal gap metric [Khalil et al., 2017] to capture solver’s performance on primal solution finding. In particular, the primal gap metric
y
(
x
~
)
reports the relative gap in the objective value of a feasible solution
x
~
to that of the optimal (or best-known) solution
x
~
*
…” The primal gap metric represents the gap between the feasible solution and the optimal solution (i.e. the optimality gap).)
Claim 30 is a system claim containing substantially the same elements as method claim 1. Ding and Koc teach the elements of claim 1, as shown above.
Ding also teaches A system comprising: one or more computers; and one or more storage devices storing instructions that, when executed by the one or more computers, cause the one or more computers to perform operations comprising: (Examiner notes that this limitation is interpreted as implementation of the disclosed method in a generic computing environment. Pg. 5, section ‘Experimental Evaluations’: “All experiments were conducted on a cluster of three 4-core machines with Intel 2.2 GHz processors and 16 GB RAM.”)
Claim 31 is a product claim containing substantially the same elements as method claim 1. Ding and Koc teach the elements of claim 1, as shown above.
Ding also teaches One or more computer-readable storage media storing instructions that when executed by one or more computers cause the one or more computers to perform operations comprising: (Examiner notes that this limitation is interpreted as implementation of the disclosed method in a generic computing environment. Pg. 5, section ‘Experimental Evaluations’: “All experiments were conducted on a cluster of three 4-core machines with Intel 2.2 GHz processors and 16 GB RAM.”)
Claims 6-7 and 12-13 are rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, and further in view of
Gasse et al. (hereinafter Gasse), “Exact Combinatorial Optimization with Graph Convolutional Neural Networks” (published 10/30/2019) and
Wu et al. (hereinafter Wu), “A Comprehensive Survey on Graph Neural Networks” (published 03/24/2020).
Regarding Claim 6, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein generating, from the parameters of the MIP, an input representation comprises:
generating, from the parameters of the MIP, a representation of a [bipartite] graph, (Pg. 3, section ‘Graph Representation for MIP’: “Our main idea is to use a tripartite graph
G
=
{
V
,
E
}
to represent an input MIP instance
I
.”)
the [bipartite] graph having:
(i) a plurality of nodes that include a first set of variable nodes each representing one of the plurality of variables and a second set of constraint nodes each representing one of the constraints, (Pg. 3, section ‘Graph Representation for MIP’: “Vertices: 1) the set of decision variable vertices
V
V
, each of which corresponds to a binary variable in
I
. 2) the set of constraint vertices
V
C
, each of which corresponds to a constraint in
I
.” The graph representation includes decision variable vertices
V
V
(i.e. variable nodes) and constraint vertices
V
C
(i.e. constraint nodes).)
(iii) for each constraint node, a respective edge from the constraint node to each variable node that represents a variable that appears in the constraint represented by the constraint node, and (Pg. 3, section ‘Graph Representation for MIP’: “Edges: 1)
v
-
c
edge: there exists an edge between
v
∈
V
V
and
c
∈
V
C
if the corresponding variable of
v
has a non-zero coefficient in the corresponding constraint of
c
in the MIP formulation.” If the corresponding variable of vertex
v
has a non-zero coefficient in the corresponding constraint of vertex
c
(i.e. the variable represented by
v
appears in the constrain represented by
c
), an edge exists between the vertices.)
the representation comprising:
respective features for each of the plurality of nodes, and (Pg. 2, section ‘Introduction’: “For a new MIP instance
I
from
D
, collect features, build the trigraph…” Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm).” Each node in the graph is processed by a fully-connected embedding layer, and therefore each node is associated with input features.)
Ding and Koc do not appear to explicitly disclose representing the MIP as a bipartite graph
However, Gasse teaches representing the MIP as a bipartite graph (Pg. 2, section 1: “[W]e propose to encode the branching policies into a graph convolutional neural network (GCNN), which allows us to exploit the natural bipartite graph representation of MILP problems…”)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, and Gasse. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Gasse teaches finding optimal solutions for mixed integer programs using a modification of branch-and-bound in which the MIP is represented as a bipartite graph. One of ordinary skill would have motivation to combine Ding, Koc, and Gasse because representing a mixed integer program as a bipartite graph “reduces the need for feature engineering by naturally leveraging the variable-constraint structure of MILP problems, and allows for the encoding of branching policies as a graph convolutional neural network” (Gasse, pg. 9, section 7).
Ding, Koc, and Gasse do not appear to explicitly disclose an adjacency matrix that represents connectivity between the variable nodes and the constraint nodes in the bipartite graph.
However, Wu teaches an adjacency matrix that represents connectivity between the variable nodes and the constraint nodes in the bipartite graph. (Pg. 6, section II.B: “A graph is represented as
G
=
(
V
,
E
)
, where
V
is the set of vertices or nodes (we will use nodes throughout this article), and
E
is the set of edges. Let
v
i
∈
V
to denote a node and
e
i
j
=
(
v
i
,
v
j
)
∈
E
to denote an edge pointing from
v
j
to
v
i
. The neighborhood of a node
v
is defined as
N
(
v
)
=
{
u
∈
V
|
(
v
,
u
)
∈
E
}
. The adjacency matrix
A
is a
n
×
n
matrix with
A
i
j
=
1
if
e
i
j
∈
E
and
A
i
j
=
0
if
e
i
j
∉
E
.” Adjacency matrix
A
represents connectivity between nodes in the graph.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, Gasse, and Wu. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Gasse teaches finding optimal solutions for mixed integer programs using a modification of branch-and-bound in which the MIP is represented as a bipartite graph. Wu teaches an overview of graph neural networks, including representing a graph using an adjacency matrix. One of ordinary skill would have motivation to combine Ding, Koc, Gasse, and Wu because Ding and Gasse represent mixed integer programs as graphs, and an adjacency matrix, as taught by Wu, provides an efficient way to store a graph as a 2-dimensional array.
Regarding Claim 7, Ding, Koc, Gasse, and Wu teach The method of claim 6, as shown above.
Ding also teaches the encoder neural network is a graph neural network that is configured to process the features for each of the plurality of nodes through a sequence of one or more graph layers to generate the embeddings for the variables in the first subset; (Pg. 1, Abstract: “we propose to represent an MIP instance using a tripartite graph, based on which a Graph Convolutional Network (GCN) is constructed to predict solution values for binary variables.” Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The node features are processed by a Graph Convolutional Network (GCN) (i.e. a graph neural network) to generate the embeddings for the nodes, including the binary variable nodes (i.e. the variables in the first subset).)
each graph layer is configured to receive as input a respective input embedding for each of the nodes in the graph and generate as output a respective output embedding for each of the nodes in the graph; (See the portion of pg. 3 cited above, as well as algorithm 1 on pg. 3. The input ‘Number of transition iterations
T
’ represents the number of graph layers. As can be seen in lines 4-12 of the algorithm, in each layer
t
of the
T
layers, for each node, previous hidden embedding
h
t
-
1
(i.e. an input embedding) is received and processed to generate hidden embedding
h
t
(i.e. an output embedding).)
the input embedding for each of the nodes in the graph for the first graph layer in the sequence includes the features for the nodes; and (See the portion of pg. 3 cited above, as well as algorithm 1 on pg. 3. As can be seen in lines 1-3 of the algorithm, at iteration
t
=
0
(i.e. for the first graph layer), the input embedding for each node
h
0
is based on the node’s corresponding ‘Input features’
x
.)
the embedding for each of the nodes in the first subset is the output embedding generated by the last graph layer in the sequence for the node representing the variable in the first subset. (See the portion of pg. 3 cited above, as well as algorithm 1 on pg. 3. As can be seen in line 13 of the algorithm, the final embedding for each variable node (i.e. each node in the first subset) used to determine the node’s predicted value
z
v
is the output embedding
h
v
T
generated at iteration
t
=
T
(i.e. by the last graph layer).)
Regarding Claim 12, Ding, Koc, Gasse, and Wu teach The method of claim 6, as shown above.
Wu also teaches wherein the adjacency matrix is an N x N matrix, wherein N is a total number of nodes in the graph, and (Pg. 6, section II.B: “The adjacency matrix
A
is a
n
×
n
matrix with
A
i
j
=
1
if
e
i
j
∈
E
and
A
i
j
=
0
if
e
i
j
∉
E
.” The symbol
n
represents the number of nodes in the graph (pg. 6, table 1).)
wherein an entry (i,j) is: equal to 1 if a node with index i is connected to a node with index j by an edge; and equal to 0 if i is not equal to j and if the node with index i is not connected to the node with index j by an edge. (See the portion of section II.B cited above. An entry in the adjacency matrix
A
i
j
is equal to 1 if an edge exists between nodes i and j, or equal to 0 if an edge does not exist between nodes i and j.)
Regarding Claim 13, Ding, Koc, Gasse, and Wu teach The method of claim 6, as shown above.
Wu also teaches wherein the adjacency matrix is an N x N matrix, wherein N is a total number of nodes in the graph, and (Pg. 6, section II.B: “The adjacency matrix
A
is a
n
×
n
matrix with
A
i
j
=
1
if
e
i
j
∈
E
and
A
i
j
=
0
if
e
i
j
∉
E
.” The symbol
n
represents the number of nodes in the graph (pg. 6, table 1).)
Ding teaches wherein the entries in the adjacency matrix represent normalized coefficients in the constraints. (Pg. 3, section ‘Graph Representation for MIP’: “The presented trigraph representation not only captures connections among the variables, constraints and objective functions but maintains the detailed coefficients numerics in its structure as well. In particular, non-zero entries in coefficient matrix
A
are included as features of
v
-
c
edges…” Edges between variables and constraints (i.e. entries in the adjacency matrix) are parameterized by entries in the constraint coefficient matrix
A
(i.e. coefficients in the constraints). Pg. 10, table 6, which shows a “[d]escription of variable, constraint, and edge features”, includes the edge feature “normalized edge coefficient” (i.e. the constraint coefficients are normalized).)
Claims 8-11 are rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, Gasse, and Wu, and further in view of
Gilmer et al. (hereinafter Gilmer), “Message Passing Neural Networks” (published 06/04/2020).
Regarding Claim 8, Ding, Koc, Gasse, and Wu teach The method of claim 7, as shown above.
Ding, Koc, Gasse, and Wu do not appear to explicitly disclose the additional features of claim 8.
However, Gilmer teaches wherein each graph layer is configured to:
apply an update function to each of the input embeddings to generate an updated embedding; and (Pg. 201-202, section 10.2: “The forward pass has two phases, a message passing phase and a readout phase. The message passing phase runs for
T
time steps and is defined in terms of message functions
M
t
and vertex update functions
U
t
. During the message passing phase, hidden states
h
v
t
at each node in the graph are updated based on aggregated messages
m
v
t
+
1
according to
m
v
t
+
1
=
∑
w
∈
N
v
M
t
h
v
t
,
h
w
t
,
e
v
w
(10.1)
h
v
t
+
1
=
U
t
(
h
v
t
,
m
v
t
+
1
)
(10.2)
where in the sum,
N
(
v
)
denotes the neighbors of
v
in graph
G
.” For each message passing phase (i.e. graph layer), message function
M
t
(i.e. an update function) is applied to each node’s hidden state (i.e. input embedding) to generate a message (i.e. an updated embedding).)
apply the adjacency matrix to the updated embeddings to generate initial output embeddings. (See the portion of section 10.2 cited above. For each message passing phase (i.e. graph layer), once the messages (i.e. updated embeddings) have been generated by message function
M
t
(i.e. the update function), they are aggregated by the summation operator according to graph neighbor connections (i.e. the adjacency matrix is applied) to generate aggregated messages
m
v
t
+
1
(i.e. initial output embeddings).)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, Gasse, Wu, and Gilmer. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Gasse teaches finding optimal solutions for mixed integer programs using a modification of branch-and-bound in which the MIP is represented as a bipartite graph. Wu teaches an overview of graph neural networks, including representing a graph using an adjacency matrix. Gilmer teaches a type of graph neural network called a message passing neural network (MPNN), in which node embeddings are iteratively updated and aggregated between neighbors. One of ordinary skill would have motivation to combine Ding, Koc, Gasse, Wu, and Gilmer because “MPNNs have proven to have a strong inductive bias for graph data, with applications ranging from program synthesis [11], modeling citation networks [12], reinforcement learning [13], modeling physical systems, and predicting properties of molecules [14–17]” (Gilmer, pg. 200, section 10.1).
Regarding Claim 9, Ding, Koc, Gasse, Wu, and Gilmer teach The method of claim 8, as shown above.
Ding also teaches wherein the initial output embeddings are the output embeddings for the graph layer. (Pg. 3, section ‘Solution Prediction for MIP’: “Nodes’ representations in the tripartite graph are updated via a 4-step procedure. In the first step (line 5 in Algorithm 1), the objective node
o
aggregates the representations of all variable nodes
{
h
v
,
v
∈
V
V
}
to update its representation
h
o
. The ‘CONCAT’ operation represents the CONCATENATE function that joins two arrays. In the second step (lines 6-8),
{
h
v
,
v
∈
V
V
}
and
h
o
are used to update the representations of their neighboring constraint node
c
∈
V
C
. In the third step (line 9), representations of constraints
{
h
c
,
c
∈
V
C
}
are aggregated to update
h
o
, while in the fourth step (lines 10-12),
{
h
c
,
c
∈
V
C
}
and
h
o
are combined to update
{
h
v
,
v
∈
V
V
}
.” As can be seen in lines 4-12 of the algorithm, in each graph layer
t
of the
T
layers, for each node, the updated hidden embedding
h
t
(i.e. the output embedding) is the result of graph neighborhood aggregation (i.e. the initial output embeddings).)
Regarding Claim 10, Ding, Koc, Gasse, Wu, and Gilmer teach The method of claim 8, as shown above.
Gilmer also teaches wherein each graph layer is configured to: combine the initial output embeddings generated by the graph layer and the input embeddings for the graph layer to generate the output embeddings for the graph layer. (See the portion of section 10.2 cited above in regard to claim 8. For each message passing phase (i.e. graph layer), vertex update function
U
t
combines the aggregated messages
m
v
t
+
1
(i.e. initial output embeddings) and the initial hidden state
h
v
t
(i.e. the input embeddings) to generate the updated hidden state
h
v
t
+
1
(i.e. output embeddings).)
Regarding Claim 11, Ding, Koc, Gasse, Wu, and Gilmer teach The method of claim 8, as shown above.
Gilmer also teaches wherein the update function is a multi-layer perceptron (MLP). (Pg. 202, section 10.2: “In what follows, we describe several models in the literature as they fit into the MPNN framework by specifying the specific message, update, and readout functions used…” Pg. 203-204, section 10.2.3: “Interaction Networks… The message function
M
(
h
v
,
h
w
,
e
v
w
)
is a neural network…” The message function (i.e. update function) is a neural network (i.e. multi-layer perceptron).)
Claim 16 is rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, and further in view of
Munguía et al. (hereinafter Munguía), “Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs” (published 08/08/2017).
Regarding Claim 16, Ding and Koc teach The method of claim 15, as shown above.
Ding also teaches assignment neural network heads that have been trained to generate assignment probabilities (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” Fully-connected layers and an output layer (i.e. assignment neural network heads) process the node embeddings to generate assignment probabilities.)
Ding and Koc do not appear to explicitly disclose wherein different ones of the partial assignments are associated with different corresponding assignment […] that result in different expected coverages of the first subset.
However, Munguía teaches wherein different ones of the partial assignments are associated with different corresponding assignment […] that result in different expected coverages of the first subset. (Pg. 1, Abstract: “The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary MIPs, where subsets of the variables are fixed.” Pg. 9, section 2.3: “[W]e propose a simple, yet intuitive variable fixing algorithm. It incorporates randomness, in order to satisfy the need for diversity and it allows the fixing of an adjustable number of variables.” Different sub-MIPs (i.e. partial assignments) each have diverse subsets of variables being fixed (i.e. different expected coverages of the first subset).)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, and Munguía. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the binary variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Munguía teaches efficient solution-finding for mixed integer programs by solving a plurality of smaller MIPs in parallel, each generated by fixing a different subset of variables. One of ordinary skill would have motivation to combine Ding, Koc, and Munguía in order to “leverage parallelism by generating a diversified set of large neighborhood searches, which are solved simultaneously. By exploring a large number of different search neighborhoods in parallel, we hope to increase the chances of finding solution improvements, hence speeding up the overall process” (Munguía, pg. 6, section 2.1).
Claims 17-19 are rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, and further in view of
Roy, “‘Binarize and Project’ to generate cuts for general mixed-integer programs” (published 02/07/2007).
Regarding Claim 17, Ding and Koc teach The method of claim 1, as shown above.
Ding also teaches wherein generating the additional constraint for the [general integer] variable comprises:
generating, by processing at least the respective embedding for the [general integer] variable using a prediction neural network head, a respective probability for one or more of the bits (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The node embedding of a variable is processed by fully-connected layers and an output layer (i.e. a prediction neural network head) to output a probability for the binary variable (i.e. the bit).)
sampling a respective value for each of the one or more bits according to the probability for the bit; and (Pg. 4, section ‘Prediction-Based MIP Solving’: “A local branching initial cut to the model is defined… where
ϕ
is a problem parameter that controls the maximum distance from a new solution
x
to the predicted solution
x
^
. Adding cuts with respect to subset
S
rather than
B
is due to the unpredictable nature of unstable variables in MIP solutions. Therefore, only those variables with high probability to take value 0 or 1 are included in
S
. For the extreme case that
ϕ
equals
0
, the initial cut is equivalent to fixing variables with indices in
S
at their predicted values.” For a binary variable (i.e. bit) in subset
S
, a value of 0 or 1 is sampled according to the associated probability.)
generating an additional constraint that constrains the value of the [general integer] variable based on the sampled values. (See the portion of pg. 4, section ‘Prediction-Based MIP Solving’ cited above. The variable is fixed (i.e. constrained) at its sampled predicted value.)
Ding and Koc do not appear to explicitly disclose wherein, for a particular partial assignment, the second subset includes a particular variable that is constrained to be a general integer variable that can take more than two possible values, and
one or more of the bits in a sequence of bits that represents a cardinality of the general integer variable;
However, Roy teaches wherein, for a particular partial assignment, the second subset includes a particular variable that is constrained to be a general integer variable that can take more than two possible values, and (Pg. 37, section 1: “We consider mixed-integer linear programming problems… when the integer variables
x
are not restricted to binary values but are bounded, it is possible to reformulate the problem in various ways into an equivalent problem where all integer variables, denoted
z
, are
0
-
1
constrained…” The mixed integer program includes integer variables
x
which are not restricted to binary values (i.e. can take more than two possible values) and are bounded (i.e. included in the second subset).)
one or more of the bits in a sequence of bits that represents a cardinality of the general integer variable; (Pg. 38-39, section 2: “We consider the reformulation of integer variables
x
∈
S
∩
Z
n
into binary variables
z
∈
{
0,1
}
m
,
m
∈
N
… Let
l
i
=
⌊
l
o
g
2
b
i
⌋
. We reformulate the variables
x
i
∈
{
0
,
.
.
.
,
b
i
}
using
x
i
=
∑
j
=
0
l
i
2
j
·
z
i
j
with
∀
j
∈
{
0
,
.
.
.
,
l
i
}
,
z
i
j
∈
{
0,1
}
…” The integer variable
x
i
is represented by a sequence of binary variables
z
i
(i.e. bits), with the number of binary variables equal to the base-2 logarithm of the integer variable bound
b
i
, and thus capable of representing the cardinality of the integer variable.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, and Roy. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the binary variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Roy teaches efficient solution-finding for mixed integer programs by reformulating general integer variables into sequences of binary variables. One of ordinary skill would have motivation to combine Ding, Koc, and Roy because Ding’s variable prediction method is “better being applied to binary variable intensive MIP problems due to the difficulties in solution value prediction for general integer variables” (Ding, pg. 7, section ‘Conclusions’), and Roy provides a way to reformulate general integer variables into binary variables, such that Ding’s method can be applied.
Regarding Claim 18, Ding, Koc, and Roy teach The method of claim 17, as shown above.
Ding also teaches wherein the one or more bits include all of the bits in the sequence, wherein the sampled values define a single value for the general integer variable, and wherein the additional constraint constrains the general integer to have the single value. (Pg. 4, section ‘Prediction-Based MIP Solving’: “[L]et
S
⊆
B
denote a subset of indices of binary variables… only those variables with high probability to take value 0 or 1 are included in
S
. For the extreme case that
ϕ
equals
0
, the initial cut is equivalent to fixing variables with indices in
S
at their predicted values.” The determination of whether to include a binary variable (i.e. a bit) in the subset of binary variables
S
(i.e. the one or more bits) and thus fix it is made based on the assignment probability. In the case that all bits in a sequence representing an integer are fixed, one of ordinary skill in the art will recognize that the integer is constrained to have a single value.)
Regarding Claim 19, Ding, Koc, and Roy teach The method of claim 17, as shown above.
Ding also teaches wherein the one or more bits include only a proper subset of the bits in the sequence that includes the one or more most significant bits in the sequence, wherein the sampled values define a range of values for the general integer variable, and wherein the additional constraint constrains the general integer to have a value that is in the range of values defined by the sampled values for the most significant bits. (See the portion of pg. 4, section ‘Prediction-Based MIP Solving’ cited above in regard to claim 18. The determination of whether to include a binary variable (i.e. a bit) in the subset of binary variables
S
(i.e. the one or more bits) and thus fix it is made based on the assignment probability. In the case that a proper subset including the most significant bits in a sequence representing an integer are fixed, one of ordinary skill in the art will recognize that the integer is constrained to a range of values defined by those bits.)
Claims 20-21 are rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc and Roy, and further in view of
Michel et al. (hereinafter Michel), “Constraint Satisfaction over Bit-Vectors” (published 01/2012).
Regarding Claim 20, Ding, Koc, and Roy teach The method of claim 17, as shown above.
Ding also teaches wherein, for the particular partial assignment selecting the respective second, proper subset comprises:
generating, by processing at least the respective embedding for the general integer variable using a corresponding assignment neural network head, a respective assignment probability for each of one or more bits in the sequence of bits; and (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” The node embedding of a variable is processed by fully-connected layers and an output layer (i.e. an assignment neural network head) to output an assignment probability for each binary variable (i.e. each bit in a sequence).)
determining whether to include the [general integer] variable in the respective second subset in accordance with the assignment probability [for the most significant bit in the sequence]. (Pg. 4, section ‘Prediction-Based MIP Solving’: “[L]et
S
⊆
B
denote a subset of indices of binary variables… only those variables with high probability to take value 0 or 1 are included in
S
.” The determination of whether to include a variable in the subset of variables
S
(i.e. the second subset)—and thus constrain it—is made based on the assignment probability.)
Ding, Koc, and Roy do not appear to explicitly disclose determining whether to constrain a general integer variable based on the assignment for the most significant bit in the sequence.
However, Michel teaches determining whether to constrain a general integer variable based on the assignment for the most significant bit in the sequence. (Pg. 10, section 4.4: “Given a bit-vector variable
x
and a free bit
i
in
x
, the algorithm uses two propagation rules (line 7 and line 8). If
I
(
u
x
)
-
2
i
<
L
, then bit
i
must be fixed to
1
since otherwise
x
cannot reach the lower bound. Similarly, if
I
l
x
+
2
i
>
U
, then bit
i
must be fixed to
0
since otherwise
x
would exceed the upper bound. The algorithm applies these two rules, starting with the most significant free bits. If, at some point, none of these two rules apply, subsequent, less significant, free bits do not have to be considered and the algorithm terminates early (line 9).” For a bit-vector variable (i.e. a general integer variable) the algorithm iteratively determines whether to fix (i.e. constrain) each bit, starting from the most significant bit in the sequence, and stopping when any bit is not fixed. One of ordinary skill in the art will recognize that, in the case that it is determined that the most significant bit should not be fixed, the bit-vector variable (i.e. general integer variable) will not be constrained at all. Otherwise, the variable will be constrained by at least the most significant bit.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, Roy, and Michel. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the binary variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Roy teaches efficient solution-finding for mixed integer programs by reformulating general integer variables into sequences of binary variables. Michel teaches constraining variables represented by bit-vectors by iteratively determining whether to fix the next most significant bit. One of ordinary skill would have motivation to combine Ding, Koc, Roy, and Michel because Ding’s variable prediction method is applicable to binary variables, Roy provides a way to reformulate general integer variables into binary variables such that Ding’s method can be applied, and Michel’s strategy of only constraining a bit in a bit-vector (sequence of binary variables representing an integer) when all more significant bits are fixed ensures that a partially constrained bit-vector still represents a contiguous interval of integer values that can be accurately described by upper and lower bounds.
Regarding Claim 21, Ding, Koc, Roy, and Michel teach The method of claim 20, as shown above.
Ding also teaches further comprising determining how many bits to include in the one or more bits for which values are sampled based on the respective assignment probabilities. (Pg. 4, section ‘Prediction-Based MIP Solving’: “[L]et
S
⊆
B
denote a subset of indices of binary variables… only those variables with high probability to take value 0 or 1 are included in
S
. For the extreme case that
ϕ
equals
0
, the initial cut is equivalent to fixing variables with indices in
S
at their predicted values.” The number of binary variables (i.e. bits) included in the subset
S
for which values are fixed (i.e. sampled) is determined based on the assignment probabilities.)
Claim 22 is rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, Roy, and Michel, and further in view of Munguía.
Regarding Claim 22, Ding, Koc, Roy, and Michel teach The method of claim 20, as shown above.
Ding also teaches assignment neural network heads that have been trained to generate assignment probabilities (Pg. 3, section ‘Solution Prediction for MIP’: “We describe in Algorithm 1 the overall forward propagation prediction procedure based on the trigraph. The procedure consists of three stages: 1) a fully-connected ‘EMBEDDING’ layer with 64 dimension output for each node so that the node representations are of the same dimension (lines 1-3 in the algorithm). 2) a graph attention network to transform node information among connected nodes (lines 4-12). 3) two fully-connected layers between variable nodes and the output layer (line 13). The sigmoid activation function is used for output so that the output value can be regarded as the probability that the corresponding binary variable takes value 1 in the MIP solution.” Fully-connected layers and an output layer (i.e. assignment neural network heads) process the node embeddings to generate assignment probabilities.)
Ding, Koc, Roy, and Michel do not appear to explicitly disclose wherein different ones of the partial assignments are associated with different corresponding assignment […] that result in different expected coverages of the first subset.
However, Munguía teaches wherein different ones of the partial assignments are associated with different corresponding assignment […] that result in different expected coverages of the first subset. (Pg. 1, Abstract: “The approach simultaneously solves a large number of sub-MIPs with the dual objective of reducing infeasibility and optimizing with respect to the original objective. Both goals are achieved by solving restricted versions of two auxiliary MIPs, where subsets of the variables are fixed.” Pg. 9, section 2.3: “[W]e propose a simple, yet intuitive variable fixing algorithm. It incorporates randomness, in order to satisfy the need for diversity and it allows the fixing of an adjustable number of variables.” Different sub-MIPs (i.e. partial assignments) each have diverse subsets of variables being fixed (i.e. different expected coverages of the first subset).)
Claims 25-29 are rejected under 35 U.S.C. 103 as being unpatentable over Ding in view of Koc, and further in view of Gasse.
Regarding Claim 25, Ding and Koc teach The method of claim 24, as shown above.
Ding and Koc do not appear to explicitly disclose the additional features of claim 25.
However, Gasse teaches wherein generating the optimality gap data comprises:
generating the optimality gap data using a branch-and-bound technique that recursively, over a plurality of steps, generates a search tree with partial integer assignments at each node of the search tree, (Pg. 1-2, section 1: “In practice, most combinatorial optimization problems can be formulated as mixed-integer linear programs (MILPs), in which case branch-and-bound (B&B) [35] is the exact method of choice. Branch-and-bound recursively partitions the solution space into a search tree, and computes relaxation bounds along the way to prune subtrees that provably cannot contain an optimal solution.” Branch-and-bound is an exact method for optimally solving mixed integer programs that recursively partitions the solution space into a search tree of partial assignments.)
wherein generating the search tree comprises, at each step:
selecting a leaf node of the current search tree from which to branch; (Pg. 2, section 1: “This iterative process requires sequential decision-making, such as node selection: selecting the next node to evaluate…”)
determining whether to expand the selected leaf node; and (Based on pg. 21-22 of the specification of the instant application, determining whether to expand a leaf node involves computing an objective lower bound based on an LP relaxation to identify whether the leaf node’s expanded subtree could possibly contain an optimal solution. Gasse, pg. 1-2, section 1: “Branch-and-bound… computes relaxation bounds along the way to prune subtrees that provably cannot contain an optimal solution.” Pruning or not pruning a subtree based on whether it could contain an optimal solution amounts to determining whether to expand the leaf node which, if expanded, would be the root of that subtree.)
in response to determining to expand the selected leaf node:
selecting a variable from a set of unfixed variables at the selected leaf node; and (Pg. 2, section 1: “This iterative process requires sequential decision-making, such as… variable selection: selecting the variable by which to partition the node’s search space [41].”)
expanding the search tree by adding two child nodes to the search tree that each have a different domain for the selected variable. (Pg. 3, section 3.1: “If a solution to the LP relaxation respects the original integrality constraint, then it is also a solution to (1). If not, then one may decompose the LP relaxation into two sub-problems, by splitting the feasible region according to a variable that does not respect integrality in the current LP solution
x
*
… In practice, the two sub-problems will only differ from the parent LP in the variable bounds for
x
i
… The branch-and-bound algorithm [52, Ch. II.4], in its simplest formulation, repeatedly performs this binary decomposition, giving rise to a search tree.” The search tree is expanded through binary decomposition (i.e. adding two child nodes) which differ in the bounds (i.e. domain) for the selected variable.)
It would have been obvious to one of ordinary skill in the art before the effective filing date of the present application to combine Ding, Koc, and Gasse. Ding teaches efficient solution-finding for mixed integer programs by representing the MIP parameters as a graph, predicting variable values using a graph neural network, fixing a subset of the variables at their predicted values, and then solving the resulting smaller MIP. Koc teaches efficient solution-finding for mixed integer programs by generating multiple starting assignments, running multiple Feasibility Pump (FP) solvers in parallel to identify feasible solutions, and then selecting the best feasible solution based on the objective function. Gasse teaches finding optimal solutions for mixed integer programs using a modification of branch-and-bound in which variable selection is performed by a graph neural network trained using imitation learning. One of ordinary skill would have motivation to combine Ding, Koc, and Gasse because Ding seeks to evaluate the objective value gap between found feasible MIP solutions and the optimal MIP solution (Ding, pg. 6, section ‘Comparisons of solution quality’), and Gasse provides a mechanism for efficiently identifying the optimal MIP solution, which “outperform[s] previously proposed machine learning approaches for branching, and could also outperform the default branching strategy of SCIP, a modern open-source solver” (Gasse, pg. 9, section 7).
Regarding Claim 26, Ding, Koc, and Gasse teach The method of claim 25, as shown above.
Gasse also teaches wherein selecting a variable from a set of unfixed variables at the selected leaf node comprises:
generating a new input representation of a sub-MIP defined by the selected leaf node; (Pg. 5, section 4.2: “We encode the state
s
t
of the B&B process at time
t
as a bipartite graph with node and edge features
(
G
,
C
,
E
,
V
)
, described in Figure 2 (Left).” The branch-and-bound process at time
t
(i.e. the sub-MIP defined by the currently selected leaf node) is represented as a bipartite graph (i.e. a new input representation).)
processing the new input representation using a second encoder neural network to generate a respective embedding for each of the unfixed variables; (Pg. 5-6, section 4.3: “Our model takes as input our bipartite state representation
s
t
=
(
G
,
C
,
V
,
E
)
and performs a single graph convolution… Following this graph-convolution layer, we obtain a bipartite graph with the same topology as the input, but with potentially different node features, so that each node now contains information from its neighbors.” The bipartite graph representation (i.e. new input representation) is processed by a graph neural network (i.e. a second encoder neural network) to generate new features for each node (i.e. an embedding for each variable).)
processing the respective embeddings using a branching neural network to generate a respective branching score for each of the unfixed variables; and (Pg. 6, section 4.3: “We obtain our policy by discarding the constraint nodes and applying a final 2-layer perceptron on variable nodes, combined with a masked softmax activation to produce a probability distribution over the candidate branching variables (i.e., the non-fixed LP variables).” The updated variable nodes (i.e. embeddings) are processed using a 2-layer perceptron and softmax activation (i.e. a branching neural network) to generate a probability distribution (i.e. branching scores) over the unfixed candidate branching variable.)
selecting the variable using the respective branching scores. (Pg. 4, section 3.3: “The brancher then selects a variable
a
t
among all fractional variables
A
(
s
t
)
⊆
{
1
,
.
.
.
,
p
}
at the currently focused node, according to a policy
π
(
a
t
|
s
t
)
.” The variable is selected according to the policy, which is defined by the probability distribution (i.e. branching scores) over the candidate branching variables.)
Regarding Claim 27, Ding, Koc, and Gasse teach The method of claim 26, as shown above.
Gasse also teaches wherein the branching neural network has been trained through imitation learning to imitate an expert policy that generates branching decisions for the branch-and-bound technique. (Pg. 2, section 1: “More precisely, we focus on variable selection, also known as the branching problem, which lies at the core of the B&B paradigm yet is still not well theoretically understood [41], and adopt an imitation learning strategy to learn a fast approximation of strong branching, a high-quality but expensive branching rule.” The branching neural network is trained using imitation learning to approximate strong branching (i.e. an expert policy that generates branching decisions).)
Regarding Claim 28, Ding, Koc, and Gasse teach The method of claim 27, as shown above.
Gasse also teaches wherein the second encoder neural network has been trained jointly with the branching neural network. (Pg. 5, section 4.1: “Imitation learning: We train by behavioral cloning [45] using the strong branching rule, which suffers a high computational cost but usually produces the smallest B&B trees, as mentioned in Section 3.2. We first run the expert on a collection of training instances of interest, record a dataset of expert state-action pairs
D
=
{
(
s
i
,
a
i
*
)
}
i
=
1
N
, and then learn our policy by minimizing the cross-entropy loss…” Pg. 5-6, section 4.3: “Our model takes as input our bipartite state representation
s
t
=
(
G
,
C
,
V
,
E
)
and performs a single graph convolution, in the form of two interleaved half-convolutions. In detail, because of the bipartite structure of the input graph, our graph convolution can be broken down into two successive passes… where
f
C
,
f
V
,
g
C
, and
g
V
are 2-layer perceptrons with relu activation functions. Following this graph-convolution layer… We obtain our policy by discarding the constraint nodes and applying a final 2-layer perceptron on variable nodes, combined with a masked softmax activation to produce a probability distribution over the candidate branching variables (i.e., the non-fixed LP variables).” The graph convolutional neural network includes both the convolution layers (i.e. the second encoder neural network) and the final perceptron layers (i.e. the branching neural network), and thus training the GCNN amounts to jointly training the encoder and branching neural network.)
Regarding Claim 29, Ding, Koc, and Gasse teach The method of claim 27, as shown above.
Gasse also teaches wherein the second encoder neural network is the same as the encoder neural network. (Ding teaches that the first encoder neural network is a graph convolutional neural network: “[W]e propose to represent an MIP instance using a tripartite graph, based on which a Graph Convolutional Network (GCN) is constructed to predict solution values for binary variables” (Ding, pg. 1, Abstract). Gasse teaches that the second encoder neural network is a graph convolutional neural network: “[W]e propose to encode the branching policies into a graph convolutional neural network (GCNN), which allows us to exploit the natural bipartite graph representation of MILP problems…” (Gasse, pg. 2, section 1). Both Ding and Gasse teach encoding the MIP using a graph convolutional neural network, and thus it would be obvious to one of ordinary skill in the art to use the same graph convolutional neural network encoder as both the first and second encoder.)
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to BENJAMIN M ROHD whose telephone number is (571)272-6445. The examiner can normally be reached Mon-Thurs 8:00-6:00 EST.
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, Viker Lamardo can be reached at (571) 270-5871. 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.
/B.M.R./Examiner, Art Unit 2147
/VIKER A LAMARDO/Supervisory Patent Examiner, Art Unit 2147
Prosecution Insights