Bound Refinement

Concept

In hardware-accelerated constrained random test generation, bound refinement is the step within the GenerateSolution algorithm that, after assigning a value to one variable, updates the feasible interval (and associated strip set / total weight) of every still-unassigned variable. It is carried out by the RefineBound procedure, which uses the overlapping constraint set (OCS) of the strip selected for the assigned variable to shrink the bounds of the remaining variables and to re-derive their total weights.

First seen 7/7/2026

Last seen 7/7/2026

Evidence 5 chunks

Wiki v1

WIKI

Bound Refinement

Definition

In the context of hardware-accelerated constrained random test generation, bound refinement is the per-iteration operation that, after a value has been chosen for one variable $x_i$, recomputes the feasible interval $B_{x_j}$ of every still-unassigned variable $x_j$ (with $j > i$). The refinement uses the overlapping constraint set (OCS) of the strip that was selected for $x_i$ to eliminate from each remaining variable's range those values that cannot be combined with the just-assigned value while still satisfying the joint constraints.

READ FULL ARTICLE →

NEIGHBORHOOD

No graph connections found for this entity yet. It may appear in future ingestion runs.

explore full graph →

RELATIONSHIPS

2 connections

Hardware accelerated constrained random test generation ← uses 100% 2e

Bound refinement is used after each variable assignment to constrain remaining variables.

RefineBound procedure ← implements 100% 1e

RefineBound implements the bound refinement concept to update variable bounds after assignments.

LINKED ENTITIES

2 links

Hardware accelerated constrained random test generation USES Extracted graph relationship

RefineBound procedure IMPLEMENTS Extracted graph relationship

CITATIONS

7 sources

7 citations — click to expand

[1] Bound refinement updates the interval of every still-unassigned variable x_j after x_i is assigned, using the OCS of the chosen strip. Hardware accelerated constrained random test generation

[2] After refinement, the new boundary of variable y contains only certain strips (e.g. S_{y_1}, S_{y_2}, S_{y_3}) when x is assigned value x_0. Hardware accelerated constrained random test generation

[3] GenerateSolution invokes RefineBound(X_i, OCS(S_{x_i}^k), x_i^linear, x_i^NGV) and then ReCompToW to update TWt_{x_j} for each remaining variable x_j with j > i. Hardware accelerated constrained random test generation

[4] Theorem 4.1 establishes soundness: the refined bound B'_{x_{k+1}} is non-empty and is a subset of the previously feasible B_{x_{k+1}} whenever x_k is chosen validly. Hardware accelerated constrained random test generation

[5] Theorem 4.2 establishes completeness: every valid tuple is generated with non-zero probability because fixing x_k cannot exclude x_{k+1} from the refined bound, since x itself satisfies all OCS constraints C_p, C_q of the strip. Hardware accelerated constrained random test generation

[6] Initial lower and upper bounds of a variable x are defined as the min and max of the first/second coordinates of all its strips. Hardware accelerated constrained random test generation

[7] After refinement, the variable's total strip weight TWt_x must be recomputed so that subsequent strip selection remains correctly weighted. Hardware accelerated constrained random test generation