Engines

A covering design comes from an engine, chosen with the engine keyword of covering, all_pairs, and the other covering functions, whose default is Auto(). Every engine keeps the same promise: every returned case is valid, every feasible combination is covered, and every excluded combination is reported (contract §1.3, §1.4). Generation checks the cases against the rules and the combinations before it returns them, whichever engine made them (§1.21). The engines differ in how many cases they give, how long they take, and whether they use randomness. excursions and full_factorial are strategies, not engines, and take no engine.

recommend says, before anything is generated, what Auto would run for your space and why.

The size of a design, and its lower bound

No engine promises a minimum number of cases (§8.1). Every covering result does state a lower bound beside its count: no design for the same request can have fewer cases than this, though the fewest a design can have may be more. Each case holds exactly one combination of any set of parameters, so the combinations of one set need a case each; a must-include row is a case of every design; and the negative rows of each Invalid value are bounded the same way and added. The summary line shows the bound, and says "minimal" when the count meets it, which proves that no design has fewer cases (§8.4, §8.7):

using UnitTestDesign
all_pairs(fill(1:3, 4)...; engine = IPOG())

9 cases (minimal) · strength 2 · IPOG · 4 parameters · 81 combinations
    p1  p2  p3  p4
 1  1   1   1   1
 2  1   2   2   2
 3  1   3   3   3
 4  2   1   2   3
 5  2   2   3   1
 6  2   3   1   2
 7  3   1   3   2
 8  3   2   1   3
 9  3   3   2   1

all_pairs(fill(1:3, 4)...)

9 cases (minimal) · strength 2 · Auto: Construction() · 4 parameters · 81 combinations
    p1  p2  p3  p4
 1  1   1   1   1
 2  2   2   2   1
 3  3   3   3   1
 4  1   2   3   2
 5  2   3   1   2
 6  3   1   2   2
 7  1   3   2   3
 8  2   1   3   3
 9  3   2   1   3

cases.record holds the bound, its proof in words, and whether the count meets it, beside the engine's configuration and what each stage did (see What a result records); report prints the bound on its "size:" line. Where rules exclude combinations, the bound counts only the feasible ones. A count above the bound is not necessarily above the minimum: for 8 binary flags the bound is 4, and the smallest design that exists has 6 cases, by Kleitman and Spencer's theorem on pairwise arrays of two values (Kleitman and Spencer 1973; Colbourn 2004, p. 127), which Auto() builds.

IPOG

IPOG, the in-parameter-order generator, covers the first few parameters, then adds one parameter at a time. Each step first gives the new parameter a value in the existing cases, choosing values that cover the most new combinations, which it finds by lookup rather than by a scan, and then adds cases for the combinations still missing. It builds four designs this way, with two rules for breaking ties and two orders for adding cases, and keeps the one with the fewest cases; the result's record.ordinary.member says which. The IPOG page describes the algorithm.

IPOG uses no randomness (§9.4). For the same inputs, the same package version, and the same Julia version, it returns the same cases in the same order, in every run and every process (§9.1). It covers any request: rules, must-include rows, stronger groups and Invalid values.

Auto

Auto chooses the engine from the request. goal says what your tests cost, which the space can't tell:

:balanced is never larger than :fast wherever it builds IPOG's design too, and costs little more: where the catalog applies, building its array takes milliseconds. Where every parameter has the same number of values it is often a quarter smaller or more. On spaces whose parameters have different numbers of values the catalog seldom applies, and :balanced gives IPOG's cases. So :fast is what IPOG() already does, and not a recommendation.

How :balanced chooses, from the request alone:

• where the catalog doesn't apply (different numbers of values on more than strength + 1 parameters), it runs IPOG;
• where the catalog's array has as many cases as the lower bound, no design has fewer, so it builds the array without running IPOG;
• where the space has at most 100,000 combinations to cover, counted before the rules, it builds both and keeps the one with fewer cases, IPOG's on a tie, so that it gives IPOG's cases unless the catalog's are fewer;
• above that, it builds the catalog's array for a shape the catalog builds exactly (every parameter with the same number of values, or strength + 1 parameters, with no rules, no must-include rows other than negative ones, and no stronger groups), and runs IPOG otherwise. In the package's benchmarks no such space had a catalog array larger than IPOG's design, but there the two are not compared, so that is measured, not guaranteed.

:compact reduces that winner once, with the row reducer of Compact, unless the space is past the reducer's limits (below), when it returns the winner as it is and the record's chose names the winner alone. The negative rows of a space with Invalid values are chosen the same way, for each invalid value, and the record keeps each choice.

