API REFERENCE/omnibias-discrete

omnibias.discrete

0.1.0a2AlphaPython >=3.10AGPL / commercial

Shared discrete-problem contracts, annealed relaxations, hard decoders, and optimality-gap evidence.

import omnibias.discrete

Use discrete to connect a represented discrete problem with a supported relaxation, optimization procedure, and decoder. A smooth relaxed iterate, a feasible hard assignment, and a certified optimum are distinct outcomes.

Annealing changes the surrogate landscape. More aggressive hardening does not guarantee convergence to the global discrete optimum. Local-search decoders and brute-force oracles have different scaling; use tiny exhaustive cases to validate energy conventions and decoder behavior.

When reporting an optimality gap, preserve both the feasible upper bound and the valid lower bound, with the assumptions of the bound construction. A solver's heuristic value alone is not an optimality certificate. Parameter shapes, Boolean-variable encoding, objective sign, and reduction conventions are part of the problem contract. This alpha package uses AGPL-or-commercial licensing.

Module contract & mathematical conventions

Differentiable discrete relaxation, decoding, and certified optimality gaps.

The DiscreteProblem protocol supplies an energy and polynomial representation. Annealing uses its closed-form gradient; decoding supplies an upper bound and optional SOS certificates supply a lower bound. The supported result is a certified gap; a zero gap requires matching bounds.

Temperature collapse hardens sigmoid(beta z) for feasibility as beta grows. This differs from founding bias collapse, the delta -> 0 derivative limit. Use matching dtypes and JAX_ENABLE_X64=1 for float64 comparisons.

Shared formulas do not imply universal floating-point identity. Verify dtype, shape, derivative-order support, and the stated numerical assumptions for the path you use.

Module source ↗Source revision 9a2d73df0573Running reference examples →

certifyModule ↗jaxModule ↗matroidModule ↗proposersModule ↗torchModule ↗

Imports & aliases

These names share a definition with another public module. Follow a name for its full contract, parameters, and examples.

Import from this module	Canonical reference
AnnealDescentProposer	omnibias.discrete.AnnealDescentProposer
TightenedGap	omnibias.discrete.TightenedGap
certify_gap	omnibias.discrete.certify_gap
tighten_gap	omnibias.discrete.tighten_gap

FUNCTION

gershgorin_min_eig_lower

omnibias.discrete.gershgorin_min_eig_lowerSource ↗

gershgorin_min_eig_lower(matrix: FloatArray) -> float

A lower bound on the smallest eigenvalue of a symmetric matrix (Gershgorin).

Parameters

Name	Type & default	Contract
matrixpositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.

Returnsfloat

Executed regression · gershgorin bounds the smallest eigenvalue

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_gershgorin_bounds_the_smallest_eigenvalue() -> None:
    rng = np.random.default_rng(0)
    for _ in range(10):
        m = rng.standard_normal((5, 5))
        sym = m + m.T
        assert gershgorin_min_eig_lower(sym) <= float(np.min(np.linalg.eigvalsh(sym))) + 1e-9

python -m pytest "packages/omnibias-discrete/tests/test_bound.py::test_gershgorin_bounds_the_smallest_eigenvalue" -q

Read the implementation

def gershgorin_min_eig_lower(matrix: FloatArray) -> float:
    r"""A lower bound on the smallest eigenvalue of a symmetric matrix (Gershgorin)."""
    m = np.asarray(matrix, dtype=float)
    diag = np.diag(m)
    off = np.sum(np.abs(m), axis=1) - np.abs(diag)
    return float(np.min(diag - off))

FUNCTION

lasserre_lower_bound

omnibias.discrete.lasserre_lower_boundSource ↗

lasserre_lower_bound(problem: DiscreteProblem, *, level: int, seed_lower: float, upper: float, steps: int=24, claim_label: str='energy') -> tuple[float, Cert] | None

The certified Lasserre / SOS lower bound on the minimum energy, or None.

Bisects gamma in [seed_lower, upper] (both valid brackets around the SOS bound), certifying E - gamma >= 0 on the Boolean hypercube at each step; returns the largest proved gamma with a hash-sealed v1 certificate, or None if omnibias-sos is unavailable or no gamma could be proved. claim_label is the human-readable subject of the sealed claim (e.g. "QUBO energy").

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
levelkeyword-only	intRequired	See the operation contract and implementation below.
seed_lowerkeyword-only	floatRequired	See the operation contract and implementation below.
upperkeyword-only	floatRequired	See the operation contract and implementation below.
stepskeyword-only	intDefault: 24	See the operation contract and implementation below.
claim_labelkeyword-only	strDefault: 'energy'	See the operation contract and implementation below.

Returnstuple[float, Cert] | None

Executed regression · sos bound is sealed

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sos_bound_is_sealed(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    prob = make_toy([[1.0, -1.0], [-1.0, 1.0]])  # E = (x0 - x1)^2
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment, level=1, bisection_steps=24)
    assert cert.method == "sos"
    assert cert.certified is True and cert.sealed is not None and cert.level == 1

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_sos_bound_is_sealed" -q

