Characterizing distributions of discrete bivariate random variables for simulation and evaluation of solution methods

Results are presented from empirical evaluations of the performance of solution procedures on random binary knapsack and weighted set covering problems in which correlation is induced between the objective function and constraint coefficients. The performance of the solution procedures degrades as the correlation induced among the test problem parameters is increased, and test problems with structured dependence should be used for many empirical evaluations of solution methods. Since structured dependence in discrete optimization test problems is desirable, ways to characterize the joint distribution of a discrete bivariate random variable for any feasible correlation are needed. The problem of finding a characterization with the maximum value of the smallest probability for any possible point is formulated as a linear program. An efficient algorithm based on the northwest corner rule and a simple probability reallocation scheme are presented