eight = fill(1:7, 8)          # eight parameters with seven values each
(IPOG = length(all_pairs(eight...; engine = IPOG())), Auto = length(all_pairs(eight...)))

(IPOG = 78, Auto = 49)

recommend(eight...)

Recommendation: 8 parameters × 7 values, strength 2, no rules; 1372 combinations to cover
  skip  IPOG()          not run: no design has fewer rows than the catalog's array, which meets the lower bound
  use   Construction()  49 rows: Bush orthogonal array, every combination exactly once
lower bound: 49 cases: the 7 × 7 = 49 combinations of p1 and p2 need a case each
goals: :fast (IPOG alone) known only after running; :balanced 49 cases, the minimum; :compact 49 cases, the minimum
covering(…) would use Construction().

The result records what Auto chose, cases.record.ordinary.chose, and each start it ran, with its size and what it built, cases.record.ordinary.starts; the summary line names it, as "Auto: Construction()". The choice depends only on the request, never on the clock, a limit, or which other packages are loaded (§9.12), but a later version may choose differently (§9.8). :fast and :balanced use no randomness; :compact draws from seed, 0 by default, which the result records (§9.11).

Construction

Construction builds the design from a catalog of algebraic constructions, for a space whose parameters all have the same number of values, or that has at most strength + 1 parameters. It chooses the smallest array the catalog has for the shape, from sizes alone, without searching:

• orthogonal arrays (Bush) for a prime-power number of values, which show every combination exactly once: the fewest cases possible, and the balance a designed experiment wants;
• the zero-sum array for strength + 1 parameters of any sizes, also at the lower bound;
• Kleitman and Spencer's arrays for two values, which are the smallest that exist;
• cover starters, products of arrays, projection, tripling and fusion at strength 2; the LFSR array and its copies, group arrays, the ordered design and doubling recursions at strength 3.

Above strength 3 it offers only the arrays that meet the lower bound, the zero-sum and orthogonal arrays, and refuses the rest. For 2 to 12 values and 3 to 20 parameters at strength 2, the catalog's array equals the smallest known at 104 of 198 shapes and is within 10% of it at 166.

With rules, must-include rows or stronger groups, the catalog's rows seed IPOG: those that no rule forbids are kept, after the must-include rows, except a row that holds nothing the must-include rows and the rows before it don't, so a result passed back as must_include for the same space gains no cases; then IPOG adds what they leave uncovered. Partial must-include rows, such as a design passed back after parameters were added or removed, are first completed as IPOG would complete them, when that shows more of the catalog's rows to be unneeded. With stronger groups the seed is often the strongest group's own array, on that group's parameters, which IPOG extends to the others. With a few rules this is much smaller than IPOG alone; as rules forbid more of the array it helps less, which is why Auto builds both. A space it has no array for, such as parameters with different numbers of values, is refused with the reason, in an ArgumentError that suggests IPOG() or Auto(). With Invalid values the ordinary cases are the catalog's, and the negative rows of each invalid value cover a request one strength lower on the other parameters; where the catalog has no array for that request, as at strength 1, those rows are IPOG's, though the result names Construction. The negative rows repeat some of the array's combinations, so the record of such a design never calls it an orthogonal array. The result's record names the array:

cases = all_pairs(eight...; engine = Construction())
cases.record.ordinary.catalog

(name = "Bush", family = "Bush orthogonal array", source = "Sherwood 2005, PDF p.3", rows = 49, lower_bound = 49, orthogonal = true, seeded = false)

Construction uses no randomness (§9.4).

Compact

Compact(inner; seed = 0, effort = 1) runs inner, then removes rows from its design, after the tabu searches TCA and FastCA: it deletes the row whose removal uncovers the fewest combinations, repairs the design at that size by changing one value of a case or copying in a case from the start, and repeats while each repair succeeds, stopping at the lower bound the result records. Every case it writes is checked against the rules on its own, so it never searches, can't stop at feasibility_limit, and its cases don't depend on it (§3.8). Must-include rows stay first and unchanged. The negative rows of a space with Invalid values are reduced too, for each invalid value; where inner refuses that request, as Construction() does at strength 1, IPOG's rows for it are reduced, as Compact(IPOG()) would.

On 100 random spaces of 4 to 12 parameters with 2 to 7 values, at strength 2, it reached the lower bound, and so proved its design minimal, on 92, in under 50 ms each. From the catalog's array it ends lower than from IPOG's design. seed seeds a fresh generator for every call, so the same seed gives the same cases; effort multiplies its two budgets, of steps and of combinations read, never seconds (§9.11). Beyond 2²⁵ combinations to cover, or 65,535 cases, it returns inner's design unreduced. The result's record says what it did, cases.record.ordinary.reducer, and what inner did, cases.record.ordinary.start.