Regression example · lasserre bound is sound and sealed

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_lasserre_bound_is_sound_and_sealed(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    prob = make_toy([[1.0, -1.0], [-1.0, 1.0]])  # E = (x0 - x1)^2 >= 0 on the cube
    _, e_min = brute_force_min(prob)
    floor = negative_coeff_lower_bound(prob.to_polynomial())
    result = lasserre_lower_bound(prob, level=1, seed_lower=floor, upper=e_min + 1.0, steps=24)
    assert result is not None
    gamma, sealed = result
    assert gamma <= e_min + 1e-6  # valid lower bound
    assert gamma >= floor - 1e-9  # and at least as tight as the trivial floor
    assert sealed is not None

python -m pytest packages/omnibias-discrete/tests/test_bound.py -k test_lasserre_bound_is_sound_and_sealed -q

Read the implementation

def lasserre_lower_bound(
    problem: DiscreteProblem,
    *,
    level: int,
    seed_lower: float,
    upper: float,
    steps: int = 24,
    claim_label: str = "energy",
) -> tuple[float, Cert] | None:
    r"""The certified Lasserre / SOS lower bound on the minimum energy, or ``None``.

    Bisects ``gamma in [seed_lower, upper]`` (both valid brackets around the SOS bound),
    certifying ``E - gamma >= 0`` on the Boolean hypercube at each step; returns the
    largest proved ``gamma`` with a hash-sealed v1 certificate, or ``None`` if
    ``omnibias-sos`` is unavailable or no ``gamma`` could be proved. ``claim_label`` is
    the human-readable subject of the sealed claim (e.g. ``"QUBO energy"``).
    """
    try:
        from omnibias.sos import (
            certify_nonneg_on_set,
            seal_positivstellensatz_certificate,
        )
    except ImportError:
        return None

    energy_poly = problem.to_polynomial()
    cons = boolean_constraints(problem.n)

    lo, hi = float(seed_lower), float(upper)
    best_gamma: float | None = None
    best_cert = None
    for _ in range(max(steps, 1)):
        mid = 0.5 * (lo + hi)
        certificate = certify_nonneg_on_set(energy_poly - mid, cons, half_degree=level)
        if certificate.certified:
            best_gamma, best_cert = mid, certificate
            lo = mid
        else:
            hi = mid
    if best_gamma is None or best_cert is None:
        return None

    sealed = seal_positivstellensatz_certificate(
        best_cert,
        claim=(
            f"{claim_label} >= {best_gamma} for all x in {{0,1}}^{problem.n} "
            f"(Lasserre / Putinar level {level})"
        ),
    )
    return best_gamma, sealed

Related APIsomnibias.discrete.boolean_constraints↗

FUNCTION

negative_coeff_lower_bound

omnibias.discrete.negative_coeff_lower_boundSource ↗

negative_coeff_lower_bound(poly: Polynomial) -> float

The sum of the polynomial's negative coefficients -- a valid floor on {0,1}^n.

On the cube every monomial x^alpha in {0, 1} subseteq [0, 1], so the positive terms contribute >= 0 and each negative term c_alpha x^alpha >= c_alpha; hence E(x) >= sum_{c_alpha < 0} c_alpha for all x in {0, 1}^n. Cheap and always sound (not interval-sealed, so certificates label it certified=False).

Parameters

Name	Type & default	Contract
polypositional-or-keyword	PolynomialRequired	See the operation contract and implementation below.

Returnsfloat

Executed regression · sos bound is sealed

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sos_bound_is_sealed(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    prob = make_toy([[1.0, -1.0], [-1.0, 1.0]])  # E = (x0 - x1)^2
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment, level=1, bisection_steps=24)
    assert cert.method == "sos"
    assert cert.certified is True and cert.sealed is not None and cert.level == 1

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_sos_bound_is_sealed" -q

Regression example · negative coeff bound is sound over the cube

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_negative_coeff_bound_is_sound_over_the_cube(make_toy) -> None:  # type: ignore[no-untyped-def]
    rng = np.random.default_rng(2)
    for _ in range(8):
        m = rng.standard_normal((4, 4))
        prob = make_toy(m + m.T, c=rng.standard_normal(4), const=float(rng.standard_normal()))
        floor = negative_coeff_lower_bound(prob.to_polynomial())
        _, e_min = brute_force_min(prob)
        assert floor <= e_min + 1e-9  # never exceeds the true minimum

python -m pytest packages/omnibias-discrete/tests/test_bound.py -k test_negative_coeff_bound_is_sound_over_the_cube -q

Read the implementation

def negative_coeff_lower_bound(poly: Polynomial) -> float:
    r"""The sum of the polynomial's negative coefficients -- a valid floor on ``{0,1}^n``.

    On the cube every monomial ``x^alpha in {0, 1} subseteq [0, 1]``, so the positive
    terms contribute ``>= 0`` and each negative term ``c_alpha x^alpha >= c_alpha``;
    hence ``E(x) >= sum_{c_alpha < 0} c_alpha`` for all ``x in {0, 1}^n``. Cheap and
    always sound (not interval-sealed, so certificates label it ``certified=False``).
    """
    return float(sum(c for c in poly.coeffs.values() if c < 0.0))

FUNCTION

mean_normalized_regret

omnibias.discrete.mean_normalized_regretSource ↗

mean_normalized_regret(cost_pred: FloatArray, cost_true: FloatArray, opt: FloatArray, decision_cost: Callable[[FloatArray, FloatArray], float]) -> float

Mean decision regret normalized by the mean true optimum.

For each instance b of a (B, ...) batch, decision_cost(cost_pred[b], cost_true[b]) is the *true* cost of the decision decoded from the predicted cost; subtracting the true optimum opt[b] gives the per-instance regret. Returns mean(regret) / max(mean(opt), eps) (eps = 1e-12), which is 0 exactly at oracle-optimal decisions.

Parameters

Name	Type & default	Contract
cost_predpositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.
cost_truepositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.
optpositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.
decision_costpositional-or-keyword	Callable[[FloatArray, FloatArray], float]Required	See the operation contract and implementation below.

Returnsfloat

Executed regression · mean normalized regret zero at optimum

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_mean_normalized_regret_zero_at_optimum() -> None:
    opt = np.array([2.0, 4.0, 6.0])
    true = np.stack([opt, np.zeros(3)], axis=1)  # true[b, 0] encodes the per-instance optimum
    pred = np.zeros((3, 2))
    result = mean_normalized_regret(pred, true, opt, lambda _p, t: float(t[0]))
    assert result == pytest.approx(0.0)

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_mean_normalized_regret_zero_at_optimum" -q

Regression example · mean normalized regret normalizes mean excess

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_mean_normalized_regret_normalizes_mean_excess() -> None:
    opt = np.array([2.0, 4.0])
    excess = np.array([0.5, 1.5])
    true = np.stack([opt + excess, np.zeros(2)], axis=1)
    pred = np.zeros((2, 2))
    result = mean_normalized_regret(pred, true, opt, lambda _p, t: float(t[0]))
    assert result == pytest.approx(float(np.mean(excess) / np.mean(opt)))

python -m pytest packages/omnibias-discrete/tests/test_shared.py -k test_mean_normalized_regret_normalizes_mean_excess -q

Read the implementation

def mean_normalized_regret(
    cost_pred: FloatArray,
    cost_true: FloatArray,
    opt: FloatArray,
    decision_cost: Callable[[FloatArray, FloatArray], float],
) -> float:
    r"""Mean decision regret normalized by the mean true optimum.

    For each instance ``b`` of a ``(B, ...)`` batch, ``decision_cost(cost_pred[b], cost_true[b])``
    is the *true* cost of the decision decoded from the predicted cost; subtracting the true
    optimum ``opt[b]`` gives the per-instance regret. Returns ``mean(regret) / max(mean(opt), eps)``
    (``eps = 1e-12``), which is ``0`` exactly at oracle-optimal decisions.
    """
    regrets = [
        decision_cost(cost_pred[b], cost_true[b]) - opt[b] for b in range(cost_pred.shape[0])
    ]
    return float(np.mean(regrets) / max(float(np.mean(opt)), 1e-12))

FUNCTION

spo_plus_subgradient

omnibias.discrete.spo_plus_subgradientSource ↗

spo_plus_subgradient(cost_pred: FloatArray, cost_true: FloatArray, oracle: Callable[[FloatArray], FloatArray]) -> FloatArray

SPO+ subgradient over a (B, ...) batch given an exact linear oracle x^*(c).

cost_pred and cost_true are equal-shaped (B, ...) cost tensors; oracle maps a single instance's cost (...) to its optimal-decision indicator of the same shape. Returns the (B, ...) subgradient 2 (x^*(c_true) - x^*(2 c_pred - c_true)). The oracle's optimization direction (min- or max-cost) is the caller's choice; the SPO+ identity is unchanged either way.

Parameters

Name	Type & default	Contract
cost_predpositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.
cost_truepositional-or-keyword	FloatArrayRequired	See the operation contract and implementation below.
oraclepositional-or-keyword	Callable[[FloatArray], FloatArray]Required	See the operation contract and implementation below.

ReturnsFloatArray

Executed regression · spo plus subgradient is zero when pred equals true

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_spo_plus_subgradient_is_zero_when_pred_equals_true() -> None:
    rng = np.random.default_rng(0)
    c = rng.standard_normal((4, 5))  # 2 pred - true == c, so both oracle calls agree
    np.testing.assert_allclose(spo_plus_subgradient(c, c, _argmin_onehot), 0.0)

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_spo_plus_subgradient_is_zero_when_pred_equals_true" -q

Regression example · spo plus subgradient matches hand computation

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_spo_plus_subgradient_matches_hand_computation() -> None:
    pred = np.array([[1.0, 2.0, 3.0]])
    true = np.array([[3.0, 2.0, 1.0]])
    # x*(true) selects index 2; x*(2 pred - true) = x*([-1, 2, 5]) selects index 0.
    grad = spo_plus_subgradient(pred, true, _argmin_onehot)
    np.testing.assert_allclose(grad, [[-2.0, 0.0, 2.0]])

python -m pytest packages/omnibias-discrete/tests/test_shared.py -k test_spo_plus_subgradient_matches_hand_computation -q

Read the implementation

def spo_plus_subgradient(
    cost_pred: FloatArray,
    cost_true: FloatArray,
    oracle: Callable[[FloatArray], FloatArray],
) -> FloatArray:
    r"""SPO+ subgradient over a ``(B, ...)`` batch given an exact linear oracle ``x^*(c)``.

    ``cost_pred`` and ``cost_true`` are equal-shaped ``(B, ...)`` cost tensors; ``oracle`` maps a
    single instance's cost ``(...)`` to its optimal-decision indicator of the same shape. Returns
    the ``(B, ...)`` subgradient ``2 (x^*(c_true) - x^*(2 c_pred - c_true))``. The oracle's
    optimization direction (min- or max-cost) is the caller's choice; the SPO+ identity is
    unchanged either way.
    """
    grad = np.zeros_like(cost_pred)
    for b in range(cost_pred.shape[0]):
        x_true = oracle(cost_true[b])
        x_spo = oracle(2.0 * cost_pred[b] - cost_true[b])
        grad[b] = 2.0 * (x_true - x_spo)
    return grad

FUNCTION

brute_force_min

omnibias.discrete.brute_force_minSource ↗

brute_force_min(problem: DiscreteProblem, *, max_n: int=_MAX_EXACT_N) -> tuple[tuple[int, ...], float]

Exact minimum-energy binary point by enumerating all 2^n assignments.

Exponential (O(2^n) energy evaluations); intended as the small-n oracle that self-checks the certificate sandwich. Raises ValueError for n > max_n.

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
max_nkeyword-only	intDefault: _MAX_EXACT_N	See the operation contract and implementation below.

Returnstuple[tuple[int, ...], float]

Explicit validation & failure cases

• When n > max_n, raises ValueError(f'brute_force_min is exponential (O(2^n)); n={n} exceeds the {max_n} cap. Use decode + certify_gap for a certified heuristic instead.').

These are explicit source guards. Backend operations may also raise for invalid shapes, dtypes, or unsupported devices.

Executed regression · negative coeff bound is sound over the cube

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_negative_coeff_bound_is_sound_over_the_cube(make_toy) -> None:  # type: ignore[no-untyped-def]
    rng = np.random.default_rng(2)
    for _ in range(8):
        m = rng.standard_normal((4, 4))
        prob = make_toy(m + m.T, c=rng.standard_normal(4), const=float(rng.standard_normal()))
        floor = negative_coeff_lower_bound(prob.to_polynomial())
        _, e_min = brute_force_min(prob)
        assert floor <= e_min + 1e-9  # never exceeds the true minimum

python -m pytest "packages/omnibias-discrete/tests/test_bound.py::test_negative_coeff_bound_is_sound_over_the_cube" -q

Regression example · brute force is labelled exponential

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_brute_force_is_labelled_exponential() -> None:
    doc = (discrete.brute_force_min.__doc__ or "").lower()
    assert "exponential" in doc or "2^n" in doc

python -m pytest packages/omnibias-discrete/tests/test_scope.py -k test_brute_force_is_labelled_exponential -q

Read the implementation

def brute_force_min(
    problem: DiscreteProblem, *, max_n: int = _MAX_EXACT_N
) -> tuple[tuple[int, ...], float]:
    r"""Exact minimum-energy binary point by enumerating all ``2^n`` assignments.

    Exponential (``O(2^n)`` energy evaluations); intended as the small-``n`` oracle that
    self-checks the certificate sandwich. Raises :class:`ValueError` for ``n > max_n``.
    """
    n = problem.n
    if n > max_n:
        raise ValueError(
            f"brute_force_min is exponential (O(2^n)); n={n} exceeds the {max_n} cap. "
            "Use decode + certify_gap for a certified heuristic instead."
        )
    idx = np.arange(1 << n, dtype=np.int64)
    bits = (idx[:, None] >> np.arange(n)[None, :]) & 1
    x = bits.astype(float)
    e = np.asarray(problem.energy(x), dtype=float)
    best = int(np.argmin(e))
    return tuple(int(v) for v in x[best]), float(e[best])

FUNCTION

decode

omnibias.discrete.decodeSource ↗

decode(problem: DiscreteProblem, *, relaxed: object | None=None, n_starts: int=8, seed: int=0) -> tuple[tuple[int, ...], float]

Round + local-search a problem to a valid binary point (an *upper* bound).

Starts from the rounded relaxed assignment (when given), the all-zero point, and n_starts deterministic random binary points; each is refined by one_flip_descent and the best is returned as (assignment, energy).

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
relaxedkeyword-only	object | NoneDefault: None	See the operation contract and implementation below.
n_startskeyword-only	intDefault: 8	See the operation contract and implementation below.
seedkeyword-only	intDefault: 0	See the operation contract and implementation below.

Returnstuple[tuple[int, ...], float]

Executed regression · sos bound is sealed

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sos_bound_is_sealed(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    prob = make_toy([[1.0, -1.0], [-1.0, 1.0]])  # E = (x0 - x1)^2
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment, level=1, bisection_steps=24)
    assert cert.method == "sos"
    assert cert.certified is True and cert.sealed is not None and cert.level == 1

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_sos_bound_is_sealed" -q

Regression example · degrades gracefully without sos

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_degrades_gracefully_without_sos(make_toy, monkeypatch: pytest.MonkeyPatch) -> None:  # type: ignore[no-untyped-def]
    monkeypatch.setitem(sys.modules, "omnibias.sos", None)
    prob = make_toy([[0.0, -1.0], [-1.0, 0.0]], c=[0.5, 0.5])
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment)
    assert cert.method == "none"  # degraded, not crashed
    assert math.isinf(cert.lower_bound) and cert.lower_bound < 0
    assert cert.certified is False and cert.is_sound

