公开(公告)号：US11842279B2

公开(公告)日：2023-12-12

申请号：US16945625

申请日：2020-07-31

Applicant: QUALCOMM Technologies, Inc.

Inventor： Changyong Oh ,  Efstratios Gavves ,  Jakub Mikolaj Tomczak ,  Max Welling

IPC: G06N3/082 ,  G06F18/20 ,  G06F18/10 ,  G06F18/21 ,  G06N7/01

CPC classification number: G06N3/082 ,  G06F18/10 ,  G06F18/217 ,  G06F18/29 ,  G06N7/01

Abstract: Certain aspects provide a method for determining a solution to a combinatorial optimization problem, including: determining a plurality of subgraphs, wherein each subgraph of the plurality of subgraphs corresponds to a combinatorial variable of the plurality of combinatorial variables; determining a combinatorial graph based on the plurality of subgraphs; determining evaluation data comprising a set of vertices in the combinatorial graph and evaluations on the set of vertices; fitting a Gaussian process to the evaluation data; determining an acquisition function for vertices in the combinatorial graph using a predictive mean and a predictive variance from the fitted Gaussian process; optimizing the acquisition function on the combinatorial graph to determine a next vertex to evaluate; evaluating the next vertex; updating the evaluation data with a tuple of the next vertex and its evaluation; and determining a solution to the problem, wherein the solution comprises a vertex of the combinatorial graph.