API Reference

varlt(u::V, v::V) where {V}

Compares two variables, $u$ and $v$, with respect to their length-lexicographic order.

Rationale

This function exists to define an arbitrary ordering for a given type and was created to address ^[MOI]. There is no predefined comparison between instances MOI's VariableIndex type.

[^MOI]: MathOptInterface Issue [#1985](https://github.com/jump-dev/MathOptInterface.jl/issues/1985)

varmul(u::V, v::V) where {V}

varmap(::Type{V}, i::Integer) where {V}

vargen(::AbstractPBF{V,T}; name::AbstractString = "x") where {V<:AbstractString,T}

Creates a function that, when called multiple times, returns the strings "aux_1", "aux_2", ... and so on.

vargen(::AbstractPBF{Symbol,T}; name::Symbol = :x) where {T}

Creates a function that, when called multiple times, returns the symbols :x₋₁, :x₋₂, ... and so on.

vargen(::AbstractPBF{V,T}; start::V = V(0), step::V = V(-1)) where {V<:Integer,T}

Creates a function that, when called multiple times, returns the integers $-1$, $-2$, ... and so on.

varshow(v::V) where {V}
varshow(io::IO, v::V) where {V}

AbstractTerm{V}

Term{V}

Reference implementation for AbstractTerm.

term

term_head

term_tail

AbstractPBF{V,T}

A pseudo-Boolean Function^[Boros2002] $f \in \mathscr{F}$ over some field $\mathbb{T}$ takes the form

\[f(\mathbf{x}) = \sum_{\omega \in \Omega\left[f\right]} c_\omega \prod_{j \in \omega} x_j\]

where each $\Omega\left[{f}\right]$ is the multi-linear representation of $f$ as a set of terms. Each term is given by a unique set of indices $\omega \subseteq \mathbb{V}$ related to some coefficient $c_\omega \in \mathbb{T}$. We say that $\omega \in \Omega\left[{f}\right] \iff c_\omega \neq 0$. Variables $x_j$ are boolean, thus $f : \mathbb{B}^{n} \to \mathbb{T}$.

PBF{V,T,S}

This is a concrete implementation of AbstractPBF that uses the S data structure to store the terms of the function.

data(f::AbstractPBF{V,T})

Returns the internal representation of $f \in \mathscr{F}$.

isconstant(f::AbstractPBF)::Bool

Check if the given Pseudo-Boolean function f is a constant, i.e., if it has no variables.

degree(f::AbstractPBF)

lowerbound(f::AbstractPBF)

Computes an approximate value for the greatest $\forall \mathbf{x}. l \le f(\mathbf{x})$.

upperbound(f::AbstractPBF)

Computes an approximate value for the least $\forall \mathbf{x}. u \ge f(\mathbf{x})$.

bounds(f::AbstractPBF)

Given $f : \mathbb{B}^{n} \to [a, b]$, returns the approximate extrema for the tightest $[l, u] \supset [a, b]$.

mingap(f::AbstractPBF{V,T}, tol::T = T(1e-6)) where {V,T}

The ideal minimum gap is the greatest lower bound on the smallest non-zero value taken by $f \in \mathscr{F}$.

maxgap(f::AbstractPBF{V,T}) where {V,T}

Computes the least upper bound for the greatest variantion possible of $f \in \mathscr{F}$ i. e.

\[\begin{array}{rl} \min & M \\ \text{s.t.} & \left|{f(\mathbf{x}) - f(\mathbf{y})}\right| \le M ~~ \forall \mathbf{x}, \mathbf{y} \in \mathbb{B}^{n} \end{array}\]

A simple approach is to define

\[M \triangleq \sum_{\omega \neq \varnothing} \left|{c_\omega}\right|\]

derivative(f::AbstractPBF{V,T}, x::V) where {V,T}

The partial derivate of function $f \in \mathscr{F}$ with respect to the $x$ variable.

\[ \Delta_i f(\mathbf{x}) = \frac{\partial f(\mathbf{x})}{\partial \mathbf{x}_i} = \sum_{\omega \in \Omega\left[{f}\right] \setminus \left\{{i}\right\}} c_{\omega \cup \left\{{i}\right\}} \prod_{k \in \omega} \mathbf{x}_k\]

gradient(f::AbstractPBF)

Computes the gradient of $f \in \mathscr{F}$ where the $i$-th derivative is given by derivative.

residual(f::AbstractPBF{V,T}, x::S) where {V,T}

The residual of $f \in \mathscr{F}$ with respect to $x$.

\[ \Theta_i f(\mathbf{x}) = f(\mathbf{x}) - \mathbf{x}_i\, \Delta_i f(\mathbf{x}) = \sum_{\omega \in \Omega\left[{f}\right] \setminus \left\{{i}\right\}} c_{\omega} \prod_{k \in \omega} \mathbf{x}_k\]

discretize(f::AbstractPBF{V,T}; tol::T) where {V,T}

For a given function $f \in \mathscr{F}$ written as

\[ f\left({\mathbf{x}}\right) = \sum_{\omega \in \Omega\left[{f}\right]} c_\omega \prod_{i \in \omega} \mathbf{x}_i\]

computes an approximate function $g : \mathbb{B}^{n} \to \mathbb{Z}$ such that

\[ \text{argmin}_{\mathbf{x} \in \mathbb{B}^{n}} g\left({\mathbf{x}}\right) = \text{argmin}_{\mathbf{x} \in \mathbb{B}^{n}} f\left({\mathbf{x}}\right)\]

This is done by rationalizing every coefficient $c_\omega$ according to some tolerance tol.

discretize!(f::AbstractPBF{V,T}; tol::T) where {V,T}

In-place version of discretize.

relaxedgcd(x::T, y::T; tol::T = T(1E-6)) where {T}

We define two real numbers $x$ and $y$ to be $\tau$-comensurable if, for some $\tau > 0$ there exists a continued fractions convergent $p_{k} \div q_{k}$ such that

\[ \left| {q_{k} x - p_{k} y} \right| \le \tau\]

Quadratization(method::QuadratizationMethod; stable::Bool = false, sign::Integer = 1)

Configures a quadratization method.

The sign keyword controls the objective sense used to choose and validate term reductions. Use sign = 1 for minimization and sign = -1 for maximization. Coefficients in the quadratized function remain in the original objective scale.

quadratize(aux, f::PBF{V, T}, ::Quadratization{Q}) where {V,T,Q}

Quadratizes a given PBF, i.e., applies a mapping $\mathcal{Q} : \mathscr{F}^{k} \to \mathscr{F}^{2}$, where $\mathcal{Q}$ is the quadratization method.

For Quadratization(...; sign = 1), the returned function preserves minimization over auxiliary variables:

\[\min_{\mathbf{y}} \mathcal{Q}\{f\}(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}).\]