python -m pytest packages/omnibias-discrete/tests/test_certify.py -k test_degrades_gracefully_without_sos -q

Read the implementation

def decode(
    problem: DiscreteProblem,
    *,
    relaxed: object | None = None,
    n_starts: int = 8,
    seed: int = 0,
) -> tuple[tuple[int, ...], float]:
    r"""Round + local-search a problem to a valid binary point (an *upper* bound).

    Starts from the rounded ``relaxed`` assignment (when given), the all-zero point, and
    ``n_starts`` deterministic random binary points; each is refined by
    :func:`one_flip_descent` and the best is returned as ``(assignment, energy)``.
    """
    n = problem.n
    rng = np.random.default_rng(seed)
    starts: list[FloatArray] = [np.zeros(n)]
    if relaxed is not None:
        starts.append(round_relaxed(relaxed))
    for _ in range(max(n_starts, 0)):
        starts.append(rng.integers(0, 2, size=n).astype(float))

    best_x: FloatArray | None = None
    best_e = np.inf
    for start in starts:
        x, e = one_flip_descent(problem, start)
        if e < best_e:
            best_x, best_e = x, e
    assert best_x is not None
    return tuple(int(v) for v in best_x), float(best_e)

Related APIsomnibias.discrete.one_flip_descent↗omnibias.discrete.round_relaxed↗

FUNCTION

energy

omnibias.discrete.energySource ↗

energy(problem: DiscreteProblem, x: object) -> float | FloatArray

The energy of x under problem (delegates to problem.energy).

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
xpositional-or-keyword	objectRequired	See the operation contract and implementation below.

Returnsfloat | FloatArray

Read the implementation

def energy(problem: DiscreteProblem, x: object) -> float | FloatArray:
    """The energy of ``x`` under ``problem`` (delegates to ``problem.energy``)."""
    result: float | FloatArray = problem.energy(x)
    return result

FUNCTION

flip_deltas

omnibias.discrete.flip_deltasSource ↗

flip_deltas(problem: DiscreteProblem, x: object) -> FloatArray

The energy change for flipping each single bit of x.

