Method for benchmarking combinatorial problems and their solutions

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.

Dependencies are inferred from the claim text.