For Quadratization(...; sign = -1), it preserves maximization over auxiliary variables:

\[\max_{\mathbf{y}} \mathcal{Q}\{f\}(\mathbf{x}, \mathbf{y}) = f(\mathbf{x}).\]

Auxiliary variables

The aux function is expected to produce auxiliary variables with the following signatures:

aux()::V where {V}

Creates and returns a single variable.

aux(n::Integer)::Vector{V} where {V}

Creates and returns a vector with $n$ variables.

quadratize(f::PBF{V, T}, ::Quadratization{Q}) where {V,T,Q}

When aux is not specified, uses vargen to generate variables.

quadratize!(aux, f::PBF{V, T}, ::Quadratization{Q}) where {V,T,Q}
quadratize!(f::PBF{V, T}, ::Quadratization{Q}) where {V,T,Q}

In-place version of quadratize.

infer_quadratization(f::AbstractPBF)

For a given PBF, returns whether it should be quadratized or not, based on its characteristics.

Quadratization(::PTR_BG; stable::Bool = false, sign::Integer = 1)

Positive term reduction PTR-BG^[PTR_BG]

Let $f(\mathbf{x}) = x_{1} x_{2} \dots x_{k}$.

\[\mathcal{Q}\left\lbrace{f}\right\rbrace(\mathbf{x}; \mathbf{w}) = \left[{ \sum_{i = 1}^{k-2} z_{i} \left({ k - i - 1 + x_{i} - \sum_{j = i+1}^{k} x_{j} }\right) }\right] + x_{k-1} x_{k}\]

where $\mathbf{x} \in \mathbb{B}^k$ and $\mathbf{w} \in \mathbb{B}^{k-2}$

Properties

[PTR_BG]: Boros & Gruber, 2014

Quadratization(::NTR_KZFD; stable::Bool = false, sign::Integer = 1)

Negative term reduction NTR-KZFD^[NTR_KZFD]

Let $f(\mathbf{x}) = -x_{1} x_{2} \dots x_{k}$.

\[\mathcal{Q}\left\lbrace{f}\right\rbrace(\mathbf{x}; w) = (k - 1) w - \sum_{i = 1}^{k} x_{i} w\]

where $\mathbf{x} \in \mathbb{B}^k, w \in \mathbb{B}$.

Properties

Quadratization(::DEFAULT; stable::Bool = false, sign::Integer = 1)

Employs NTR_KZFD for negative terms and PTR_BG for the positive ones.

wishart(rng, n::Integer, m::Integer)

Generate a $K_{n}$ (complete graph) Ising weight matrix $J$ with the $\mathbf{1} \in {\pm 1}^{n}$ state as a planted ground state.

The main diagonal of $J$ is zero.

The Hamiltonian is zero field, i.e,

\[E(\mathbf{s}) = -\frac{1}{2} \mathbf{s}' J \mathbf{s}\]

• $m$ specifies the number of columns in $W$ (for $m \ge n$, FM and easy.)

• precision: number of decimal points to round the uncorrelated Gaussian used to generate the w elements. This is to avoid numerical issues where a spurious state takes over as the GS.

Alternatively, can even replace the Gaussian with a bounded range uniform discrete distribution in $[-range, +range]$...

sherrington_kirkpatrick(rng, ::Type{F}, n::Integer; μ::T = zero(T), σ::T = one(T)) where {V,T,F<:AbstractPBF{V,T}}

\[f^{(n)}_{\textrm{SK}}(\mathbf{x}) = \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} J_{i, j} x_i x_j\]

where $J_{i, j} \sim \mathcal{N}(0, 1)$.

not_all_equal_3sat(rng, n::Integer, m::Integer)

Generates Not-all-equal 3-SAT problem with $m$ variables and $n$ clauses.

k_regular_k_xorsat

Generates a $k$-regurlar $k$-XORSAT instance with $n$ boolean variables.

r_regular_k_xorsat(rng, r::Integer, k::Integer; quad::QuadratizationMethod)

Generates a $r$-regurlar $k$-XORSAT instance with $n$ boolean variables.

If $r = k$, then falls back to k_regular_k_xorsat.