Bounds for maximin Latin hypercube designs

Research output: Contribution to journalArticleScientificpeer-review

293 Downloads (Pure)

Abstract

Latin hypercube designs (LHDs) play an important role when approximating computer simulation models. To obtain good space-filling properties, the maximin criterion is frequently used. Unfortunately, constructing maximin LHDs can be quite time consuming when the number of dimensions and design points increase. In these cases, we can use heuristical maximin LHDs. In this paper, we construct bounds for the separation distance of certain classes of maximin LHDs. These bounds are useful for assessing the quality of heuristical maximin LHDs. Until now only upper bounds are known for the separation distance of certain classes of unrestricted maximin designs, i.e., for maximin designs without a Latin hypercube structure. The separation distance of maximin LHDs also satisfies these “unrestricted” bounds. By using some of the special properties of LHDs, we are able to find new and tighter bounds for maximin LHDs. Within the different methods used to determine the upper bounds, a variety of combinatorial optimization techniques are employed. Mixed-integer programming, the traveling salesman problem, and the graph-covering problem are among the formulations used to obtain the bounds. Besides these bounds, also a construction method is described for generating LHDs that meet Baer’s bound for the distance measure for certain values of n.
Original languageEnglish
Pages (from-to)595-608
JournalOperations Research
Volume57
Issue number3
Publication statusPublished - 2009

Fingerprint

Maximin
Traveling salesman problem
Combinatorial optimization
Integer programming
Computer simulation
Upper bound
Mixed integer programming
Optimization techniques
Distance measure
Simulation model
Graph

Cite this

@article{f556d9e2e3b942db96ee94d31c3ba7d6,
title = "Bounds for maximin Latin hypercube designs",
abstract = "Latin hypercube designs (LHDs) play an important role when approximating computer simulation models. To obtain good space-filling properties, the maximin criterion is frequently used. Unfortunately, constructing maximin LHDs can be quite time consuming when the number of dimensions and design points increase. In these cases, we can use heuristical maximin LHDs. In this paper, we construct bounds for the separation distance of certain classes of maximin LHDs. These bounds are useful for assessing the quality of heuristical maximin LHDs. Until now only upper bounds are known for the separation distance of certain classes of unrestricted maximin designs, i.e., for maximin designs without a Latin hypercube structure. The separation distance of maximin LHDs also satisfies these “unrestricted” bounds. By using some of the special properties of LHDs, we are able to find new and tighter bounds for maximin LHDs. Within the different methods used to determine the upper bounds, a variety of combinatorial optimization techniques are employed. Mixed-integer programming, the traveling salesman problem, and the graph-covering problem are among the formulations used to obtain the bounds. Besides these bounds, also a construction method is described for generating LHDs that meet Baer’s bound for the distance measure for certain values of n.",
author = "{van Dam}, E.R. and G. Rennen and B.G.M. Husslage",
note = "Appeared earlier as CentER Discussion Paper 2007-16",
year = "2009",
language = "English",
volume = "57",
pages = "595--608",
journal = "Operations Research",
issn = "0030-364X",
publisher = "INFORMS Inst.for Operations Res.and the Management Sciences",
number = "3",

}

Bounds for maximin Latin hypercube designs. / van Dam, E.R.; Rennen, G.; Husslage, B.G.M.

In: Operations Research, Vol. 57, No. 3, 2009, p. 595-608.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Bounds for maximin Latin hypercube designs

AU - van Dam, E.R.

AU - Rennen, G.

AU - Husslage, B.G.M.

N1 - Appeared earlier as CentER Discussion Paper 2007-16

PY - 2009

Y1 - 2009

N2 - Latin hypercube designs (LHDs) play an important role when approximating computer simulation models. To obtain good space-filling properties, the maximin criterion is frequently used. Unfortunately, constructing maximin LHDs can be quite time consuming when the number of dimensions and design points increase. In these cases, we can use heuristical maximin LHDs. In this paper, we construct bounds for the separation distance of certain classes of maximin LHDs. These bounds are useful for assessing the quality of heuristical maximin LHDs. Until now only upper bounds are known for the separation distance of certain classes of unrestricted maximin designs, i.e., for maximin designs without a Latin hypercube structure. The separation distance of maximin LHDs also satisfies these “unrestricted” bounds. By using some of the special properties of LHDs, we are able to find new and tighter bounds for maximin LHDs. Within the different methods used to determine the upper bounds, a variety of combinatorial optimization techniques are employed. Mixed-integer programming, the traveling salesman problem, and the graph-covering problem are among the formulations used to obtain the bounds. Besides these bounds, also a construction method is described for generating LHDs that meet Baer’s bound for the distance measure for certain values of n.

AB - Latin hypercube designs (LHDs) play an important role when approximating computer simulation models. To obtain good space-filling properties, the maximin criterion is frequently used. Unfortunately, constructing maximin LHDs can be quite time consuming when the number of dimensions and design points increase. In these cases, we can use heuristical maximin LHDs. In this paper, we construct bounds for the separation distance of certain classes of maximin LHDs. These bounds are useful for assessing the quality of heuristical maximin LHDs. Until now only upper bounds are known for the separation distance of certain classes of unrestricted maximin designs, i.e., for maximin designs without a Latin hypercube structure. The separation distance of maximin LHDs also satisfies these “unrestricted” bounds. By using some of the special properties of LHDs, we are able to find new and tighter bounds for maximin LHDs. Within the different methods used to determine the upper bounds, a variety of combinatorial optimization techniques are employed. Mixed-integer programming, the traveling salesman problem, and the graph-covering problem are among the formulations used to obtain the bounds. Besides these bounds, also a construction method is described for generating LHDs that meet Baer’s bound for the distance measure for certain values of n.

M3 - Article

VL - 57

SP - 595

EP - 608

JO - Operations Research

JF - Operations Research

SN - 0030-364X

IS - 3

ER -