GND

GND builds the design one case at a time, in the manner of the AETG generator (Cohen et al., 1997). For each new case it draws candidates random candidate cases. Each candidate starts from the parameter with the most uncovered combinations and sets the others in a random order, giving each the value that covers the most uncovered combinations. GND keeps the candidate that covers the most, and repeats until every required combination is covered.

GND(; seed = 0, candidates = 50, rng = nothing)

• seed: every call seeds a fresh generator from seed, so repeated calls with the same inputs return the same design (§9.5). The default is
  1. The seed is recorded in the result, as cases.seed, and
  report prints it. Another seed gives another design with the same guarantee.
• rng: to draw from your own generator instead, pass it as rng. GND copies it at the start of every call and never advances it, so two calls with the same rng agree and your generator is left as it was (§9.6). The recorded seed is then nothing.
• candidates: the number of candidate cases drawn for each new case. More candidates mean more work per case and do not reliably give a shorter design. The 0.4 keyword M still works, with a deprecation warning, and means candidates.

The progress guarantee. If no candidate covers anything new, GND builds the case from the first uncovered combination instead. That combination is feasible, since only feasible combinations are required, so it can be completed into a valid case that covers it. Every round therefore covers at least one combination, and GND stops after at most as many rounds as there are required combinations. There is no retry limit and no "could not construct a case" error.

Other seeds give other designs, of slightly different lengths, and the same rng gives the same design without advancing it:

[length(all_pairs(fill(1:8, 10)...; engine = GND(seed = s))) for s in 0:4]

5-element Vector{Int64}:
 100
 101
 101
 101
 102

using Random
rng = Xoshiro(2024)
before = copy(rng)
four = fill(1:4, 10)
a = all_pairs(four...; engine = GND(rng = rng))
b = all_pairs(four...; engine = GND(rng = rng))
(same_design = a == b, rng_unchanged = rng == before, recorded_seed = a.seed)

(same_design = true, rng_unchanged = true, recorded_seed = nothing)

What a result records

A covering result keeps how its cases were made in cases.record. The lower bound, its proof, and whether the count meets it (minimal) are the package's own, proved at generation and checked against the cases; no engine sets them. cases.record.engine is the engine's configuration, the whole tree of it: each engine's name, constructor call, seed and settings, with an engine it wraps or chooses among nested inside. The seed line of report names that call, which with the same request gives the same cases:

nine = fill(1:3, 4)
cases = all_pairs(nine...; engine = Compact(GND(seed = 17); seed = 3, effort = 2))
cases.record.engine

(name = :Compact, call = "Compact(GND(seed = 17); seed = 3, effort = 2)", seed = 3, randomized = true, settings = (inner = (name = :GND, call = "GND(seed = 17)", seed = 17, randomized = true, settings = (candidates = 50,)), effort = 2))

report(cases)

9 cases cover all 54 feasible pairs of an 81-combination space; Compact(GND(seed = 17)) seed 3
size: 9 cases, minimal: the 3 × 3 = 9 combinations of p1 and p2 need a case each
bonus: 36 of 108 feasible triples covered
prefix curve:
  first 2 of 9 cover 22% (12 of 54)
  first 4 of 9 cover 44% (24 of 54)
  first 6 of 9 cover 66% (36 of 54)
  first 8 of 9 cover 88% (48 of 54)
  first 9 of 9 cover 100% (54 of 54)
seed: 3 (Compact(GND(seed = 17); seed = 3, effort = 2) repeats these cases)

cases.record.ordinary is the stage that made the ordinary cases: the engine's call, the cases it made, and what it reports, which for Compact is its inner engine's stage, start, and the reducer's run, reducer; for Auto, each start it ran, starts, which one it kept, kept, and what it chose, chose; and for Construction, its array, catalog:

cases.record.ordinary

(engine = "Compact(GND(seed = 17); seed = 3, effort = 2)", rows = 9, start = (engine = "GND(seed = 17)", rows = 11), reducer = (start = 11, rows = 9, bound = 9, steps = 0, budget = 60000, work = 142, work_budget = 4000000000, stop = :bound))

With Invalid values, cases.record.negative has one entry for each invalid value: the parameter, the value, the cases that hold it, and the stage that covered its negative combinations, a request one strength lower on the other parameters. Its engine says which engine ran there: the same one, or IPOG where the engine has nothing for that request, as Construction has nothing at strength 1:

