Measuring the Quality of Approximate Solutions to Zero-One Programming Problems

We point out the difficulties associated with measuring the quality of an approximate (heuristic) solution by “Percentage-Error” as is customary. We define a set of properties that are to be expected from a proper measure of solution quality and investigate the family of functions which satisfy those conditions. In particular, we show that for any class of 0–1 programming problems appropriate functions do exist and that they are uniquely defined up to monotone transformations. We conclude with several examples of linear functions which are suitable for certain classes of problems.