API REFERENCE/omnibias-discrete

omnibias.discrete.certify

0.1.0a2AlphaPython >=3.10AGPL / commercial

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

import omnibias.discrete.certify

Module contract & mathematical conventions

Rigorous optimality-gap certificate for a decoded discrete point.

certify_gap sandwiches the true minimum energy between

• a **rigorous lower bound** -- the Lasserre / SOS bound over the Boolean hypercube (omnibias.discrete._core.bound.lasserre_lower_bound, hash-sealed and Lean-checkable), seeded and back-stopped by the always-valid omnibias.discrete._core.bound.negative_coeff_lower_bound; and

• the **decoded point's energy** as the upper bound.

The result is a certified optimality gap lower <= optimum <= energy -- never an exact-optimality claim, and honest about bound strength (a weaker bound only widens the certified gap). Without omnibias-sos the SOS bound is unavailable and the certificate degrades to the trivial floor (certified=False), or to method="none" when even the polynomial cannot be built.

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 →

CLASS

TightenedGap

omnibias.discrete.TightenedGapSource ↗

class TightenedGap

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.

Best sound Lasserre sandwich among increasing relaxation levels.

tight is always False. A smaller gap is a better sound floor, without asserting a zero optimality gap.

Parameters

Name	Type & default	Contract
certificatedataclass field	GapCertificateRequired	See the operation contract and implementation below.
level_useddataclass field	intRequired	See the operation contract and implementation below.
levels_trieddataclass field	tuple[int, ...]Required	See the operation contract and implementation below.
tightdataclass field	boolDefault: False	See the operation contract and implementation below.

Fields & methods

certificatefield

certificate: GapCertificate

Declared GapCertificate field on TightenedGap. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

level_usedfield

level_used: int

Declared int field on TightenedGap. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

levels_triedfield

levels_tried: tuple[int, ...]

Declared tuple[int, ...] field on TightenedGap. A value must be provided when constructing the configuration, unless an inherited constructor supplies it.

View source ↗

tightfield

tight: bool = False

Declared bool field on TightenedGap. Default expression: False.

View source ↗

gapproperty

gap(self) -> float

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

Returns: float

Method implementation

    def gap(self) -> float:
        return self.certificate.absolute_gap

View source ↗

honestymethod

honesty(self) -> dict[str, bool]

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

Returns: dict[str, bool]

Method implementation

    def honesty(self) -> dict[str, bool]:
        return {
            "p_vs_np_claim": False,
            "tight": False,
        }

View source ↗

Read the implementation

class TightenedGap:
    """Best sound Lasserre sandwich among increasing relaxation levels.

    ``tight`` is always ``False``. A smaller gap is a better sound floor,
    without asserting a zero optimality gap.
    """

    certificate: GapCertificate
    level_used: int
    levels_tried: tuple[int, ...]
    tight: bool = False

    @property
    def gap(self) -> float:
        return self.certificate.absolute_gap

    def honesty(self) -> dict[str, bool]:
        return {
            "p_vs_np_claim": False,
            "tight": False,
        }

Other public import paths

• omnibias.discrete.TightenedGap
• omnibias.discrete.certify.TightenedGap

FUNCTION

certify_gap

omnibias.discrete.certify_gapSource ↗

certify_gap(problem: DiscreteProblem, x: object, *, level: int=1, bisection_steps: int=24, seed_lower: float | None=None, claim_label: str='energy') -> GapCertificate

Certify how close the binary point x is to optimal for problem.

Parameters

problem: Any ~omnibias.discrete._core.problem.DiscreteProblem. x: A binary point x in {0, 1}^n (e.g. from omnibias.discrete.decode) -- the upper bound. level: SOS relaxation half-degree (1 is the basic Boolean relaxation; higher is tighter and more expensive). Must be at least ceil(deg(E) / 2) to represent the energy. bisection_steps: Number of bisection steps used to search for the largest provable SOS bound. seed_lower: Optional lower bracket for the bisection; defaults to the always-valid negative_coeff_lower_bound. claim_label: Human-readable subject of the sealed SOS claim.

Returns

~omnibias.discrete._core.solution.GapCertificate with the rigorous lower bound, the decoded energy, and a sealed v1 certificate when an SOS bound proved.

Parameters

Name	Type & default	Contract
problempositional-or-keyword	DiscreteProblemRequired	Any ~omnibias.discrete._core.problem.DiscreteProblem.
xpositional-or-keyword	objectRequired	A binary point x in {0, 1}^n (e.g. from omnibias.discrete.decode) -- the upper bound.
levelkeyword-only	intDefault: 1	SOS relaxation half-degree (1 is the basic Boolean relaxation; higher is tighter and more expensive). Must be at least ceil(deg(E) / 2) to represent the energy.
bisection_stepskeyword-only	intDefault: 24	Number of bisection steps used to search for the largest provable SOS bound.
seed_lowerkeyword-only	float | NoneDefault: None	Optional lower bracket for the bisection; defaults to the always-valid negative_coeff_lower_bound.
claim_labelkeyword-only	strDefault: 'energy'	Human-readable subject of the sealed SOS claim.

ReturnsGapCertificate

Explicit validation & failure cases

• When xv.shape[0] != n, raises ValueError(f'x must have length {n}, got {xv.shape[0]}').
• When not is_binary(xv), raises ValueError('x must be a binary point in {0, 1}^n (decode the relaxation first)').

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

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 · rejects a wrong length point

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_wrong_length_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="length"):
        certify_gap(prob, np.array([0.0, 1.0, 0.0]))

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