flagged = TestSpace((a = [1, 2, 3, Invalid(0)], b = 1:3, c = 1:3, d = 1:3))
all_pairs(flagged; engine = Construction()).record.negative

1-element Vector{NamedTuple}:
 (parameter = :a, value = "Invalid(0)", rows = 3, stage = (engine = "IPOG()", rows = 3, member = (tiebreak = :lowest, vertical = :support)))

What every engine does with rules

Before generating, the call classifies every combination at the requested strengths as required or excluded, with the rules that exclude it (Constraints). While generating, IPOG, GND and the catalog's seeded path set a value only when the partial case can still be completed into a valid case; the reducer writes only cases it has checked whole. No engine can reach a dead end. Before returning, generation checks every case against the rules and every required combination against the cases; a failed check is an internal error, never a returned design (§1.21). A search that reaches feasibility_limit throws a ResourceLimitError rather than return a design it cannot certify (§3.6).

How long the designs are

Cases for some spaces at this release, with the lower bound each result records. "Compact" is Auto(goal = :compact) at its default effort and seed.

Where every parameter has the same number of values, the catalog is far below IPOG: over a sample of 132 such shapes at strength 2, IPOG returns a median of 26% more cases, and over 70 at strength 3, 35% more. On spaces of parameters with different numbers of values, Auto() is IPOG, and the reducer is what removes cases: on 100 random such spaces at strength 2 it saved 4.5% of IPOG's cases on average. No design for smooth has fewer than 11 cases, which an exhaustive search over its 57 valid cases shows (the package's tests repeat it), and none for 8 binary flags has fewer than 6, by Kleitman and Spencer's theorem. Those results have the fewest cases possible, though their bounds are lower, and the package, which calls a count minimal only when it meets its bound, doesn't say so (§8.4).

What a smaller design gives up

A pairwise design covers some triples by accident, and a smaller one covers fewer: bench12's 21 IPOG cases cover 60.7% of its feasible triples, and the reduced 18 cover 56.1%. When tests are cheap, the larger design is arguably the better one: it finds more of the failures that need three values together. report's "bonus" line counts these triples for any result, and all_triples covers them all. This is why no default reduces a design. The default Auto() does keep the catalog's array where it has fewer cases, and an orthogonal array holds each combination once, so it covers fewer triples too: for 8 parameters of 7 values, IPOG's 78 cases cover 21.8% of the triples and the array's 49 cover 14.3%. Name engine = IPOG() for IPOG's larger design.

What a call costs, and where it stops

The time of a warm call on an Apple M2 laptop with Julia 1.13, and the peak memory of the process, which includes about 310 MiB for Julia and the package. A call is slower when a garbage collection lands in it, and a peak moves with the collector: where two figures are given, both were measured. "Compact" is Auto(goal = :compact); "one rule" is a single rule forbidding one pair. A first call also compiles: about a tenth of a second for a small space, and 3 seconds for a space of 250 parameters, for its row type.

(benchmark/engine_costs.jl repeats these.) What grows, and what stops a call that is too large; a design that can't be certified is not returned:

• Strength and width. The combinations to cover grow with the number of parameters to the power of the strength, and IPOG's time with them and with the cases. The supported scale is 250 parameters, 64 values and strength 4, with strengths 5 and 6 on about 20 parameters; strength 6 on 20 three-valued parameters took 19 minutes at the start of this release's work.
• Rules. With any rule, every combination is classified before generation, each by a feasibility search, and the call keeps the searches' answers for the parameters that rules link together: a rule over two parameters keeps a few answers however wide the space, while a rule that reads the whole case, or rules that chain many parameters, link them into one search whose answers grow with the combinations. Classification keeps nothing for a required combination but its count, and for an excluded one its explanation. During the call, IPOG marks with a bit each combination of a set of parameters that a rule partly excludes, and GND holds every required combination as a column of the parameters, eight bytes each. Twenty binary parameters at strength 6 with one rule peaked at 414 to 447 MiB, where at the start of this release's work they peaked at 4.3 to 7.1 GiB. On 200 options with 24 rules a first call, which compiles, took 2.1 seconds and a warm call 0.05 seconds, peaking at 445 MiB, where a first call took 3 seconds and 1.4 GiB; on 400 options with 46 rules a first call took 9.2 seconds and a warm call 2.5 seconds, peaking at 756 to 775 MiB, where a first call took 19 seconds and 6.2 GiB. There classification is nearly the whole call, and most of it is explaining the 3,281 combinations that the rules exclude only together: the search for the rules behind each, which explanation_limit bounds (with a limit of 1, which leaves those explanations unresolved, classification took 0.2 seconds where it took 2.1). Where rules link many parameters into one search, that search sets the time. A rule that reads the whole case is checked only on complete cases, which makes its search far longer than a scoped rule's (what rules cost).
• feasibility_limit (1,000,000 nodes per question by default) stops a search that can't decide whether a combination or a partial case has a valid completion, with a ResourceLimitError that names it. Raise it to finish; a larger limit never changes the cases of a call that succeeded (§3.8). IPOG's call needs a limit enough for each of the designs it builds (IPOG).
• Memory has no limit in the package: a request too large for the machine fails as the operating system fails it.
• The reducer returns its start unreduced beyond 2²⁵ combinations to cover or 65,535 cases, and its budgets count work: at the default effort it takes up to about 20 seconds at strength 3 on larger spaces, such as 30 parameters of 4 values, and at strengths 4 to 6.
• Certification reads every case for every set of strength parameters, whichever engine made the design.

