# US 8,543,524 B1 · Method for benchmarking combinatorial problems and their solutions > Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt - Number: US 8,543,524 B1 - Document ID: US8543524B1 - Status: Granted - Kind: B1 - Application number: 13/110,663 - Filed: 2011-05-18 - Granted: 2013-09-24 - Earliest claimed: 2011-05-18 - Assignees: The Boeing Company - Applicants: Barry Ross Fox; Steven James Jowers - Inventors: Barry Ross Fox; Steven James Jowers - Web page: https://patentgrep.com/patent/US8543524B1 ## CPC - G06Q 10/04: Forecasting or optimisation specially adapted for administrative or management purposes, e.g. linear programming or "cutting stock problem" (market predictions or forecasting for commercial activities G06Q30/0202) - 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)} - G06Q: INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES; SYSTEMS OR METHODS SPECIALLY ADAPTED FOR ADMINISTRATIVE, COMMERCIAL, FINANCIAL, MANAGERIAL OR SUPERVISORY PURPOSES, NOT OTHERWISE PROVIDED FOR - G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N) ## Abstract Methods of benchmarking the problem solution space of a trial scenario for a combinatorial solver, as well as the characteristic performance of a combinatorial solver operating upon the trial scenario. Given a set of predetermined trial scenario data, the generalized method includes the steps of: (a) obtaining a random sequence; (b) reordering the predetermined trial scenario data into a randomized input form according to the random sequence; (c) inputting the randomized input form into a combinatorial solver; (d) solving the randomized input form with the combinatorial solver to produce a solution; (e) evaluating the solution to measure the value of a criterion of solution quality; and (f) recording the measured value of the criterion of solution quality in a data storage structure. The steps are repeated for a predetermined number of trials, whereupon the statistical distribution of the measured values is analyzed in order to determine at least one parameter of a statistical distribution function. The resulting parameters can be used to evaluate performance, to compare performance, and to estimate the computational effort to be invested in obtaining solutions exceeding a measurable criterion of quality. ## Claims ### Claim 1 A method of benchmarking the problem solution space of a trial scenario for a combinatorial solver, the trial scenario including predetermined trial scenario data, and the method including the steps of: a. obtaining a random sequence; b. reordering the predetermined trial scenario data into a randomized input form according to the random sequence; c. inputting the randomized input form into an unbiased combinatorial solver; d. solving the randomized input form with the unbiased combinatorial solver to produce a solution; e. evaluating the solution to measure the value of a criterion of solution quality; f. recording the measured value of the criterion of solution quality in a data storage structure; g. repeating the obtaining, reordering, inputting, solving, evaluating, and recording steps for a predetermined number of trials representing a subset of the problem solution space having statistical power; and h. analyzing a statistical distribution of the measured values in the data storage structure and determining at least one parameter of a statistical distribution function. ### Claim 2 (depends on 1) The method of claim 1, wherein the statistical distribution function is a Gaussian distribution. ### Claim 3 (depends on 2) The method of claim 2, wherein the at least one parameter includes the mean μ and standard deviation σ of the Gaussian distribution. ### Claim 4 (depends on 1) The method of claim 1, wherein the measured values in the data storage structure are evaluated to verify that a problem solution space of the trial scenario may be approximately described by a selected statistical distribution function. ### Claim 5 (depends on 1) The method of claim 1, wherein the measured values in the data storage structure are plotted as a histogram for comparison with the selected statistical distribution function. ### Claim 6 (depends on 1) The method of claim 1, wherein the measured values in the data storage structure are subjected to a mathematical analysis to check whether there is a significant deviation from a selected statistical distribution function. ### Claim 7 (depends on 6) The method of claim 6, wherein the measured values in the data storage structure are subjected to an Anderson-Darling test versus the selected statistical distribution function. ### Claim 8 (depends on 7) The method of claim 7 wherein the selected statistical distribution function is the Gaussian cumulative probability distribution function. ### Claim 9 (depends on 1) The method of claim 1, further comprising the step of communicating at least the at least one parameter of the statistical distribution function to a third party. ### Claim 10 A method of benchmarking the characteristic performance of a combinatorial solver operating upon predetermined trial scenario data, the method including the steps of: a. obtaining a random sequence; b. reordering the predetermined trial scenario data into a randomized input form according to the random sequence; c. inputting the randomized input form into the combinatorial solver; d. solving the randomized input form with the combinatorial solver to produce a solution; e. evaluating the solution to measure the value of a criterion of solution quality; f. recording the measured value of the criterion of solution quality in a data storage structure; g. repeating the obtaining, reordering, inputting, solving, evaluating, and recording steps for a predetermined number of trials representing a subset of the problem solution space having statistical power; and h. analyzing a statistical distribution of the measured values in the table and determining at least one parameter of a statistical distribution function. ### Claim 11 (depends on 10) The method of claim 10, wherein the statistical distribution function is a Gaussian distribution. ### Claim 12 (depends on 11) The method of claim 11, wherein the at least one parameter includes the mean μ and standard deviation σ of the Gaussian distribution. ### Claim 13 (depends on 10) The method of claim 10, wherein the measured values in the data storage structure are evaluated to verify that a problem solution space of the trial scenario may be approximately described by a selected statistical distribution function. ### Claim 14 (depends on 10) The method of claim 10, wherein the measured values in the data storage structure are plotted as a histogram for comparison with the selected statistical distribution function. ### Claim 15 (depends on 10) The method of claim 10 wherein the measured values in the data storage structure are subjected to a mathematical analysis to check whether there is a significant deviation from a selected statistical distribution function. ### Claim 16 (depends on 15) The method of claim 15, wherein the measured values in the data storage structure are subjected to an Anderson-Darling test versus the selected statistical distribution function. ### Claim 17 (depends on 16) The method of claim 16 wherein the selected statistical distribution function is the Gaussian cumulative probability distribution function. ### Claim 18 (depends on 10) The method of claim 10, further comprising the step of communicating at least the at least one parameter of a statistical distribution function to a third party. ### Claim 19 (depends on 10) The method of claim 10, further comprising the step of applying the at least one parameter of the statistical distribution function to estimate the minimum value of the criterion of solution quality to be found by solving the randomized input form with the combinatorial solver for a second predetermined number of trials. ### Claim 20 (depends on 10) The method of claim 10, further comprising the step of applying the at least one parameter of the statistical distribution function to estimate a second predetermined number of trials over which to solve the randomized input form with the combinatorial solver in order to find a solution having a minimum value of the criterion of solution quality of about a predetermined threshold value.