A Comparison of Real-World Linear Programs and Their Randomly Generated Analogs

The intent of the study is to determine the ability of randomly-generated problems to simulate real-world problems for the purposes of testing, benchmarking and comparing software implementations of solution algorithms, and to determine if the “degree of randomness” is related to the difficulty in obtaining a solution. Randomly-generated analogs are defined to be problems created with some of the characteristics of a real-world (actual application) problem, but containing data with random elements. These analogs fall into classes that can be characterized by “nearness” to the real-world problem. The first class is obtained by randomly perturbing the problem data. The second class is obtained by randomizing the ones in the Boolean image of the problem data. The third class consists of problems obtained from software generator that accepts the problem characteristics as input. The random elements are generated from uniform and normal distributions.The measures of difficulty include central processor time, iterations and bumps in the optimal basis. Several optimizers are used in the study. In general, the results show that the difficulty increases with the “degree of randomness” and difficulty difference increases as a function of size.