Certificates

Both entry points are explicit post-fit operations. Neither runs during ordinary fitting, and neither repairs a labeling: they report what is true of the labels they are given.

exchange_stability_report

exchange_stability_report(scores: ArrayLike, labels: ArrayLike, *, weights: ArrayLike | None = None, criterion: DOptimality | ProfiledDOptimality | None = None, rank_rtol: float | None = None, gain_tolerance: float = 1e-10, execution: ExecutionConfig | None = None) -> StabilityReport

Certify one supplied labeling against every single-row relocation.

This runs exactly one complete exact scan of the same engine optimize_partition uses, on labels of any origin: a guarded Mahalanobis-Lloyd run stopped by guard="reject", an external tool, or a hand edit. Nothing is optimized and nothing is repaired; the report states whether an improving relocation exists and, when it does, names it.

Rows are scanned as supplied. Identical score rows are deliberately not merged, because relocating one row of a repeated score atom is an ordinary single-point move that the certificate must consider.

Parameters:

• scores (ArrayLike) –

  Finite score matrix with shape [N, P].

• labels (ArrayLike) –

  Integer labeling with shape [N]. Cell count is taken from the labels, and every cell below it must hold positive weight. Labels of zero-weight rows carry no measure but still count toward the declared cell range.

• weights (ArrayLike | None, default: None ) –

  Optional finite, nonnegative weights with shape [N].

• criterion (DOptimality | ProfiledDOptimality | None, default: None ) –

  DOptimality by default; ProfiledDOptimality certifies the same-label profiled objective instead.

• rank_rtol (float | None, default: None ) –

  Relative threshold of the informative Fisher subspace, matching the solver configuration that produced the labels.

• gain_tolerance (float, default: 1e-10 ) –

  Strict minimum gain that counts as an improvement. Match it to the gain_tolerance of the solver configuration that produced the labels: a labeling optimized at one tolerance is not certified at a smaller one, and the returned report records the tolerance it holds at.

Returns:

• StabilityReport –

  Stability verdict at gain_tolerance, exact objective, best remaining gain, and the improving move in original row indexing when one exists.

StabilityReport dataclass

StabilityReport(stable: bool, best_gain: float, best_move: tuple[int, int] | None, objective: float, n_bins: int, criterion: DOptimality | ProfiledDOptimality, gain_tolerance: float)

Certify that no single-row relocation improves one supplied labeling.

The report is produced by exchange_stability_report from exactly one complete exact scan, so it verifies labels of any origin: a guarded Mahalanobis-Lloyd run that stopped early, an external tool, or a hand edit.

Stability is always a statement at a tolerance, never at tolerance zero, so the certificate carries the tolerance it was issued at.

Attributes:

• stable (bool) –

  Whether no admissible relocation improves the criterion by more than gain_tolerance.

• best_gain (float) –

  Largest exact objective gain found in the scan. It is -inf when the labeling admits no relocation at all.

• best_move (tuple[int, int] | None) –

  (row, destination) of that gain in original input row indexing, or None when the labeling is stable.

• objective (float) –

  Exact criterion value of the supplied labeling, in the convention PartitionResult.objective uses for the same criterion.

• n_bins (int) –

  Number of cells the labeling declares.

• criterion (DOptimality | ProfiledDOptimality) –

  Criterion the scan certified against.

• gain_tolerance (float) –

  Strict minimum gain the scan counted as an improvement. stable means best_gain <= gain_tolerance; a labeling certified at one tolerance is not certified at a smaller one.

to_dict

to_dict() -> dict[str, JsonValue]

Return a JSON-compatible stability representation.

certify_partition

certify_partition(scores: ArrayLike, *, weights: ArrayLike | None = None, n_bins: int, incumbent: ArrayLike | None = None, criterion: DOptimality | ProfiledDOptimality | None = None, rank_rtol: float | None = None, config: CertificationConfig | None = None, execution: ExecutionConfig | None = None) -> PartitionCertificate

Prove or bound the global optimality of a finite D partition.

The search starts from an incumbent so that pruning is effective from the first node. Supplying the labels of an exchange result therefore answers the practical question directly: did the exchange already find the global optimum of this weighted score table?