Uses problem.flip_deltas when the problem provides that closed-form fast path, otherwise evaluates the n single-flip neighbours in one batched energy call and subtracts the base energy.

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
xpositional-or-keyword	objectRequired	See the operation contract and implementation below.

ReturnsFloatArray

Executed regression · one flip descent reaches a local minimum

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_one_flip_descent_reaches_a_local_minimum(make_toy) -> None:  # type: ignore[no-untyped-def]
    prob = make_toy([[0.0, -2.0], [-2.0, 0.0]], c=[1.0, 1.0])
    x, e = one_flip_descent(prob, np.array([1.0, 0.0]))
    assert e == pytest.approx(float(prob.energy(x)))
    assert np.all(flip_deltas(prob, x) >= -1e-9)  # no single flip improves

python -m pytest "packages/omnibias-discrete/tests/test_decode.py::test_one_flip_descent_reaches_a_local_minimum" -q

Regression example · fast path matches the generic fallback

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_fast_path_matches_the_generic_fallback(make_toy) -> None:  # type: ignore[no-untyped-def]
    rng = np.random.default_rng(7)
    m = rng.standard_normal((6, 6))
    Q, c = m + m.T, rng.standard_normal(6)
    fast = make_toy(Q, c=c)
    slow = make_toy(Q, c=c, fast=False)
    assert not hasattr(slow, "flip_deltas")  # forces the batched-energy fallback
    # Closed-form flip deltas and the batched-energy fallback agree bit-for-bit-ish.
    x = rng.integers(0, 2, size=6).astype(float)
    assert np.allclose(flip_deltas(fast, x), flip_deltas(slow, x), atol=1e-9)
    assert decode(fast, seed=1) == decode(slow, seed=1)

python -m pytest packages/omnibias-discrete/tests/test_decode.py -k test_fast_path_matches_the_generic_fallback -q

Read the implementation

def flip_deltas(problem: DiscreteProblem, x: object) -> FloatArray:
    r"""The energy change for flipping each single bit of ``x``.

    Uses ``problem.flip_deltas`` when the problem provides that closed-form fast path,
    otherwise evaluates the ``n`` single-flip neighbours in one batched ``energy`` call
    and subtracts the base energy.
    """
    fast = getattr(problem, "flip_deltas", None)
    if fast is not None:
        return np.asarray(fast(x), dtype=float)
    xv = np.asarray(x, dtype=float)
    n = problem.n
    base = float(problem.energy(xv))
    neighbours = np.tile(xv, (n, 1))
    diag = np.arange(n)
    neighbours[diag, diag] = 1.0 - neighbours[diag, diag]
    neigh_energy = np.asarray(problem.energy(neighbours), dtype=float)
    return neigh_energy - base

FUNCTION

is_binary

omnibias.discrete.is_binarySource ↗

is_binary(x: object, *, tol: float=1e-09) -> bool

Whether every entry of x is within tol of 0 or 1.

Parameters

Name	Type & default	Contract
xpositional-or-keyword	objectRequired	See the operation contract and implementation below.
tolkeyword-only	floatDefault: 1e-09	See the operation contract and implementation below.

Returnsbool

Executed regression · rejects a non binary point

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_rejects_a_non_binary_point(make_toy) -> None:  # type: ignore[no-untyped-def]
    prob = make_toy([[1.0, 0.0], [0.0, 1.0]])
    with pytest.raises(ValueError, match="binary"):
        certify_gap(prob, np.array([0.5, 0.5]))

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_rejects_a_non_binary_point" -q

Regression example · is binary and round relaxed

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_binary_and_round_relaxed() -> None:
    assert is_binary(np.array([0.0, 1.0, 0.0]))
    assert not is_binary(np.array([0.5, 1.0]))
    assert np.array_equal(round_relaxed(np.array([0.4, 0.5, 0.9])), np.array([0.0, 1.0, 1.0]))

python -m pytest packages/omnibias-discrete/tests/test_decode.py -k test_is_binary_and_round_relaxed -q

Read the implementation

def is_binary(x: object, *, tol: float = 1e-9) -> bool:
    """Whether every entry of ``x`` is within ``tol`` of ``0`` or ``1``."""
    xv = np.asarray(x, dtype=float)
    return bool(np.all((np.abs(xv) < tol) | (np.abs(xv - 1.0) < tol)))

FUNCTION

one_flip_descent

omnibias.discrete.one_flip_descentSource ↗

one_flip_descent(problem: DiscreteProblem, x0: object) -> tuple[FloatArray, float]

Greedy single-bit-flip descent from x0 to a 1-flip-local minimum.

x0 is rounded to {0, 1} first; each step flips the most energy-decreasing bit until no single flip improves. Returns (x, energy).

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	See the operation contract and implementation below.
x0positional-or-keyword	objectRequired	See the operation contract and implementation below.

Returnstuple[FloatArray, float]

Executed regression · one flip descent reaches a local minimum

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_one_flip_descent_reaches_a_local_minimum(make_toy) -> None:  # type: ignore[no-untyped-def]
    prob = make_toy([[0.0, -2.0], [-2.0, 0.0]], c=[1.0, 1.0])
    x, e = one_flip_descent(prob, np.array([1.0, 0.0]))
    assert e == pytest.approx(float(prob.energy(x)))
    assert np.all(flip_deltas(prob, x) >= -1e-9)  # no single flip improves

python -m pytest "packages/omnibias-discrete/tests/test_decode.py::test_one_flip_descent_reaches_a_local_minimum" -q

Read the implementation

def one_flip_descent(problem: DiscreteProblem, x0: object) -> tuple[FloatArray, float]:
    r"""Greedy single-bit-flip descent from ``x0`` to a 1-flip-local minimum.

    ``x0`` is rounded to ``{0, 1}`` first; each step flips the most energy-decreasing
    bit until no single flip improves. Returns ``(x, energy)``.
    """
    x = round_relaxed(x0)
    while True:
        delta = flip_deltas(problem, x)
        i = int(np.argmin(delta))
        if delta[i] >= -1e-12:
            break
        x[i] = 1.0 - x[i]
    return x, float(problem.energy(x))

Related APIsomnibias.discrete.flip_deltas↗omnibias.discrete.round_relaxed↗

FUNCTION

round_relaxed

omnibias.discrete.round_relaxedSource ↗

round_relaxed(x: object) -> FloatArray

Round a soft assignment to {0, 1} at the 0.5 threshold.

Parameters

Name	Type & default	Contract
xpositional-or-keyword	objectRequired	See the operation contract and implementation below.

ReturnsFloatArray

Executed regression · is binary and round relaxed

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_binary_and_round_relaxed() -> None:
    assert is_binary(np.array([0.0, 1.0, 0.0]))
    assert not is_binary(np.array([0.5, 1.0]))
    assert np.array_equal(round_relaxed(np.array([0.4, 0.5, 0.9])), np.array([0.0, 1.0, 1.0]))

python -m pytest "packages/omnibias-discrete/tests/test_decode.py::test_is_binary_and_round_relaxed" -q

Read the implementation

def round_relaxed(x: object) -> FloatArray:
    """Round a soft assignment to ``{0, 1}`` at the ``0.5`` threshold."""
    return (np.asarray(x, dtype=float) >= 0.5).astype(float)

CLASS

DiscreteProblem

omnibias.discrete.DiscreteProblemSource ↗

class DiscreteProblem(Protocol)

A pseudo-Boolean minimization problem over x in {0, 1}^n.

Required surface

n: The number of binary variables. energy(x): The objective at one point (n,) or a batch (m, n); returns a float for a single point and an (m,) array for a batch. Minimizing energy is the problem. to_polynomial(): The energy as an omnibias.sos.Polynomial over n variables, used by the certified Lasserre lower bound.

