Relations

mixle.relations describes ranked feasible sets over structured spaces. A relation is not merely an optimization problem. The single best solution is often useful, but the full ranked set is the real object: assignments in increasing cost, strings outward from an edit-distance center, k-best Viterbi paths, shortest paths, spanning trees, feature subsets, stable matchings, graph cuts, and related combinatorial structures.

The common surface is deliberately small:

relation.solve()       # best Solution or None
relation.top(k)        # k best Solutions
relation.enumerator()  # lazy iterator, best first

Every result is a Solution(value, objective). value is the structured object itself; objective is the cost or score used for ranking.

Why Relations Belong In Mixle

Heterogeneous probabilistic systems frequently need structured decisions:

  • assign observations to latent explanations;

  • enumerate plausible state paths;

  • search edits near a generated answer;

  • rank feature subsets under a regression objective;

  • enforce matching, flow, or graph constraints after a model produces scores.

Treating those as relations keeps the ranking and feasibility logic explicit. The probabilistic model can score evidence, while the relation layer can enumerate the structured objects that satisfy the constraint.

Assignment

Assignment ranks bipartite assignments by total cost.

from mixle.relations import Assignment

relation = Assignment([[1.0, 9.0], [9.0, 1.0]])
best = relation.solve()

assert best.value.tolist() == [0, 1]
assert best.objective == 2.0

alternatives = relation.top(3)

Use this when a model produces a cost matrix and the downstream decision must be one-to-one: entity resolution, worker-task assignment, latent component matching, or alignment across modalities.

Paths And Viterbi

ShortestPath and ViterbiPath expose best-first path enumeration. best_first_paths is the lower-level engine for custom state graphs.

Use this when you need more than the best path:

  • compare the top few hidden-state explanations;

  • estimate ambiguity in a decoded sequence;

  • present alternative routes or derivations;

  • search a trellis lazily until enough probability mass has been covered.

The distinction from a normal sampler is important. A relation enumerator is ranked by objective. It is the right tool when you need the best alternatives, not random alternatives.

Edit-Distance Neighborhoods

EditDistance and nearest_first enumerate states outward from a center. This supports workflows like:

  • spelling or normalization alternatives;

  • local robustness checks around a generated string;

  • approximate matching against a structured vocabulary;

  • bounded repair of malformed identifiers.

Because the iterator is lazy, callers can request only the first few neighbors or stop at a distance threshold.

Spanning Trees And Graph Relations

SpanningTree ranks spanning trees by edge objective. Additional graph helpers include:

  • max_flow and min_cut;

  • min_arborescence;

  • graph_coloring;

  • max_clique and max_independent_set;

  • tsp_held_karp.

These are useful when a probabilistic model estimates local scores but the valid output has a global graph constraint.

Regression And MILP Helpers

BestSubsetRegression ranks feature subsets. The module also includes bounded and cardinality-constrained optimization helpers:

  • branch_and_bound_milp;

  • cardinality_constrained_milp;

  • admm_bounded_least_squares;

  • irreducible_infeasible_subset.

Use these when you need a constrained explanation, sparse decision rule, or debugging pass for infeasible linear constraints.

Stable Matching

stable_matching implements proposer-optimal Gale-Shapley matching. is_stable_matching verifies that a candidate matching has no blocking pair.

This is a decision layer, not a probabilistic estimator. It pairs naturally with Mixle when preference scores are model outputs but the final assignment must satisfy a stable matching constraint.

Relations And Probability

Relations do not replace distributions. They complement them:

  • A distribution scores or samples observations.

  • A relation enumerates feasible structured decisions.

  • An inference loop can use both: model scores become relation costs, and relation alternatives become candidate explanations.

For example, an HMM can estimate transition and emission probabilities, while ViterbiPath enumerates the best latent paths. A record model can score entity-pair likelihoods, while Assignment enforces a one-to-one matching.

Operational Guidance

Use relations when all three are true:

  1. The output is structured.

  2. Feasibility matters globally.

  3. The top alternatives are more useful than independent samples.

Use distributions or samplers when uncertainty over the full support matters more than ranked feasibility. Use Enumeration and Ranking when the object is a probability distribution with enumerable support. Use mixle.relations when the object is a constrained structured space with an objective.