Read the implementation

def certify_gap(
    problem: DiscreteProblem,
    x: object,
    *,
    level: int = 1,
    bisection_steps: int = 24,
    seed_lower: float | None = None,
    claim_label: str = "energy",
) -> GapCertificate:
    r"""Certify how close the binary point ``x`` is to optimal for ``problem``.

    Parameters
    ----------
    problem:
        Any :class:`~omnibias.discrete._core.problem.DiscreteProblem`.
    x:
        A binary point ``x in {0, 1}^n`` (e.g. from :func:`omnibias.discrete.decode`) --
        the upper bound.
    level:
        SOS relaxation half-degree (``1`` is the basic Boolean relaxation; higher is
        tighter and more expensive). Must be at least ``ceil(deg(E) / 2)`` to represent
        the energy.
    bisection_steps:
        Number of bisection steps used to search for the largest provable SOS bound.
    seed_lower:
        Optional lower bracket for the bisection; defaults to the always-valid
        :func:`negative_coeff_lower_bound`.
    claim_label:
        Human-readable subject of the sealed SOS claim.

    Returns
    -------
    :class:`~omnibias.discrete._core.solution.GapCertificate` with the rigorous lower
    bound, the decoded energy, and a ``sealed`` v1 certificate when an SOS bound proved.
    """
    n = problem.n
    xv = np.asarray(x, dtype=float).reshape(-1)
    if xv.shape[0] != n:
        raise ValueError(f"x must have length {n}, got {xv.shape[0]}")
    if not is_binary(xv):
        raise ValueError("x must be a binary point in {0, 1}^n (decode the relaxation first)")
    upper = float(problem.energy(xv))

    try:
        import omnibias.sos  # noqa: F401  (availability gate for the polynomial + SOS bound)
    except ImportError:
        return GapCertificate(
            lower_bound=float("-inf"), energy=upper, method="none", level=0,
            certified=False, sealed=None,
        )

    poly = problem.to_polynomial()
    floor = negative_coeff_lower_bound(poly)
    seed = floor if seed_lower is None else float(seed_lower)
    result = lasserre_lower_bound(
        problem, level=level, seed_lower=seed, upper=upper,
        steps=bisection_steps, claim_label=claim_label,
    )
    if result is None:  # sos present but nothing proved -> the valid trivial floor
        return GapCertificate(
            lower_bound=floor, energy=upper, method="negative_coeff", level=0,
            certified=False, sealed=None,
        )
    gamma, sealed = result
    return GapCertificate(
        lower_bound=gamma, energy=upper, method="sos", level=level,
        certified=True, sealed=sealed,
    )

Related APIsomnibias.discrete.lasserre_lower_bound↗omnibias.discrete.negative_coeff_lower_bound↗omnibias.discrete.is_binary↗omnibias.discrete.GapCertificate↗

Other public import paths

• omnibias.discrete.certify_gap
• omnibias.discrete.certify.certify_gap

FUNCTION

tighten_gap

omnibias.discrete.tighten_gapSource ↗

tighten_gap(problem: DiscreteProblem, x: object, *, levels: Sequence[int]=(1, 2), bisection_steps: int=24, seed_lower: float | None=None, claim_label: str='energy') -> TightenedGap

Run increasing Lasserre levels and keep the best sound lower bound.

A higher level that fails or is not sound is skipped. Tightness is never claimed.

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.
levelskeyword-only	Sequence[int]Default: (1, 2)	See the operation contract and implementation below.
bisection_stepskeyword-only	intDefault: 24	See the operation contract and implementation below.
seed_lowerkeyword-only	float | NoneDefault: None	See the operation contract and implementation below.
claim_labelkeyword-only	strDefault: 'energy'	See the operation contract and implementation below.

ReturnsTightenedGap

Explicit validation & failure cases

• When not levels, raises ValueError('levels must be non-empty').
• When any((level < 0 for level in ordered)), raises ValueError('levels must be >= 0').

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

Read the implementation

def tighten_gap(
    problem: DiscreteProblem,
    x: object,
    *,
    levels: Sequence[int] = (1, 2),
    bisection_steps: int = 24,
    seed_lower: float | None = None,
    claim_label: str = "energy",
) -> TightenedGap:
    """Run increasing Lasserre levels and keep the best sound lower bound.

    A higher level that fails or is not sound is skipped. Tightness is
    never claimed.
    """
    if not levels:
        raise ValueError("levels must be non-empty")
    ordered = tuple(int(level) for level in levels)
    if any(level < 0 for level in ordered):
        raise ValueError("levels must be >= 0")
    best: GapCertificate | None = None
    used = ordered[0]
    fallback: GapCertificate | None = None
    for level in ordered:
        nxt = certify_gap(
            problem,
            x,
            level=level,
            bisection_steps=bisection_steps,
            seed_lower=seed_lower,
            claim_label=claim_label,
        )
        if fallback is None:
            fallback = nxt
        if not nxt.is_sound:
            continue
        if best is None or nxt.lower_bound + 1e-12 >= best.lower_bound:
            best = nxt
            used = level
    if best is None:
        best = fallback
    return TightenedGap(
        certificate=best,
        level_used=used,
        levels_tried=ordered,
        tight=False,
    )

Related APIsomnibias.discrete.TightenedGap↗omnibias.discrete.certify_gap↗

Other public import paths

• omnibias.discrete.tighten_gap
• omnibias.discrete.certify.tighten_gap

← Package overviewRunnable learning examples →