Optional fast path

flip_deltas(x): The vector of energy changes E(x with bit i flipped) - E(x) for every i. When present the local-search decoder uses it instead of the generic batched-energy fallback (e.g. QUBO has a one-matvec closed form).

Fields & methods

nproperty

n(self) -> int

See the class contract above and the exact method implementation below.

Returns: int

Method implementation

    def n(self) -> int: ...

View source ↗

energymethod

energy(self, x: object) -> float | FloatArray

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
xpositional-or-keyword	objectRequired	See the operation contract and implementation below.

Returns: float | FloatArray

Method implementation

    def energy(self, x: object) -> float | FloatArray: ...

View source ↗

to_polynomialmethod

to_polynomial(self) -> Polynomial

See the class contract above and the exact method implementation below.

Returns: Polynomial

Method implementation

    def to_polynomial(self) -> Polynomial: ...

View source ↗

Read the implementation

class DiscreteProblem(Protocol):
    r"""A pseudo-Boolean minimization problem over ``x in {0, 1}^n``.

    Required surface
    ----------------
    n:
        The number of binary variables.
    energy(x):
        The objective at one point ``(n,)`` or a batch ``(m, n)``; returns a ``float``
        for a single point and an ``(m,)`` array for a batch. Minimizing ``energy`` is
        the problem.
    to_polynomial():
        The energy as an :class:`omnibias.sos.Polynomial` over ``n`` variables, used by
        the certified Lasserre lower bound.

    Optional fast path
    ------------------
    flip_deltas(x):
        The vector of energy changes ``E(x with bit i flipped) - E(x)`` for every ``i``.
        When present the local-search decoder uses it instead of the generic
        batched-energy fallback (e.g. QUBO has a one-matvec closed form).
    """

    @property
    def n(self) -> int: ...

    def energy(self, x: object) -> float | FloatArray: ...

    def to_polynomial(self) -> Polynomial: ...

FUNCTION

boolean_constraints

omnibias.discrete.boolean_constraintsSource ↗

boolean_constraints(n: int) -> list[Polynomial]

The Boolean-hypercube generators x_i - x_i^2 >= 0 and x_i^2 - x_i >= 0.

Together the two inequalities per variable pin x_i(1 - x_i) = 0, i.e. x_i in {0, 1} -- the semialgebraic description Putinar's Positivstellensatz uses to certify a lower bound on the minimum energy over the cube.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnslist[Polynomial]

Executed regression · sos bound is sealed

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sos_bound_is_sealed(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    prob = make_toy([[1.0, -1.0], [-1.0, 1.0]])  # E = (x0 - x1)^2
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment, level=1, bisection_steps=24)
    assert cert.method == "sos"
    assert cert.certified is True and cert.sealed is not None and cert.level == 1

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_sos_bound_is_sealed" -q

Read the implementation

def boolean_constraints(n: int) -> list[Polynomial]:
    r"""The Boolean-hypercube generators ``x_i - x_i^2 >= 0`` and ``x_i^2 - x_i >= 0``.

    Together the two inequalities per variable pin ``x_i(1 - x_i) = 0``, i.e.
    ``x_i in {0, 1}`` -- the semialgebraic description Putinar's Positivstellensatz uses
    to certify a lower bound on the minimum energy over the cube.
    """
    from omnibias.sos import Polynomial

    cons: list[Polynomial] = []
    for i in range(n):
        xi = Polynomial.variable(i, n)
        xi_sq = xi * xi
        cons.append(xi - xi_sq)
        cons.append(xi_sq - xi)
    return cons

CONSTANT

INIT_THETA_SCALE

omnibias.discrete.INIT_THETA_SCALESource ↗

INIT_THETA_SCALE = 0.01

Amplitude of the deterministic symmetry-breaking perturbation of theta_0.

Read the implementation

INIT_THETA_SCALE = 1e-2

FUNCTION

initial_theta

omnibias.discrete.initial_thetaSource ↗

initial_theta(n: int) -> NDArray[np.float64]

Deterministic initial theta_0 of length n (fixed seed, backend-shared).

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

ReturnsNDArray[np.float64]

Executed regression · output is in the unit box

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_output_is_in_the_unit_box() -> None:
    jnp = pytest.importorskip("jax.numpy")
    from omnibias.discrete.jax import anneal_descent as ja

    a, b, scale = _quadratic(2)
    aj, bj = jnp.asarray(a), jnp.asarray(b)
    x = np.asarray(ja(lambda z: 2.0 * (aj @ z) + bj, scale, a.shape[0]))
    assert np.all(x >= 0.0) and np.all(x <= 1.0) and np.all(np.isfinite(x))

python -m pytest "packages/omnibias-discrete/tests/test_relaxation.py::test_output_is_in_the_unit_box" -q

Read the implementation

def initial_theta(n: int) -> NDArray[np.float64]:
    """Deterministic initial ``theta_0`` of length ``n`` (fixed seed, backend-shared)."""
    rng = np.random.default_rng(0)
    return (INIT_THETA_SCALE * rng.standard_normal(n)).astype(float)

CLASS

AnnealSchedule

omnibias.discrete.AnnealScheduleSource ↗

class AnnealSchedule

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

Homotopy schedule for the differentiable annealed (temperature-collapse) relaxation.

The relaxation parametrises x = sigmoid(beta theta) in (0, 1)^n and descends the closed-form energy gradient by unrolled gradient descent along a geometric beta homotopy; as beta grows the soft assignment collapses onto a binary vertex. Defaults are eval-quality; fast is enough to train *through* the relaxation.

Attributes

beta0, beta_growth: Initial inverse-temperature and geometric growth factor per stage. stages: Number of homotopy stages (each warm-starts the next). steps: Gradient-descent steps per stage. step_safety: Fraction of the (closed-form Lipschitz) step to take (0 < step_safety <= 1).

Parameters

Name	Type & default	Contract
beta0dataclass field	floatDefault: 0.5	Initial inverse-temperature and geometric growth factor per stage.
beta_growthdataclass field	floatDefault: 1.5	See the operation contract and implementation below.
stagesdataclass field	intDefault: 12	Number of homotopy stages (each warm-starts the next).
stepsdataclass field	intDefault: 60	Gradient-descent steps per stage.
step_safetydataclass field	floatDefault: 0.9	Fraction of the (closed-form Lipschitz) step to take (0 < step_safety <= 1).

Executed regression · fast schedule is lighter

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_fast_schedule_is_lighter() -> None:
    assert AnnealSchedule.fast().stages < AnnealSchedule().stages

python -m pytest "packages/omnibias-discrete/tests/test_schedule.py::test_fast_schedule_is_lighter" -q

Regression example · invalid parameters raise

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_invalid_parameters_raise(kwargs: dict[str, float]) -> None:
    with pytest.raises(ValueError):
        AnnealSchedule(**kwargs)

python -m pytest packages/omnibias-discrete/tests/test_schedule.py -k test_invalid_parameters_raise -q

Fields & methods

beta0field

beta0: float = 0.5

Initial inverse-temperature and geometric growth factor per stage.

View source ↗

beta_growthfield

beta_growth: float = 1.5

Initial inverse-temperature and geometric growth factor per stage.

View source ↗

stagesfield

stages: int = 12

Number of homotopy stages (each warm-starts the next).

Regression example · betas are geometric and length matches stages

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_betas_are_geometric_and_length_matches_stages() -> None:
    sched = AnnealSchedule(beta0=0.5, beta_growth=2.0, stages=4)
    betas = sched.betas()
    assert betas == [0.5, 1.0, 2.0, 4.0]
    assert len(betas) == sched.stages