Identical score rows are certified as one atom with their pooled weight, matching optimize_partition and the exhaustive test oracle. Their common label is what the certificate reports.

Parameters:

• scores (ArrayLike) –

  Finite score matrix with shape [N, P].

• weights (ArrayLike | None, default: None ) –

  Optional finite, nonnegative weights with shape [N].

• n_bins (int) –

  Number of cells to certify.

• incumbent (ArrayLike | None, default: None ) –

  Optional starting labeling with shape [N] and values in [0, n_bins), normally PartitionResult.labels. When omitted, one default D exchange supplies it. Identical score rows must already agree on their bin, and every cell must stay nonempty.

• criterion (DOptimality | ProfiledDOptimality | None, default: None ) –

  DOptimality by default and the only supported value.

• rank_rtol (float | None, default: None ) –

  Relative threshold of the informative Fisher subspace, matching the configuration that produced the incumbent.

• config (CertificationConfig | None, default: None ) –

  Search capacity and tolerance. Defaults to CertificationConfig().

Returns:

• PartitionCertificate –

  Best labeling found, the global upper bound at termination, the remaining gap, and whether the tree was exhausted.

Raises:

• ValueError –

  When the criterion is profiled, when the instance exceeds max_rows, or when the inputs cannot support a regular n_bins-cell partition.

CertificationConfig dataclass

CertificationConfig(max_nodes: int = 2000000, max_rows: int = 64, gain_tolerance: float = 1e-10)

Configure explicit branch-and-bound certification of a D partition.

Parameters:

• max_nodes (int, default: 2000000 ) –

  Maximum number of search nodes. Reaching it stops the search and downgrades the certificate to status="budget_exhausted" with a genuine outstanding upper bound; it never turns a partial search into a claim of optimality.

• max_rows (int, default: 64 ) –

  Maximum number of distinct positive-weight score atoms. Global certification is exponential in this count, so the guard refuses an oversized instance by name instead of appearing to hang. It may not exceed 512, the depth the search recursion supports.

• gain_tolerance (float, default: 1e-10 ) –

  Slack used both to prune a subtree and to accept a new incumbent, so status="optimal" means no labeling beats the reported objective by more than this much.

__post_init__

__post_init__() -> None

Validate the bounded-search capacity contract at construction time.

to_dict

to_dict() -> dict[str, JsonValue]

Return a JSON-compatible configuration mapping.

PartitionCertificate dataclass

PartitionCertificate(status: Literal['optimal', 'budget_exhausted'], objective: float, labels: ndarray, upper_bound: float, gap: float, nodes_explored: int, incumbent_was_optimal: bool)

Report what a bounded global D search actually proved.

certify_partition explores hard labelings with the singleton-completion upper bound: any completion of a partial assignment is coarser than the partial cells together with singleton cells for the unassigned atoms, so Loewner monotonicity of the log determinant makes \(\log\det(I_{\text{partial}}+R_t)\) a valid ceiling for the whole subtree. The search is exponential in the worst case and therefore explicitly bounded; the certificate always states which of the two outcomes occurred.

Attributes:

• status (Literal['optimal', 'budget_exhausted']) –

  "optimal" when the tree was exhausted, so no labeling beats objective by more than the configured gain tolerance. "budget_exhausted" when the node budget stopped the search first.

• objective (float) –

  Best log determinant found, in the Fisher-whitened convention of PartitionResult.objective under DOptimality.

• labels (ndarray) –

  Labels attaining objective, defined for every input row. Zero-weight rows carry the label of their nearest cell mean in the terminal metric and never influenced the search.

• upper_bound (float) –

  Global ceiling at termination. It equals objective for a proved optimum and is otherwise the best bound still outstanding on an abandoned subtree.

• gap (float) –

  upper_bound minus objective, nonnegative by construction and exactly zero for a proved optimum.

• nodes_explored (int) –

  Number of search nodes visited, including pruned children.

• incumbent_was_optimal (bool) –

  Whether the search proved the starting incumbent optimal without improving it. It is False whenever the budget was exhausted, because an unfinished search proves nothing about the incumbent.

to_dict

to_dict() -> dict[str, JsonValue]

Return a JSON-compatible representation of the certificate.