verify_assignment: Verify that an assignment is optimal
In couplr: Optimal Pairing and Matching via Linear Assignment

verify_assignment

R Documentation

Verify that an assignment is optimal

Description

Checks a solved assignment against the linear-programming optimality conditions and returns the result of each check. Unlike the status field on a solve result, which records what the solver terminated on, this is a statement about the matching: certified_optimal is TRUE only when every condition holds.

Usage

verify_assignment(
  x,
  cost = NULL,
  duals = NULL,
  maximize = FALSE,
  tol = 1e-09,
  arithmetic = c("auto", "exact", "double")
)

## S3 method for class 'assignment_certificate'
print(x, ...)

Arguments

`x`	An `assignment_certificate` object.
`cost`	Numeric cost matrix the assignment was computed on, or a lazy cost specification from `compute_distances()`. Required unless `x` already carries one.
`duals`	Optional list with elements `u` and `v` giving row and column potentials in the orientation of `cost`. Overrides any duals on `x`.
`maximize`	Logical; whether the assignment maximized rather than minimized. Defaults to `FALSE`.
`tol`	Numeric tolerance for the feasibility and slackness comparisons of a numerical certificate, ignored by an exact one. The duality-gap comparison scales it by the magnitude of the objective, since an absolute tolerance on a sum of many terms is not reachable in double precision.
`arithmetic`	One of `"auto"`, `"exact"` or `"double"`. `"auto"`, the default, reports the exact conclusion when the exact conditions hold and the numerical one otherwise, which is the strongest statement the instance supports; the exact conditions imply the numerical ones at any non-negative `tol`, so `"auto"` certifies nothing `"double"` would refuse. `"exact"` refuses to fall back, so `certified_optimal` is then `TRUE` only on an exact certificate. `"double"` decides everything within `tol`.
`...`	Ignored.

Value

An object of class assignment_certificate, a list with elements:

certified_optimal — logical, the conclusion. TRUE only when every condition below holds.
arithmetic — "exact" or "double", the arithmetic the conclusion was reached in.
exact_certificate — logical; whether the conditions hold in exact arithmetic. arithmetic = "double" does not ask the question, and reports FALSE here and in exact_available.
exact_available — logical; whether the exact question was asked of every condition. It is FALSE under arithmetic = "double", and on a certificate assembled from a scan that priced part of the problem against a tolerance rather than evaluating it, which is what the edge-generation loop hands back.
n_exact_violations, n_exact_untight — pairs failing exact dual feasibility, and matched pairs not exactly tight.
structurally_valid_matching — logical; no column claimed twice, no forbidden pair matched, no index out of range. Unmatched rows are permitted, so this holds for a partial matching.
all_rows_matched — logical; every row of the short side holds a column.
primal_feasible — logical; both of the two above. The primal constrains every row of the short side to hold exactly one pair, so a partial matching is a valid matching and not a feasible solution, and no conclusion rests on it. primal_objective is still reported for one, since an unmatched row costs nothing and leaves the sum meaningful.
dual_feasible — logical; c_ij - u_i - v_j >= -tol over every admissible pair, and, when there are more columns than rows, v_j <= tol for every column.
complementary_slackness — logical; both halves.
cs_matched_tight, cs_unmatched_free — the two halves separately.
primal_objective, dual_objective, duality_gap — numeric.
max_suboptimality — numeric; the most any feasible solution can beat this one by, in the cost unit. It adds to the duality gap the slack the dual conditions were allowed: n_rows times the depth the reduced costs were permitted below zero, plus, where the sign condition applies, n_cols times the height the column duals were permitted above it, plus an envelope for each objective's own rounding. Compensated summation buys back the accumulation error rather than removing it, so each sum is charged ⁠(2u + gamma_n^2)⁠ times the sum of its terms' magnitudes and the assembly is rounded outward at every step. The number is an upper bound in double arithmetic and not an estimate of one. It is zero only where every one of those terms is exactly zero, which is what certified_optimal reports. NA when primal_feasible is FALSE: the quantity is what a feasible solution can beat this one by, and there is no answer for a candidate that is not one.
certified_reduced_cost_floor — numeric; the lower bound proved for the reduced cost of every admissible pair, the ones never evaluated included. Equal to min_reduced_cost when every pair was visited, and below it when a pruning pricer proved only its own threshold.
min_reduced_cost, worst_i, worst_j — the most violated pair, if any.
max_matched_slack, max_v_unmatched, max_v — the quantities the slackness and sign conditions bound.
n_matched, n_rows, n_cols, transposed, tolerance.

Invisibly returns x.

What the certificate proves

The conditions are decided in one of two arithmetics, and the certificate says which one it used.

An exact certificate decides every condition in exact arithmetic, with no tolerance anywhere. It proves that the matching attains the minimum total cost of the cost matrix as supplied. The three quantities in each condition are IEEE doubles, and a double is a rational number, so c_ij - u_i - v_j has an exact sign; the check evaluates that sign exactly rather than reading the sign of a rounded difference. A cost matrix that is itself a rounding of something else — Mahalanobis distances, say — is still certified as the matrix it is, which is the problem the solver was given.

A numerical certificate decides the same conditions within tol. It establishes optimality up to that tolerance and no further. It is what is available when the potentials are not exactly optimal for the matrix: a potential computed as c_ij - v_j misses exact tightness by the rounding of that subtraction, and a matched arc off by one unit in the last place is enough to put the exact conclusion out of reach.

Which of the two an instance supports is a property of the arithmetic that produced the potentials, so it is worth checking rather than assuming. Integer costs and costs drawn on the unit interval have given an exact certificate on every instance we have measured, across problem sizes, both orientations of a rectangular problem, and every solver. Costs that are themselves computed, such as Euclidean distances between covariate vectors, have given a numerical one, with matched arcs off by a relative 1e-16 to 1e-15.

The check needs dual variables. If x carries them (as assignment_duals() results do), they are used. Otherwise they are obtained by solving cost with assignment_duals(), which costs a second solve. Either way the duals are verified, not trusted: dual feasibility is checked over every admissible pair, so duals that do not certify anything cause the verification to fail rather than pass.

Optimal duals are shared by all optimal solutions of a linear program, so a matching from one solver can be certified against duals from another. That is what makes it possible to certify solvers that return no duals of their own.

Examples

set.seed(1)
cost <- matrix(runif(100), 10, 10)
verify_assignment(assignment(cost), cost)

# A rectangular problem, where the condition on unmatched columns bites.
# Passing the duals result reuses its duals instead of solving again.
rect <- matrix(runif(120), 6, 20)
verify_assignment(assignment_duals(rect), rect)

# Integer costs carry an integer optimal dual solution, so the conditions
# hold with no tolerance and the certificate is exact.
int_cost <- matrix(sample(1:100, 64, replace = TRUE), 8, 8)
cert <- verify_assignment(assignment(int_cost), int_cost)
cert$arithmetic

couplr documentation built on Sept. 17, 2026, 1:08 a.m.