python -m pytest packages/omnibias-discrete/tests/test_schedule.py -k test_betas_are_geometric_and_length_matches_stages -q

View source ↗

stepsfield

steps: int = 60

Gradient-descent steps per stage.

View source ↗

step_safetyfield

step_safety: float = 0.9

Fraction of the (closed-form Lipschitz) step to take (0 < step_safety <= 1).

View source ↗

__post_init__method

__post_init__(self) -> None

See the class contract above and the exact method implementation below.

Returns: None

Validation & failure cases

• When self.beta0 <= 0.0, raises ValueError('beta0 must be > 0').
• When self.beta_growth < 1.0, raises ValueError('beta_growth must be >= 1').
• When self.stages < 1 or self.steps < 1, raises ValueError('stages and steps must be >= 1').
• When not 0.0 < self.step_safety <= 1.0, raises ValueError('step_safety must be in (0, 1]').

Executed regression · fast schedule is lighter

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_fast_schedule_is_lighter() -> None:
    assert AnnealSchedule.fast().stages < AnnealSchedule().stages

python -m pytest "packages/omnibias-discrete/tests/test_schedule.py::test_fast_schedule_is_lighter" -q

Method implementation

    def __post_init__(self) -> None:
        if self.beta0 <= 0.0:
            raise ValueError("beta0 must be > 0")
        if self.beta_growth < 1.0:
            raise ValueError("beta_growth must be >= 1")
        if self.stages < 1 or self.steps < 1:
            raise ValueError("stages and steps must be >= 1")
        if not 0.0 < self.step_safety <= 1.0:
            raise ValueError("step_safety must be in (0, 1]")

View source ↗

betasmethod

betas(self) -> list[float]

The inverse-temperature beta at each homotopy stage.

Returns: list[float]

Executed regression · discrete schedule drives tropical operators

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_discrete_schedule_drives_tropical_operators() -> None:
    schedule = AnnealSchedule.fast()
    tropical = as_tropical_schedule(schedule)
    assert tropical.betas() == schedule.betas()

python -m pytest "packages/omnibias-discrete/tests/test_tropical_integration.py::test_discrete_schedule_drives_tropical_operators" -q

Method implementation

    def betas(self) -> list[float]:
        """The inverse-temperature ``beta`` at each homotopy stage."""
        out, beta = [], self.beta0
        for _ in range(self.stages):
            out.append(beta)
            beta *= self.beta_growth
        return out

View source ↗

fastmethod

fast(cls) -> AnnealSchedule

A lighter schedule for training *through* the relaxation.

Returns: AnnealSchedule

Executed regression · fast schedule is lighter

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_fast_schedule_is_lighter() -> None:
    assert AnnealSchedule.fast().stages < AnnealSchedule().stages

python -m pytest "packages/omnibias-discrete/tests/test_schedule.py::test_fast_schedule_is_lighter" -q

Method implementation

    def fast(cls) -> AnnealSchedule:
        """A lighter schedule for training *through* the relaxation."""
        return cls(beta0=0.5, beta_growth=1.7, stages=8, steps=30)

View source ↗

Read the implementation

class AnnealSchedule:
    r"""Homotopy schedule for the differentiable annealed (temperature-collapse) relaxation.

    The relaxation parametrises ``x = sigmoid(beta theta) in (0, 1)^n`` and descends the
    closed-form energy gradient by unrolled gradient descent along a geometric ``beta``
    homotopy; as ``beta`` grows the soft assignment collapses onto a binary vertex.
    Defaults are eval-quality; :meth:`fast` is enough to train *through* the relaxation.

    Attributes
    ----------
    beta0, beta_growth:
        Initial inverse-temperature and geometric growth factor per stage.
    stages:
        Number of homotopy stages (each warm-starts the next).
    steps:
        Gradient-descent steps per stage.
    step_safety:
        Fraction of the (closed-form Lipschitz) step to take (``0 < step_safety <= 1``).
    """

    beta0: float = 0.5
    beta_growth: float = 1.5
    stages: int = 12
    steps: int = 60
    step_safety: float = 0.9

    def __post_init__(self) -> None:
        if self.beta0 <= 0.0:
            raise ValueError("beta0 must be > 0")
        if self.beta_growth < 1.0:
            raise ValueError("beta_growth must be >= 1")
        if self.stages < 1 or self.steps < 1:
            raise ValueError("stages and steps must be >= 1")
        if not 0.0 < self.step_safety <= 1.0:
            raise ValueError("step_safety must be in (0, 1]")

    def betas(self) -> list[float]:
        """The inverse-temperature ``beta`` at each homotopy stage."""
        out, beta = [], self.beta0
        for _ in range(self.stages):
            out.append(beta)
            beta *= self.beta_growth
        return out

    @classmethod
    def fast(cls) -> AnnealSchedule:
        """A lighter schedule for training *through* the relaxation."""
        return cls(beta0=0.5, beta_growth=1.7, stages=8, steps=30)

CLASS

DiscreteSolution

omnibias.discrete.DiscreteSolutionSource ↗

class DiscreteSolution(Generic[ArrayT])

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

A decoded binary point and (optionally) the relaxation it was rounded from.

Attributes

assignment: The decoded binary vector as a tuple of 0 / 1 of length n. energy: The energy of assignment (an *upper* bound on the minimum). relaxed: Optional soft assignment x in (0, 1)^n produced by the differentiable relaxation (the point the binary vector was decoded from), a backend array.

Parameters

Name	Type & default	Contract
assignmentdataclass field	tuple[int, ...]Required	The decoded binary vector as a tuple of 0 / 1 of length n.
energydataclass field	floatRequired	The energy of assignment (an *upper* bound on the minimum).
relaxeddataclass field	ArrayT | NoneDefault: None	Optional soft assignment x in (0, 1)^n produced by the differentiable relaxation (the point the binary vector was decoded from), a backend array.

Fields & methods

assignmentfield

assignment: tuple[int, ...]

The decoded binary vector as a tuple of 0 / 1 of length n.

View source ↗

energyfield

energy: float

The energy of assignment (an *upper* bound on the minimum).

View source ↗

relaxedfield

relaxed: ArrayT | None = None

Optional soft assignment x in (0, 1)^n produced by the differentiable relaxation (the point the binary vector was decoded from), a backend array.

View source ↗

nproperty

n(self) -> int

See the class contract above and the exact method implementation below.

Returns: int

Method implementation

    def n(self) -> int:
        return len(self.assignment)

View source ↗

Read the implementation

class DiscreteSolution(Generic[ArrayT]):
    r"""A decoded binary point and (optionally) the relaxation it was rounded from.

    Attributes
    ----------
    assignment:
        The decoded binary vector as a tuple of ``0`` / ``1`` of length ``n``.
    energy:
        The energy of ``assignment`` (an *upper* bound on the minimum).
    relaxed:
        Optional soft assignment ``x in (0, 1)^n`` produced by the differentiable
        relaxation (the point the binary vector was decoded from), a backend array.
    """

    assignment: tuple[int, ...]
    energy: float
    relaxed: ArrayT | None = None

    @property
    def n(self) -> int:
        return len(self.assignment)

CLASS

GapCertificate

omnibias.discrete.GapCertificateSource ↗

class GapCertificate

Dataclass constructor fields; inherited fields, if any, are declared by the base class. A field(...) expression describes a default factory or field options, not a literal argument default.

A rigorous optimality-gap certificate for a decoded discrete point.

Combines a rigorous **lower** bound on the minimum energy with the decoded point's energy as the **upper** bound, so the true optimum is provably sandwiched lower_bound <= optimum <= energy; the gap certifies how close to optimal the point is -- **without** any exact-optimality claim.

Attributes