Which to choose

• Use the default, Auto(), for most tests: it is never larger than IPOG where it builds both (and above 100,000 combinations, on the package's benchmarks, it never was), much smaller when every parameter has the same number of values, and IPOG's design on most other spaces. On 681 of the package's benchmark spaces, a warm call took at most about a millisecond longer than IPOG alone. recommend shows what it would do.
• IPOG() builds IPOG's design alone, which is what Auto(goal = :fast) runs. It is deterministic and covers any request. It is fast without rules or with a few. With many rules it slows down and takes more memory: each of the four designs it builds asks the feasibility search whether a partial case can still be completed, so on a heavily constrained space it can take a few times as long as one design would.
• Use Auto(goal = :compact), or Compact around an engine you choose, when each case is expensive, such as a simulation or a hardware run. Its lower bound tells you how far from the minimum the design can be.
• Use Construction() when you want the catalog's array itself, such as an orthogonal array for a designed experiment.
• Use GND with several seeds when you want designs that differ but keep the same guarantee, for instance to vary the cases a nightly job runs.

design_sizes compares engines on your space, one row per engine:

design_sizes(fill(1:5, 6)...; strengths = 2:3, distances = Int[], engine = [IPOG(), Auto(), Auto(goal = :compact)])

strategy        engine                 cases   share    pairs    triples
full_factorial                         15625  100.0%  375/375  2500/2500  valid 15625 of 15625
covering(2)     IPOG()                    38    0.2%  375/375   733/2500
covering(2)     Auto()                    25    0.2%  375/375   500/2500
covering(2)     Auto(goal = :compact)     25    0.2%  375/375   500/2500
covering(3)     IPOG()                   190    1.2%  375/375  2500/2500
covering(3)     Auto()                   125    0.8%  375/375  2500/2500
covering(3)     Auto(goal = :compact)    125    0.8%  375/375  2500/2500
case counts are the rows each strategy produced with each engine, not lower bounds

No engine promises the same design across package versions, or after you add a value or a rule (§9.8, §9.9); Auto's choice and the catalog's arrays may change too. When the exact cases matter, save them and pass them back as must_include, which keeps every saved case and adds only what an edit requires (§9.10); see Commit a design as data.

Before 0.5

Two things changed in GND for 0.5. The 0.4 release scored candidate values against the wrong number of known parameters, so once enough parameters were set its choices were effectively random. Fixing the score shrank GND's designs by 17 to 35 percent (for ten four-valued parameters, pairwise, from 36 to 38 cases down to 30; for ten eight-valued parameters, from about 152 down to 100). And the 0.4 GND() drew from an unseeded generator, so two identical calls gave different designs; the fixed default seed replaces it. Comparisons made with 0.4 therefore understate GND, and the 0.4 version of this page, which said GND gives shorter designs in general, overstated it.

Reference

• Cohen, D. M., S. R. Dalal, M. L. Fredman, and G. C. Patton. "The AETG system: An approach to testing based on combinatorial design." IEEE Transactions on Software Engineering 23(7), 1997.
• Colbourn, C. J. "Combinatorial aspects of covering arrays." Le Matematiche 59, 2004. The catalog's other constructions and their sources are listed in the package's source, src/construction_arrays.jl.
• Lin, J., C. Luo, S. Cai, K. Su, D. Hao, and L. Zhang. "TCA: An efficient two-mode meta-heuristic algorithm for combinatorial test generation." ASE 2015.
• Lin, J., S. Cai, C. Luo, Q. Lin, and H. Zhang. "Towards more efficient meta-heuristic algorithms for combinatorial test generation." ESEC/FSE