Definition

A constraint hierarchy is a scheme in which soft constraints are organized into multiple priority tiers according to their perceived importance in a particular verification scenario. In the cited stimuli-generation context, expert knowledge is entered as soft constraints and may be applied in such a multi-tiered hierarchy, identified in the source as a Borning hierarchy. ^[1]

Role in CSP-based stimuli generation

The cited work uses constraint satisfaction problems (CSPs) because CSPs are declarative: rules can be stated directly and enforced by the underlying CSP algorithm. The same setting also uses Soft-CSP machinery to account for prioritizations on expert-knowledge rules. ^[2]

Within this framework, a constraint hierarchy provides the prioritization structure for expert-knowledge soft constraints. The source notes that constraint hierarchies appear in other applications, but reports that stimuli generation appears distinctive in both the number of soft constraints in the model and the depth of the hierarchy. ^[3]

Interaction with randomized solution sampling

Stimuli generation in the cited setting also requires repeated sampling from the same Soft-CSP instance: a design model plus a test template defines a single Soft-CSP, but the solver is expected to produce many different tests that are distributed as uniformly as possible among conforming tests. ^[4]

This requirement can conflict with a strict constraint-hierarchy objective. If the maximal number of soft constraints can be satisfied by only one assignment, then a pure hierarchy-oriented solver would have to return that assignment every time. The source identifies this as contradicting the goal of diverse tests for a given template. ^[5]

Local metric compromise

The cited approach resolves the conflict by defining a local metric for solving the soft constraint hierarchy. Under this metric, if a partial solution can be extended to satisfy additional soft constraints, it must be extended in that way; however, the solver drops the requirement that the final solution satisfy a globally maximal number of soft constraints over the entire search space. ^[6]

Practical implication

In this usage, a constraint hierarchy is not merely an optimization criterion. It is balanced against randomized exploration: the solver still honors additional satisfiable soft constraints locally, while avoiding a global-maximization rule that could collapse repeated runs onto a single solution and undermine test diversity. ^[6]