lower_bound: Rigorous lower bound on the minimum energy of the problem. energy: The decoded point's energy (the certified upper bound). method: Which lower bound was used, e.g. "sos" (Lasserre / Positivstellensatz over the Boolean hypercube), "spectral" (eigenvalue-shift / box-QP relaxation), "negative_coeff" (the trivial sum-of-negative-coefficients bound), or "none" (no lower bound available in this environment). level: The SOS relaxation half-degree for method == "sos" (0 otherwise). certified: True iff lower_bound is rigorously sealed (an SOS proof, or an interval-sealed convex bound); False for a valid-but-unsealed float value. sealed: Optional hash-sealed v1 certificate (an omnibias.core.proof object) when an SOS lower bound was proved and sealed; None otherwise.

Parameters

Name	Type & default	Contract
lower_bounddataclass field	floatRequired	Rigorous lower bound on the minimum energy of the problem.
energydataclass field	floatRequired	The decoded point's energy (the certified upper bound).
methoddataclass field	strRequired	Which lower bound was used, e.g. "sos" (Lasserre / Positivstellensatz over the Boolean hypercube), "spectral" (eigenvalue-shift / box-QP relaxation), "negative_coeff" (the trivial sum-of-negative-coefficients bound), or "none" (no lower bound available in this environment).
leveldataclass field	intRequired	The SOS relaxation half-degree for method == "sos" (0 otherwise).
certifieddataclass field	boolRequired	True iff lower_bound is rigorously sealed (an SOS proof, or an interval-sealed convex bound); False for a valid-but-unsealed float value.
sealeddataclass field	object | NoneDefault: None	Optional hash-sealed v1 certificate (an omnibias.core.proof object) when an SOS lower bound was proved and sealed; None otherwise.

Executed regression · degrades gracefully without sos

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_degrades_gracefully_without_sos(make_toy, monkeypatch: pytest.MonkeyPatch) -> None:  # type: ignore[no-untyped-def]
    monkeypatch.setitem(sys.modules, "omnibias.sos", None)
    prob = make_toy([[0.0, -1.0], [-1.0, 0.0]], c=[0.5, 0.5])
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment)
    assert cert.method == "none"  # degraded, not crashed
    assert math.isinf(cert.lower_bound) and cert.lower_bound < 0
    assert cert.certified is False and cert.is_sound

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_degrades_gracefully_without_sos" -q

Regression example · certificate is gap shaped not exactness

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_certificate_is_gap_shaped_not_exactness() -> None:
    fields = GapCertificate.__dataclass_fields__
    assert "lower_bound" in fields and "energy" in fields
    for banned in ("optimal", "is_exact", "exact", "is_optimal", "zero_gap"):
        assert banned not in fields, f"{banned} would imply an exactness claim"
    for prop in ("absolute_gap", "relative_gap", "is_sound"):
        assert hasattr(GapCertificate, prop)

python -m pytest packages/omnibias-discrete/tests/test_scope.py -k test_certificate_is_gap_shaped_not_exactness -q

Fields & methods

lower_boundfield

lower_bound: float

Rigorous lower bound on the minimum energy of the problem.

View source ↗

energyfield

energy: float

The decoded point's energy (the certified upper bound).

View source ↗

methodfield

method: str

Which lower bound was used, e.g. "sos" (Lasserre / Positivstellensatz over the Boolean hypercube), "spectral" (eigenvalue-shift / box-QP relaxation), "negative_coeff" (the trivial sum-of-negative-coefficients bound), or "none" (no lower bound available in this environment).

View source ↗

levelfield

level: int

The SOS relaxation half-degree for method == "sos" (0 otherwise).

View source ↗

certifiedfield

certified: bool

True iff lower_bound is rigorously sealed (an SOS proof, or an interval-sealed convex bound); False for a valid-but-unsealed float value.

View source ↗

sealedfield

sealed: object | None = None

Optional hash-sealed v1 certificate (an omnibias.core.proof object) when an SOS lower bound was proved and sealed; None otherwise.

View source ↗

absolute_gapproperty

absolute_gap(self) -> float

Certified absolute optimality gap energy - lower_bound (>= 0).

Returns: float

Executed regression · sos sandwich is sound

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_sos_sandwich_is_sound(make_toy) -> None:  # type: ignore[no-untyped-def]
    pytest.importorskip("omnibias.sos")
    rng = np.random.default_rng(0)
    for seed in range(4):
        m = rng.standard_normal((3, 3))
        prob = make_toy(m + m.T, c=rng.standard_normal(3), const=0.3)
        _, e_min = brute_force_min(prob)
        assignment, _ = decode(prob, seed=seed, n_starts=16)
        cert = certify_gap(prob, assignment, level=1, bisection_steps=20)
        assert cert.method in ("sos", "negative_coeff")
        assert cert.lower_bound <= e_min + 1e-6  # lower bound never exceeds the true min
        assert cert.energy >= e_min - 1e-9  # decoded energy is an upper bound
        assert cert.is_sound and cert.absolute_gap >= -1e-9

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_sos_sandwich_is_sound" -q

Method implementation

    def absolute_gap(self) -> float:
        """Certified absolute optimality gap ``energy - lower_bound`` (``>= 0``)."""
        return self.energy - self.lower_bound

View source ↗

relative_gapproperty

relative_gap(self) -> float

Certified relative gap (energy - lower_bound) / max(|lower_bound|, tiny).

Returns: float

Method implementation

    def relative_gap(self) -> float:
        """Certified relative gap ``(energy - lower_bound) / max(|lower_bound|, tiny)``."""
        return self.absolute_gap / max(abs(self.lower_bound), _TINY)

View source ↗

is_soundproperty

is_sound(self) -> bool

Whether the sandwich holds (lower_bound <= energy within rounding).

Returns: bool

Executed regression · degrades gracefully without sos

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_degrades_gracefully_without_sos(make_toy, monkeypatch: pytest.MonkeyPatch) -> None:  # type: ignore[no-untyped-def]
    monkeypatch.setitem(sys.modules, "omnibias.sos", None)
    prob = make_toy([[0.0, -1.0], [-1.0, 0.0]], c=[0.5, 0.5])
    assignment, _ = decode(prob)
    cert = certify_gap(prob, assignment)
    assert cert.method == "none"  # degraded, not crashed
    assert math.isinf(cert.lower_bound) and cert.lower_bound < 0
    assert cert.certified is False and cert.is_sound

python -m pytest "packages/omnibias-discrete/tests/test_certify.py::test_degrades_gracefully_without_sos" -q

Method implementation

    def is_sound(self) -> bool:
        """Whether the sandwich holds (``lower_bound <= energy`` within rounding)."""
        return self.lower_bound <= self.energy + 1e-9

View source ↗

Read the implementation

