# US 11,308,400 B2 · Optimally stopped optimization systems having heuristic optimizer and methods using the same > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 11,308,400 B2 - Document ID: US11308400B2 - Status: Granted - Kind: B2 - Application number: 16/105,840 - Filed: 2018-08-20 - Published: 2019-03-28 - Granted: 2022-04-19 - Earliest claimed: 2017-08-18 - Assignees: University of Southern California - Applicants: University of Southern California - Inventors: Daniel A. Lidar; Walter Vinci - Web page: https://patentgrep.com/patent/US11308400B2 ## CPC - G06N 5/01: Dynamic search techniques; Heuristics; Dynamic trees; Branch-and-bound - G06F 17/11: for solving equations {, e.g. nonlinear equations, general mathematical optimization problems (optimization specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06F 17/18: for evaluating statistical data {, e.g. average values, frequency distributions, probability functions, regression analysis (forecasting specially adapted for a specific administrative, business or logistic context G06Q10/04)} - G06N 7/01: Probabilistic graphical models, e.g. probabilistic networks - G06N 20/00: Machine learning - G06N 20/10: using kernel methods, e.g. support vector machines [SVM] - G06N: COMPUTING ARRANGEMENTS BASED ON SPECIFIC COMPUTATIONAL MODELS - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract An optimally stopped heuristic optimizer includes a processor. The processor heuristically generates a sequence of proposed solutions for solving a discrete optimization problem associated with an objective function, and for each additional proposed solution of the sequence, derives an estimate of a quality distribution that is based on the sequence including the additional proposed solution. The quality distribution assigns a probability to each of the proposed solutions according to quality of the proposed solution. The processor further, responsive to a most recent additional proposed solution of the sequence having quality better than a quality threshold that is defined by the estimate corresponding to the sequence including the most recent additional proposed solution, commands a stop such that further proposed solutions to the discrete optimization problem are no longer generated, and identifies and outputs a selected one of the sequence having best quality. ## Claims ### Claim 1 An optimally stopped heuristic optimizer comprising: a processor programmed to heuristically generate a sequence of proposed solutions for solving a discrete optimization problem associated with an objective function, for each additional proposed solution of the sequence, derive an estimate of a quality distribution that is based on the sequence including the additional proposed solution, and that assigns a probability to each of the proposed solutions according to quality of the proposed solution, and responsive to a most recent additional proposed solution of the sequence having quality better than a quality threshold that is defined by the estimate corresponding to the sequence including the most recent additional proposed solution, command a stop of computing resources of the processor such that further proposed solutions to the discrete optimization problem are no longer generated by the computing resources, and identify and output a selected one of the sequence having best quality, wherein the quality of the most recent additional proposed solution is an energy of the most recent additional proposed solution, and the quality threshold is an energy threshold. ### Claim 2 (depends on 1) The optimizer of claim 1, wherein a quality better than the quality threshold is an energy less than the energy threshold. ### Claim 3 (depends on 1) The optimizer of claim 1, wherein the most recent additional proposed solution of the sequence is the selected one. ### Claim 4 (depends on 1) The optimizer of claim 1, wherein the processor is further programmed to derive the estimate via maximum likelihood estimation. ### Claim 5 (depends on 1) The optimizer of claim 1, wherein the processor is further programmed to derive the estimate via Bayesian estimation. ### Claim 6 (depends on 1) The optimizer of claim 1, wherein the processor is further programmed to derive the estimate via generalized Pareto distributions. ### Claim 7 A method optimally stopping a heuristic optimizer, comprising: by a processor, heuristically generating a sequence of proposed solutions for solving a discrete optimization problem associated with an objective function, for each additional proposed solution of the sequence, deriving an estimate of a quality distribution that is based on the sequence including the additional proposed solution, and that assigns a probability to each of the proposed solutions according to quality of the proposed solution, and responsive to a most recent additional proposed solution of the sequence having quality better than a quality threshold that is defined by the estimate corresponding to the sequence including the most recent additional proposed solution, commanding a stop of computing resources of the processor such that further proposed solutions to the discrete optimization problem are no longer generated by the computing resources, and identifying and outputting a selected one of the sequence having best quality, wherein the quality of the most recent additional proposed solution is an energy of the most recent additional proposed solution, and the quality threshold is an energy threshold. ### Claim 8 (depends on 7) The method of claim 7, wherein a quality better than the quality threshold is an energy less than the energy threshold. ### Claim 9 (depends on 7) The method of claim 7, wherein the most recent additional proposed solution of the sequence is the selected one. ### Claim 10 (depends on 7) The method of claim 7 further comprising deriving the estimate via maximum likelihood estimation. ### Claim 11 (depends on 7) The method of claim 7 further comprising deriving the estimate via Bayesian estimation. ### Claim 12 (depends on 7) The method of claim 7 further comprising deriving the estimate via generalized Pareto distributions.