Using integer programming techniques for the solution of an experimental design problem

Latin hypercube sampling is often used to estimate the distribution function of a complicated function of many random variables. In so doing, it is typically necessary to choose a permutation matrix which minimizes the correlation among the cells in the hypercube layout. This problem can be formulated as a generalized, multi-dimensional assignment problem. For the two-dimensional case, we provide a polynomial algorithm. For higher dimensions, we offer effective heuristic and bounding procedures.Supported in part by a grant from the National Institute of Standards and Technology (60NANB9D-0974).Supported in part by grants from the Office of Naval Research (N00014-90-J-1324) and the Air Force Office of Scientific Research (F49 620-90-C-0022).Research partially performed while visiting the Department of Mathematics, Brunel University, Uxbridge, England.