class GapCertificate:
    r"""A rigorous optimality-gap certificate for a decoded discrete point.

    Combines a rigorous **lower** bound on the minimum energy with the decoded point's
    energy as the **upper** bound, so the true optimum is provably sandwiched
    ``lower_bound <= optimum <= energy``; the gap certifies how close to optimal the
    point is -- **without** any exact-optimality  claim.

    Attributes
    ----------
    lower_bound:
        Rigorous lower bound on the minimum energy of the problem.
    energy:
        The decoded point's energy (the certified upper bound).
    method:
        Which lower bound was used, e.g. ``"sos"`` (Lasserre / Positivstellensatz over
        the Boolean hypercube), ``"spectral"`` (eigenvalue-shift / box-QP relaxation),
        ``"negative_coeff"`` (the trivial sum-of-negative-coefficients bound), or
        ``"none"`` (no lower bound available in this environment).
    level:
        The SOS relaxation half-degree for ``method == "sos"`` (``0`` otherwise).
    certified:
        ``True`` iff ``lower_bound`` is rigorously sealed (an SOS proof, or an
        interval-sealed convex bound); ``False`` for a valid-but-unsealed float value.
    sealed:
        Optional hash-sealed v1 certificate (an ``omnibias.core.proof`` object) when an
        SOS lower bound was proved and sealed; ``None`` otherwise.
    """

    lower_bound: float
    energy: float
    method: str
    level: int
    certified: bool
    sealed: object | None = None

    @property
    def absolute_gap(self) -> float:
        """Certified absolute optimality gap ``energy - lower_bound`` (``>= 0``)."""
        return self.energy - self.lower_bound

    @property
    def relative_gap(self) -> float:
        """Certified relative gap ``(energy - lower_bound) / max(|lower_bound|, tiny)``."""
        return self.absolute_gap / max(abs(self.lower_bound), _TINY)

    @property
    def is_sound(self) -> bool:
        """Whether the sandwich holds (``lower_bound <= energy`` within rounding)."""
        return self.lower_bound <= self.energy + 1e-9

CLASS

UnionFind

omnibias.discrete.UnionFindSource ↗

class UnionFind

Disjoint-set forest with path halving; union reports whether it merged two trees.

union(a, b) returns True when a and b were in different components (so the edge (a, b) is a tree edge) and False when they were already connected (so the edge closes a cycle) -- exactly the signal an incremental forest / matroid-independence check needs.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Executed regression · is forest path and triangle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_forest_path_and_triangle() -> None:
    assert is_forest([(0, 1), (1, 2), (2, 3)], 4) is True  # a path is acyclic
    assert is_forest([(0, 1), (1, 2), (2, 0)], 3) is False  # a triangle is not
    assert is_forest([], 3) is True  # the empty edge set is a forest

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_is_forest_path_and_triangle" -q

Regression example · union find reports tree vs cycle edges

This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_union_find_reports_tree_vs_cycle_edges() -> None:
    uf = UnionFind(4)
    assert uf.union(0, 1) is True
    assert uf.union(1, 2) is True
    assert uf.union(0, 2) is False  # 0 and 2 are already connected -> cycle edge
    assert uf.find(0) == uf.find(2)
    assert uf.find(3) == 3  # untouched singleton

python -m pytest packages/omnibias-discrete/tests/test_shared.py -k test_union_find_reports_tree_vs_cycle_edges -q

Fields & methods

__init__method

__init__(self, n: int) -> None

See the class contract above and the exact method implementation below.

Parameters

Name	Type & default	Contract
npositional-or-keyword	intRequired	See the operation contract and implementation below.

Returns: None

Validation & failure cases

• When n < 0, raises ValueError('n must be >= 0').

Executed regression · is forest path and triangle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_forest_path_and_triangle() -> None:
    assert is_forest([(0, 1), (1, 2), (2, 3)], 4) is True  # a path is acyclic
    assert is_forest([(0, 1), (1, 2), (2, 0)], 3) is False  # a triangle is not
    assert is_forest([], 3) is True  # the empty edge set is a forest

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_is_forest_path_and_triangle" -q

Method implementation

    def __init__(self, n: int) -> None:
        if n < 0:
            raise ValueError("n must be >= 0")
        self._parent = list(range(n))

View source ↗

findmethod

find(self, a: int) -> int

The representative of a's component (with path-halving compression).

Parameters

Name	Type & default	Contract
apositional-or-keyword	intRequired	See the operation contract and implementation below.

Returns: int

Executed regression · is forest path and triangle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_forest_path_and_triangle() -> None:
    assert is_forest([(0, 1), (1, 2), (2, 3)], 4) is True  # a path is acyclic
    assert is_forest([(0, 1), (1, 2), (2, 0)], 3) is False  # a triangle is not
    assert is_forest([], 3) is True  # the empty edge set is a forest

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_is_forest_path_and_triangle" -q

Method implementation

    def find(self, a: int) -> int:
        """The representative of ``a``'s component (with path-halving compression)."""
        parent = self._parent
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a

View source ↗

unionmethod

union(self, a: int, b: int) -> bool

Merge the components of a and b; True iff they were previously disjoint.

Parameters

Name	Type & default	Contract
apositional-or-keyword	intRequired	See the operation contract and implementation below.
bpositional-or-keyword	intRequired	See the operation contract and implementation below.

Returns: bool

Executed regression · is forest path and triangle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_forest_path_and_triangle() -> None:
    assert is_forest([(0, 1), (1, 2), (2, 3)], 4) is True  # a path is acyclic
    assert is_forest([(0, 1), (1, 2), (2, 0)], 3) is False  # a triangle is not
    assert is_forest([], 3) is True  # the empty edge set is a forest

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_is_forest_path_and_triangle" -q

Method implementation

    def union(self, a: int, b: int) -> bool:
        """Merge the components of ``a`` and ``b``; ``True`` iff they were previously disjoint."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self._parent[ra] = rb
        return True

View source ↗

Read the implementation

class UnionFind:
    r"""Disjoint-set forest with path halving; ``union`` reports whether it merged two trees.

    ``union(a, b)`` returns ``True`` when ``a`` and ``b`` were in different components (so the
    edge ``(a, b)`` is a tree edge) and ``False`` when they were already connected (so the edge
    closes a cycle) -- exactly the signal an incremental forest / matroid-independence check needs.
    """

    def __init__(self, n: int) -> None:
        if n < 0:
            raise ValueError("n must be >= 0")
        self._parent = list(range(n))

    def find(self, a: int) -> int:
        """The representative of ``a``'s component (with path-halving compression)."""
        parent = self._parent
        while parent[a] != a:
            parent[a] = parent[parent[a]]
            a = parent[a]
        return a

    def union(self, a: int, b: int) -> bool:
        """Merge the components of ``a`` and ``b``; ``True`` iff they were previously disjoint."""
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        self._parent[ra] = rb
        return True

FUNCTION

is_forest

omnibias.discrete.is_forestSource ↗

is_forest(edges: Iterable[tuple[int, int]], n_vertices: int) -> bool

Whether edges over n_vertices vertices induce a forest (are acyclic).

Streams the edges through one UnionFind; the first edge that closes a cycle short- circuits the result to False. Runs in O(E alpha(V)).

Parameters

Name	Type & default	Contract
edgespositional-or-keyword	Iterable[tuple[int, int]]Required	See the operation contract and implementation below.
n_verticespositional-or-keyword	intRequired	See the operation contract and implementation below.

Returnsbool

Executed regression · is forest path and triangle

Recorded coverage confirms this test executed the API body. This example belongs to the pinned upstream test suite. It may use fixtures and imports from its full file. Run it from that checkout with its test dependencies installed.

Full file, imports & fixtures ↗

def test_is_forest_path_and_triangle() -> None:
    assert is_forest([(0, 1), (1, 2), (2, 3)], 4) is True  # a path is acyclic
    assert is_forest([(0, 1), (1, 2), (2, 0)], 3) is False  # a triangle is not
    assert is_forest([], 3) is True  # the empty edge set is a forest

python -m pytest "packages/omnibias-discrete/tests/test_shared.py::test_is_forest_path_and_triangle" -q

Read the implementation

def is_forest(edges: Iterable[tuple[int, int]], n_vertices: int) -> bool:
    r"""Whether ``edges`` over ``n_vertices`` vertices induce a forest (are acyclic).

    Streams the edges through one :class:`UnionFind`; the first edge that closes a cycle short-
    circuits the result to ``False``. Runs in ``O(E alpha(V))``.
    """
    uf = UnionFind(n_vertices)
    return all(uf.union(u, v) for u, v in edges)

Related APIsomnibias.discrete.UnionFind↗

← Package overviewRunnable learning examples →