Obtaining minimum-correlation Latin hypercube sampling plans using an IP-based heuristic.

*(English)*Zbl 0840.62060Summary: The objective of Latin Hypercube Sampling is to determine an effective procedure for sampling from a (possibly correlated) univariate population to estimate the distribution function (or at least a significant number of moments) of a complicated function of its variables. The typical application involves a computer-based model in which it is largely impossible to find a way (closed form or numerical) to do the necessary transformations of variables and where it is expensive to run in terms of computing resources and time. Classical approaches to hypercube sampling have used sophisticated stratified sampling techniques; but such sampling may provide incorrect measures of the output parameters’ variances or covariances due to correlation between the sampling pairs.

We offer a strategy which provides a sampling specification minimizing the sum of the absolute values of the pairwise differences between the true and sampled correlation pairs. We show that optimal plans can be obtained for even small sample sizes. We consider the characteristics of permutation matrices which minimize the sum of correlations between column pairs and then present an effective heuristic for solution. This heuristic generally finds plans which match the correlation structure exactly. When it does not, we provide a hybrid lagrangian/heuristic method, which empirically has found the optimal solution for all cases tested.

We offer a strategy which provides a sampling specification minimizing the sum of the absolute values of the pairwise differences between the true and sampled correlation pairs. We show that optimal plans can be obtained for even small sample sizes. We consider the characteristics of permutation matrices which minimize the sum of correlations between column pairs and then present an effective heuristic for solution. This heuristic generally finds plans which match the correlation structure exactly. When it does not, we provide a hybrid lagrangian/heuristic method, which empirically has found the optimal solution for all cases tested.

##### MSC:

62H99 | Multivariate analysis |

62D05 | Sampling theory, sample surveys |

90C90 | Applications of mathematical programming |

90C10 | Integer programming |

90C06 | Large-scale problems in mathematical programming |

##### Keywords:

assignment problem; distribution sampling; estimation; optimization; sensitivity analysis; Latin hypercube sampling; univariate population; computer-based model; permutation matrices; sum of correlations
PDF
BibTeX
XML
Cite

\textit{C. M. Harris} et al., OR Spektrum 17, No. 2--3, 139--148 (1995; Zbl 0840.62060)

Full Text:
DOI

##### References:

[1] | Chapman R, Yakowitz H (1984) Evaluating the Risks of Solid Waste Management Programs: A Suggested Approach. Resourc Conservation 11: 77–94 · doi:10.1016/0166-3097(84)90013-0 |

[2] | Cheng RCH, Davenport T (1989) The Problem of Dimensionality in Stratified Sampling. Manag Sci 35: 1278–1296 · Zbl 0681.62020 · doi:10.1287/mnsc.35.11.1278 |

[3] | Harris CM (1983) Oil and Gas Supply Modeling under Uncertainty: Putting DOE Midterm Forecasts in Perspective. Energy J 4: 53–65 |

[4] | Harris CM (1984a) Issues in Sensitivity and Statistical Analysis of Large-Scale Computer-Based Models. Technical Report NBS-GCR-84-466, National Bureau of Standards, U.S. Department of Commerce, Gaithersburg, MD 20899 |

[5] | Harris CM (1984b) Computer Generation of Latin Hypercube Sampling Plans. Technical Report NBS-GCR-84-476, National Bureau of Standards, U.S. Department of Commerce, Gaithersburg, MD 20899 |

[6] | Harris CM (1985) Critical Issues in Implementing Latin Hypercube Sensitivity Sampling Plans. Technical Report UVA/529475/SE86/101, Department of Systems Engineering, University of Virginia, Charlottesville, VA 22901 |

[7] | Hoffman KL, Padberg MW (1989) Techniques for Improving the Representation of Zero-One Linear Programming Problems. Technical Report, Department of Operations Research and Applied Statistics, George Mason University, Fairfax, VA 22030 |

[8] | Iman RL, Conover WJ (1980) Small Sample Sensitivity Analysis Techniques for Computer Models, with an Application to Risk Assessment. Commun Statist-Theor Meth A9: 1749–1842 · Zbl 0449.68059 · doi:10.1080/03610928008827996 |

[9] | Iman RL, Conover WJ (1982) A Distribution-Free Approach to Inducing Correlation Among Input Variables. Commun Statist-Simula Computa 11: 311–334 · Zbl 0496.65071 · doi:10.1080/03610918208812265 |

[10] | Iman RL, Shortencarier MJ (1984) A FORTRAN 77 Program and User’s Guide for the Generation of Latin Hypercube and Random Samples for Use with Computer Models. Technical Report SAND83-2365, Sandia National Laboratories, Albuquerque, NM 87185 |

[11] | McKay MD, Conover WJ, Beckman RJ (1979) A Comparison of the Three Methods for Selecting Values of Input Variables in the Analysis of Output from a Computer Code. Technometrics 21: 239–245 · Zbl 0415.62011 · doi:10.2307/1268522 |

[12] | Owen AB (1994) Controlling Correlations in Latin Hypercube Samples. Amer Statist Assoc 89: 1517–1522 · Zbl 0813.65060 · doi:10.2307/2291014 |

[13] | Padberg MW, Rinaldi G (1990) A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems. Math Program Ser A 47: 219–257 · Zbl 0706.90050 · doi:10.1007/BF01580861 |

[14] | Stein M (1987) Large Sample Properties of Simulations Using Latin Hypercube Sampling. Technometrics 29: 143–151 · Zbl 0627.62010 · doi:10.2307/1269769 |

This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.