ScoreQuant

Result · D-BB-SINGLETON-BOUND

Singleton refinement bounds unfinished D assignments

Proved herepublication: internal

Read the proof and evidence →

Meaning

Singleton refinement supplies an upper bound for branch-and-bound certification on small finite problems.

Scientific context

A partial assignment can be bounded above by completing it with one singleton cell per unassigned observation, because refining a partition can only increase information. On small instances this lets a bounded search either prove a partition optimal or report honestly that its budget ran out before it could. The resulting certificate always states which of the two happened; a certificate that reports the budget as exhausted proves nothing about the incumbent partition, and says so explicitly.

Statement

For unassigned U, I_completion <= I_partial+Σ_{i∈U} w_i s_i s_i^T, so its logdet is a valid upper bound on every completion.

global certification

Relationships

Rests on

The full chain beneath it

Enables

Raises

Open next door

In the library

Carried by PartitionCertificate. Reference.

Every object and refusal

Local graph
Local map of Singleton-refinement branch-and-bound upper bound for D1 prerequisites to the left, 1 results it enables or questions it raises to the right, 0 boundary cases below.Refinement monotonicityRefinement monotonici…Stronger branch-and-bound upper boundsStronger branch-and-b…Singleton-refinement branch-and-bound upper bound for DSingleton-refinement…
Prerequisites to the left, what it enables or raises to the right, boundary cases below. Open in the map.

Proof

D12. Singleton-refinement branch-and-bound bound

For a partial assignment and unassigned point set UU, singleton refinement yields

Icompletion⪯Ipartial+∑i∈Uwisisi⊤.\boxed{ I_{\rm completion} \preceq I_{\rm partial}+ \sum_{i\in U}w_is_is_i^\top. }

Thus

log⁡det⁡(Ipartial+∑i∈Uwisisi⊤)\log\det\left( I_{\rm partial}+\sum_{i\in U}w_is_is_i^\top \right)

is a valid D upper bound for every completion.

Measured implementation: exact agreement with exhaustive search on small instances and certificates through N=40N=40 for reported d=2,K=3d=2,K=3 tests. The hardest reported N=40N=40 instance visited 131,799 nodes in 8.3 s; this is instance-dependent evidence, not a worst-case claim.

From D-optimality · chapter contents