Computational Methods for the
Generation of Spatially
Balanced Latin Squares
Cornell University
Caption: spatially-balanced Latin square of order 6
Caption: Average distance between pairs of symbols.
Generation of Spatially Balanced Latin Squares
In a spatially-balanced Latin square all pairs of symbols have the same total distance in the Latin square. The distance of two symbols
in a given row is the difference between the column indices of the symbols. The existence of spatially-balanced Latin squares is an open
question in combinatorics, and no polynomial time constructions for the generation of spatially-balanced Latin squares have been found
yet. Therefore, in order to get some insights into the structure of spatially-balanced Latin squares we used general local and complete
search methods. We discovered that local search methods do not scale
well on this domain, failing to find the global optimum for instances larger
than order 9. On the other hand, our results with a CP based approach were very promising and we
could generate totally spatially-balanced Latin squares up to order 18. Furthermore the CP based models provided us with interesting
insights about the structure of this problem that allowed us to conjecture the existence of polynomial time constructions for
generating spatially-balanced Latin squares. We are currently working on finding such efficient constructions.
An Applet visualizing Spatially Balanced Latin Squares
Using the local search and the Constraint Programming approaches, we
pre-computed spatially balanced Latin squares. Go to our
Java Applet with Hundreds of Spatially Balanced Designs. The applet contains fully-balanced designs as well as
sub-optimal solutions found by the local search approach.
Motivational Application: Agronomic Field Experiments [van Es and van
Es 93; van Es 2002]
In agronomic field experiments, one has to test and compare different soil
treatments. Two different soil treatments may correspond to two different
fertilizers or two different ways of preparing the soil. In order to perform
statistically significant field experiments, it is important to test different
treatments in an unbiased way. Most agronomic field experiments are implemented
through randomized complete
block designs (RCBD) where each block has as many experimental units as
treatments
. Use of blocks is in most cases justified by spatial variability in fields, and
this layout is an attractive way to organize replications. This approach to
experimental design uses random allocation of treatments to plots, which is used
to ensure that a treatment is not continually favored or handicapped in
successive replications by user bias or some extraneous source of variation
.
Consider the following example of an RCBD:
Use any fixed assignment of treatments to symbols:
Treatment 1 = A
Treatment 2 = B
Treatment 3 = C
Treatment 4 = D
Treatment 5 = E
Then permute the the symbols randomly within each block:
Block 1 D B A E C
Block 2 A B E C D
Block 3 B A C D E
Although this randomization approach is intuitively attractive, it has been
shown to cause biases and imprecision under most field conditions
(Van Es 92. The reason for this is that underlying soil characteristics are
typically non-random and show field trends, spatial autocorrelation, or
periodicity
. For example, fertility patterns in fields often exhibit high and low areas due
to, among others, erosion, drainage variability, and management history. The
classical randomization process does not explicitly account for such field
patterns, and many realizations of such RCBD designs may result in undesirable
outcomes.
The first problem is the spatial distribution of individual treatments.
In the example above, we see for example that treatments 1 and 2 (symbols A and
B) are planted on the west side of the field in all blocks. What often happens
in practice is that the researchers choosing the design will iterate the
randomization process until they are content with the spatial distribution of
the individual treatments - a fact that makes the whole purpose of randomization
obsolete. To overcome this problem, it has been suggested to consider Latin
square designs. A Latin square has the same number of blocks as there are
treatments, such that one treatments occurs in each column exactly once:
Consider the following example of a Latin square design:
First randomize the assignment of treatments to symbols:
Treatment 1 = E
Treatment 2 = C
Treatment 3 = D
Treatment 4 = A
Treatment 5 = B
Then choose a pre-computed Latin square to assign treatments to
concrete slots:
Block 1 D B A E C
Block 2 A E B C D
Block 3 B A C D E
Block 4 E C D A B
Block 5 C D E B A
Another problem with RCBDs is the expected distribution of pairs of
treatments. Looking at the Latin square above, we see that, in every block,
treatments 4 and 5 (symbols A and B) are always planted very close to each
other, while treatments 2 and 5 (symbols B and C) have a larger average distance
within each block. Due to spatial correlations in the field, such a design is
highly undesirable. Therefore, van Es and van Es proposed spatially balanced
experimental designs that are inherently robust to non-random field variability.
Like for Latin square designs, this approach uses dummy indicators and the
treatments are randomly assigned to the indicators. In other words, treatments
are randomly allocated to optimized designs, rather than to plots. Such designs
may be spatially-balanced complete block designs or spatially-balanced Latin
squares, the latter being a special case of the former. In a spatially-balanced
Latin square all pairs of symbols (treatments, in agronomic terms) have the same
total distance in the Latin square. The distance of two symbols in a given row
is the difference between the column indices of the symbols.
Consider the following example of a fully-balanced Latin square design:
First randomize the assignment of treatments to symbols:
Treatment 1 = A
Treatment 2 = C
Treatment 3 = B
Treatment 4 = E
Treatment 5 = D
Then choose a pre-computed spatially-balanced Latin square to assign
treatments to concrete slots:
Block 1 A B C D E
Block 2 B E D A C
Block 3 C D B E A
Block 4 D A E C B
Block 5 E C A B D
References
Carla Gomes and Meinolf Sellmann Streamlined Constraint Reasoning. Proc. CP04, 2004.
Carla Gomes, Meinolf Sellmann, Cindy van Es, and Harold van Es The Challenge
of Generating Spatially Balanced Scientific Experiment Designs. To appear in
Proc. CP-AI-OR
, 2004.
Harold van Es, Sources of soil variability. In Methods of Soil Analysis, Part 4: Physical
Properties, Soil Sci. Soc. Am, 2002.
Harold van Es and Cindy van Es. The spatial nature of randomization and its effects on outcome of field
experiments. Agronomy Journal, 85, pp 420-428, 1993.