Bounds for Maximin Latin Hypercube Designs

Research output: Working paperDiscussion paperOther research output

219 Downloads (Pure)

Abstract

Latin hypercube designs (LHDs) play an important role when approximating computer simula- tion 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 approximate 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 approximate 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 struc- ture. 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 vari- ety of combinatorial optimization techniques are employed. Mixed Integer Programming, the Travelling 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 ℓ1 distance measure for certain values of n.
Original languageEnglish
Place of PublicationTilburg
PublisherOperations research
Number of pages20
Volume2007-16
Publication statusPublished - 2007

Publication series

NameCentER Discussion Paper
Volume2007-16

Fingerprint

Latin Hypercube Design
Maximin
Graph Covering
Latin Hypercube
Upper bound
Covering Problem
Mixed Integer Programming
Combinatorial Optimization
Distance Measure
Travelling salesman problems
Optimization Techniques
Computer Simulation

Keywords

  • Latin hypercube design
  • maximin
  • space-filling
  • mixed integer programming
  • trav- elling salesman problem
  • graph covering.

Cite this

van Dam, E. R., Rennen, G., & Husslage, B. G. M. (2007). Bounds for Maximin Latin Hypercube Designs. (CentER Discussion Paper; Vol. 2007-16). Tilburg: Operations research.
van Dam, E.R. ; Rennen, G. ; Husslage, B.G.M. / Bounds for Maximin Latin Hypercube Designs. Tilburg : Operations research, 2007. (CentER Discussion Paper).
@techreport{da0c15bef18e474eb557fe98b7ed88a6,
title = "Bounds for Maximin Latin Hypercube Designs",
abstract = "Latin hypercube designs (LHDs) play an important role when approximating computer simula- tion 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 approximate 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 approximate 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 struc- ture. 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 vari- ety of combinatorial optimization techniques are employed. Mixed Integer Programming, the Travelling 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 ℓ1 distance measure for certain values of n.",
keywords = "Latin hypercube design, maximin, space-filling, mixed integer programming, trav- elling salesman problem, graph covering.",
author = "{van Dam}, E.R. and G. Rennen and B.G.M. Husslage",
note = "Subsequently published in Operations Research, 2009 Pagination: 20",
year = "2007",
language = "English",
volume = "2007-16",
series = "CentER Discussion Paper",
publisher = "Operations research",
type = "WorkingPaper",
institution = "Operations research",

}

van Dam, ER, Rennen, G & Husslage, BGM 2007 'Bounds for Maximin Latin Hypercube Designs' CentER Discussion Paper, vol. 2007-16, Operations research, Tilburg.

Bounds for Maximin Latin Hypercube Designs. / van Dam, E.R.; Rennen, G.; Husslage, B.G.M.

Tilburg : Operations research, 2007. (CentER Discussion Paper; Vol. 2007-16).

Research output: Working paperDiscussion paperOther research output

TY - UNPB

T1 - Bounds for Maximin Latin Hypercube Designs

AU - van Dam, E.R.

AU - Rennen, G.

AU - Husslage, B.G.M.

N1 - Subsequently published in Operations Research, 2009 Pagination: 20

PY - 2007

Y1 - 2007

N2 - Latin hypercube designs (LHDs) play an important role when approximating computer simula- tion 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 approximate 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 approximate 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 struc- ture. 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 vari- ety of combinatorial optimization techniques are employed. Mixed Integer Programming, the Travelling 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 ℓ1 distance measure for certain values of n.

AB - Latin hypercube designs (LHDs) play an important role when approximating computer simula- tion 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 approximate 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 approximate 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 struc- ture. 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 vari- ety of combinatorial optimization techniques are employed. Mixed Integer Programming, the Travelling 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 ℓ1 distance measure for certain values of n.

KW - Latin hypercube design

KW - maximin

KW - space-filling

KW - mixed integer programming

KW - trav- elling salesman problem

KW - graph covering.

M3 - Discussion paper

VL - 2007-16

T3 - CentER Discussion Paper

BT - Bounds for Maximin Latin Hypercube Designs

PB - Operations research

CY - Tilburg

ER -

van Dam ER, Rennen G, Husslage BGM. Bounds for Maximin Latin Hypercube Designs. Tilburg: Operations research. 2007. (CentER Discussion Paper).