qubosolver.solving.classical

Classical QUBO solver algorithms.

Provides CPLEX, tabu search, simulated annealing, random sampling, and brute-force solvers.

Modules:

brute_force –

Exact brute-force QUBO solver by exhaustive enumeration.
cplex –

QUBO solver backed by IBM CPLEX.
iterative_bitflip_local_search –

Bit-flip local search for QUBO solutions.
random_sampling –

Uniform random bitstring sampler for QUBO instances.
simulated_annealing –

Simulated Annealing solver for QUBO problems.
tabu_search –

Tabu Search solver for QUBO problems.
trivial_solution_search –

Trivial QUBO solution detection.

brute_force

Exact brute-force QUBO solver by exhaustive enumeration.

Enumerates the 2^n binary assignments of an n-variable QUBO, evaluates \(x^T Q x\) for each, and returns the max_bitstrings lowest-cost ones. This is exact but scales exponentially in n; it is meant for small instances, validation, and as a ground-truth reference for other solvers.

Enumeration proceeds in fixed-size batches so peak memory stays bounded and a wall-clock time_limit can interrupt it between batches. When the limit is reached the best assignments found so far are returned, so the result is a valid (possibly non-optimal) solution rather than an error.

Functions:

solve –

Solve a QUBO exactly by enumerating all 2^n binary assignments.

solve

solve(instance: Instance, *, max_bitstrings: int = 1, time_limit: float = float('inf')) -> Solution

Solve a QUBO exactly by enumerating all 2^n binary assignments.

Evaluates every assignment's cost and returns the max_bitstrings lowest-cost ones, sorted by ascending cost. Enumeration is batched; when time_limit elapses, the best assignments found so far are returned.

Parameters:

instance (Instance) –

The QUBO instance to solve.
max_bitstrings (int, default: 1 ) –

Number of lowest-cost bitstrings to return. If max_bitstrings > 2^n, only 2^n bitstrings are returned.
time_limit (float, default: float('inf') ) –

Wall-clock budget in seconds. Enumeration stops between batches once the budget is exhausted and returns the best solutions found so far. Use float("inf") for no limit.

Returns:

Solution –

A solution with up to max_bitstrings bitstrings, their QUBO costs, and probabilities, sorted by ascending cost.

Source code in qubosolver/solving/classical/brute_force.py

def solve(
    instance: Instance,
    *,
    max_bitstrings: int = 1,
    time_limit: float = float("inf"),
) -> Solution:
    """Solve a QUBO exactly by enumerating all ``2^n`` binary assignments.

    Evaluates every assignment's cost and returns the ``max_bitstrings``
    lowest-cost ones, sorted by ascending cost.  Enumeration is batched; when
    ``time_limit`` elapses, the best assignments found so far are returned.

    Args:
        instance: The QUBO instance to solve.
        max_bitstrings: Number of lowest-cost bitstrings to return.  If
            ``max_bitstrings > 2^n``, only ``2^n`` bitstrings are returned.
        time_limit: Wall-clock budget in seconds.  Enumeration stops between
            batches once the budget is exhausted and returns the best solutions
            found so far.  Use ``float("inf")`` for no limit.

    Returns:
        A solution with up to ``max_bitstrings`` bitstrings, their QUBO costs,
            and probabilities, sorted by ascending cost.
    """
    n: int = instance.size
    if n == 0:
        return Solution.zeros(0)

    if n > _LARGE_INSTANCE_SIZE and math.isinf(time_limit):
        logger.warning(
            f"brute_force: no time_limit set for a {n}-variable instance; "
            f"exhaustively enumerating {1 << n:,} assignments with no time limit "
            "may run for an impractically long time. Consider passing a finite "
            "time_limit."
        )

    Q = instance.matrix
    total = 1 << n
    deadline = time.perf_counter() + time_limit

    if max_bitstrings == -1:
        max_bitstrings = total

    best_bits = bitstrings.zeros(0, n, device=Q.device).to(Q.dtype)
    best_costs = vector.zeros(0)

    for start in range(0, total, _BATCH_SIZE):
        stop = min(start + _BATCH_SIZE, total)
        indices = vectori.as_tensor(torch.arange(start, stop, device=Q.device))
        bits = _decode_bits(indices, n).to(Q.dtype)
        costs = _costs.batched_quadratic_cost(bits, Q)

        merged_bits = torch.cat((best_bits, bits), dim=0)
        merged_costs = torch.cat((best_costs, costs), dim=0)

        # Keep only the current lowest-cost `max_bitstrings` assignments.
        k = min(max_bitstrings, merged_costs.shape[0])
        top = torch.topk(merged_costs, k, largest=False).indices
        best_bits = merged_bits[top]
        best_costs = merged_costs[top]

        if time.perf_counter() >= deadline:
            break

    solution = Solution(
        bitstrings=bitstrings.as_tensor(best_bits),
        costs=best_costs,
        counts=vectori.tensor([1] * best_bits.shape[0]),
    )
    return solution._sort_by_cost()._compute_probabilities()

cplex

QUBO solver backed by IBM CPLEX.

Formulates the QUBO problem as a Binary Quadratic Program (BQP) and solves it with IBM CPLEX's branch-and-bound MIP engine, which guarantees an optimal solution within the given time limit.

Note

This module requires the cplex Python package (part of IBM CPLEX Optimization Studio) to be installed. Install it with the extras extra: pip install 'qubo-solver[extras]'.

Functions:

solve –

Solve a QUBO instance to optimality (or time limit) using IBM CPLEX.

solve

solve(instance: Instance, *, time_limit: float = float('inf'), log_path: str = '') -> Solution

Solve a QUBO instance to optimality (or time limit) using IBM CPLEX.

Parameters:

instance (Instance) –

The QUBO instance to solve.
time_limit (float, default: float('inf') ) –

Wall-clock time limit for CPLEX in seconds. CPLEX returns the best feasible solution found so far when the limit is reached.
log_path (str, default: '' ) –

File path where CPLEX log output (progress, warnings, errors) is written, opened in write mode ("w"), so any existing file is overwritten. When empty (the default), logging is suppressed and no file is created.

Returns:

Solution –

A solution containing exactly one bitstring — the best (or optimal) solution found by CPLEX.

Source code in qubosolver/solving/classical/cplex.py

def solve(instance: Instance, *, time_limit: float = float("inf"), log_path: str = "") -> Solution:
    """Solve a QUBO instance to optimality (or time limit) using IBM CPLEX.

    Args:
        instance: The QUBO instance to solve.
        time_limit: Wall-clock time limit for CPLEX in seconds. CPLEX returns
            the best feasible solution found so far when the limit is
            reached.
        log_path: File path where CPLEX log output (progress, warnings,
            errors) is written, opened in write mode (``"w"``), so any
            existing file is overwritten. When empty (the default), logging
            is suppressed and no file is created.

    Returns:
        A solution containing exactly one bitstring — the best (or
            optimal) solution found by CPLEX.
    """
    # If there are no variables, return an empty solution.
    if not instance:
        return Solution.zeros(0)

    # Open a log file, or a no-op context manager if none was requested.
    with open(log_path, "w") if log_path else contextlib.nullcontext() as log_file:
        problem = _to_cplex(instance, log_file=log_file)
        if math.isfinite(time_limit):
            problem.parameters.timelimit.set(time_limit)

        problem.solve()

        # Retrieve solution.
        solution = _to_solution(problem.solution)

    return solution

iterative_bitflip_local_search

Bit-flip local search for QUBO solutions.

This module provides greedy single-bit-flip local search strategies that improve a batch of candidate bitstrings by iteratively flipping bits, stopping when no flip improves the objective, a maximum number of iterations is reached, or a shared time budget is exhausted.

The main public entry point is solve, which applies the selected strategy to every bitstring in an existing Solution, or to a batch of uniformly random candidates generated on the fly. It is used as a post-processing step in Solver. "best_improvement" runs every bitstring in lockstep as a single batched search; "first_improvement" and "greedy_sweep" improve each bitstring independently.

Functions:

solve –

Improve every bitstring in starts via single-bit-flip local search.

solve

solve(instance: Instance, *, starts: Solution | int = 1, strategy: Literal['greedy_sweep', 'best_improvement', 'first_improvement'] = 'greedy_sweep', max_iterations: int = -1, time_limit: float = float('inf')) -> Solution

Improve every bitstring in starts via single-bit-flip local search.

Bitstrings driven to the same local minimum are merged afterwards via deduplicate.

time_limit is a global budget for the whole batch of bitstrings in starts, not a per-bitstring limit. Once it is exhausted, any remaining bitstrings are left unchanged, with their original cost.

Parameters:

instance (Instance) –

The instance used to evaluate bitstring costs.
starts (Solution | int, default: 1 ) –

Either the Solution to refine, or an int giving the number of uniformly random candidate bitstrings to draw via random_sampling.solve, which may return fewer than requested after deduplication. This random draw is not reproducible via a caller-supplied rng; callers who need reproducibility should sample their own Solution (e.g. with a seeded random_sampling.solve) and pass it in directly.
strategy (Literal['greedy_sweep', 'best_improvement', 'first_improvement'], default: 'greedy_sweep' ) –

Which local-search strategy to use: "best_improvement", "first_improvement", or "greedy_sweep".
max_iterations (int, default: -1 ) –

For "first_improvement" and "greedy_sweep", the maximum number of accepted flips per bitstring. For "best_improvement", the maximum number of batch rounds: each round applies one flip to every bitstring that still has an improving one, so a bitstring may converge in fewer rounds than this cap, and different bitstrings can converge after different numbers of flips under the same cap. Defaults to -1, i.e. no limit.
time_limit (float, default: float('inf') ) –

Maximum total time in seconds for the whole batch. Defaults to float('inf'), i.e. no limit.

Returns:

Solution –

A new solution with updated bitstrings, costs, counts, and probabilities reflecting the locally optimal results.

Raises:

ValueError –

If strategy is not one of the supported strategies.
ValueError –

If starts bitstrings do not have length instance.size.

Source code in qubosolver/solving/classical/iterative_bitflip_local_search.py

def solve(
    instance: Instance,
    *,
    starts: Solution | int = 1,
    strategy: Literal["greedy_sweep", "best_improvement", "first_improvement"] = "greedy_sweep",
    max_iterations: int = -1,
    time_limit: float = float("inf"),
) -> Solution:
    """Improve every bitstring in `starts` via single-bit-flip local search.

    Bitstrings driven to the same local minimum are merged afterwards via
    [`deduplicate`][qubosolver.Solution.deduplicate].

    `time_limit` is a *global* budget for the whole batch of bitstrings in
    `starts`, not a per-bitstring limit. Once it is exhausted, any
    remaining bitstrings are left unchanged, with their original cost.

    Args:
        instance: The instance used to evaluate bitstring costs.
        starts: Either the [`Solution`][] to refine, or an ``int`` giving
            the number of uniformly random candidate bitstrings to draw
            via [`random_sampling.solve`][],
            which may return fewer than requested after deduplication. This
            random draw is *not* reproducible via a caller-supplied `rng`;
            callers who need reproducibility should sample their own
            [`Solution`][] (e.g. with a seeded [`random_sampling.solve`][])
            and pass it in directly.
        strategy: Which local-search strategy to use: ``"best_improvement"``,
            ``"first_improvement"``, or ``"greedy_sweep"``.
        max_iterations: For ``"first_improvement"`` and ``"greedy_sweep"``,
            the maximum number of accepted flips per bitstring. For
            ``"best_improvement"``, the maximum number of *batch rounds*:
            each round applies one flip to every bitstring that still has
            an improving one, so a bitstring may converge in fewer rounds
            than this cap, and different bitstrings can converge after
            different numbers of flips under the same cap. Defaults to
            `-1`, i.e. no limit.
        time_limit: Maximum total time in seconds for the whole batch.
            Defaults to `float('inf')`, i.e. no limit.

    Returns:
        A new solution with updated `bitstrings`, `costs`, `counts`,
            and `probabilities` reflecting the locally optimal results.

    Raises:
        ValueError: If `strategy` is not one of the supported strategies.
        ValueError: If `starts` bitstrings do not have length `instance.size`.
    """
    if strategy != "best_improvement" and strategy not in _ROW_STRATEGIES:
        raise ValueError(f"Unknown postprocessing strategy: {strategy}")

    if isinstance(starts, int):
        solution = random_sampling_solve(instance, max_bitstrings=starts)
    else:
        solution = deepcopy(starts)

    # If there are no bitstrings, return the solution unchanged.
    if not solution:
        return solution

    if solution.bitstrings.shape[1] != instance.size:
        raise ValueError(
            f"starts has bitstrings of length {solution.bitstrings.shape[1]}, "
            f"but instance.size is {instance.size}."
        )

    if instance.size == 0:
        return Solution.zeros(0, count=len(solution))

    if strategy == "best_improvement":
        # best_improvement is batched over every row at once instead of
        # looping row by row, so it needs its own dispatch path here.
        solution.bitstrings = _best_improvement_search_batch(
            instance.matrix,
            solution.bitstrings,
            max_iterations=max_iterations,
            time_limit=time_limit,
        )
    else:
        search_fn = _ROW_STRATEGIES[strategy]
        deadline = time.monotonic() + time_limit

        for i, sol in enumerate(solution):
            # Get the current solution (row) as a numpy array of integers.
            s_orig = sol.bitstring

            # `time_limit` is a budget for the whole batch, so each row gets
            # only what is left of it, not a fresh full budget.
            remaining = deadline - time.monotonic()
            if remaining <= 0.0:
                break

            # Apply bit-flip local search to improve the solution.
            solution.bitstrings[i, :] = search_fn(
                instance.matrix,
                s_orig,
                rng=None,
                max_iterations=max_iterations,
                time_limit=remaining,
            )

    # The incremental deltas used above can drift from the true x^T Q x by a
    # few ULPs; recompute exactly rather than trusting the accumulated value.
    solution._compute_costs(instance.matrix)
    solution.deduplicate()

    return solution

random_sampling

Uniform random bitstring sampler for QUBO instances.

Functions:

solve –

Sample uniformly random bitstring solutions for a QUBO instance.

solve

solve(instance: Instance, *, max_bitstrings: int = 1, rng: torch.Generator | None = None) -> Solution

Sample uniformly random bitstring solutions for a QUBO instance.

Draws max_bitstrings independent binary vectors uniformly at random, deduplicates them (identical samples are merged and their draw count is accumulated in counts), evaluates the QUBO cost of each unique bitstring.

Note

Because of deduplication, the returned solution may contain fewer than max_bitstrings bitstrings when the same random vector is drawn more than once.

Parameters:

instance (Instance) –

The QUBO instance whose coefficient matrix is used to evaluate bitstring costs.
max_bitstrings (int, default: 1 ) –

Number of random bitstrings to draw before deduplication. The returned solution may contain fewer unique bitstrings.
rng (torch.Generator | None, default: None ) –

PyTorch random number generator controlling the sampling.

Returns:

Solution –

A solution with unique bitstrings, their QUBO costs, draw counts, and probabilities.

Source code in qubosolver/solving/classical/random_sampling.py

def solve(
    instance: Instance,
    *,
    max_bitstrings: int = 1,
    rng: torch.Generator | None = None,
) -> Solution:
    """Sample uniformly random bitstring solutions for a QUBO instance.

    Draws `max_bitstrings` independent binary vectors uniformly at random,
    deduplicates them (identical samples are merged and their draw count is
    accumulated in `counts`), evaluates the QUBO cost of each unique
    bitstring.

    Note:
        Because of deduplication, the returned solution may contain fewer than
        `max_bitstrings` bitstrings when the same random vector is drawn more
        than once.

    Args:
        instance: The QUBO instance whose coefficient matrix is used to
            evaluate bitstring costs.
        max_bitstrings: Number of random bitstrings to draw before
            deduplication.  The returned solution may contain fewer unique
            bitstrings.
        rng: PyTorch random number generator controlling the sampling.

    Returns:
        A solution with unique bitstrings, their QUBO costs, draw counts, and probabilities.
    """
    rng = rng or torch_rng()
    solution = Solution(
        bitstrings=bitstrings.rand(max_bitstrings, instance.size, rng=rng),
        costs=vector.zeros(max_bitstrings),
        counts=vectori.zeros(max_bitstrings).fill_(1),
        probabilities=vector.zeros(max_bitstrings),
    )
    solution = solution.deduplicate(update=False)._update(instance)

    return solution

simulated_annealing

Simulated Annealing solver for QUBO problems.

Implements a bit-flip annealer that minimizes the quadratic objective \(E(x) = x^T Q x\) over binary vectors \(x \\in \\{0,1\\}^n\), run independently from each of a batch of starting points and merged into a single solution.

Functions:

solve –

Run Simulated Annealing on a QUBO instance from each of a batch of starting points.

solve

solve(instance: Instance, starts: Bitstrings | int = 1, *, merge: bool = True, top_k: int = 1, max_iter: int = 1000, initial_temp: float = 5.0, final_temp: float = 0.001, cooling_rate: float | None = None, time_limit: float = float('inf'), rng: torch.Generator | None = None, stats: Literal['per_run', 'full'] = 'per_run', vectorized: bool = True) -> Solution | list[Solution]

Run Simulated Annealing on a QUBO instance from each of a batch of starting points.

For each starting bitstring, at each of max_iter steps a random bit is proposed for flipping. The flip is always accepted when it reduces the energy; otherwise it is accepted with probability \(\\exp(-\\Delta E / T)\).

Up to top_k unique lowest-energy bitstrings encountered during each run are retained, along with how many iterations were spent at each one (whether or not the proposed flip at that iteration was accepted). The runs are independent. By default (merge=True) the per-start results are merged into a single Solution. Pass merge=False to instead get back the unmerged, one-per-start list.

Example

Running a single explicit start requires promoting it to a batch of size 1 first, via torch.unsqueeze:

solution = simulated_annealing(instance, start.unsqueeze(0))

Passing merge=False returns the per-start results instead of a single merged Solution:

solutions = simulated_annealing(instance, starts, merge=False)

Parameters:

instance (Instance) –

The QUBO instance to solve. Its coefficient matrix is symmetrised internally as (Q + Qᵀ) / 2.
starts (Bitstrings | int, default: 1 ) –

Either a batch of initial binary solutions, a tensor of shape (k, n) with values in {0, 1} (one independent run is performed per row), or an int giving the number of uniformly random starts to generate.
merge (bool, default: True ) –

When True (default), merge the per-start results into a single Solution. When False, return the unmerged list of one Solution per starting point (same order as starts).
top_k (int, default: 1 ) –

Maximum number of unique best solutions to keep per run, ordered by ascending energy.
max_iter (int, default: 1000 ) –

Number of bit-flip proposals to perform.
initial_temp (float, default: 5.0 ) –

Starting temperature \(T_0\). Higher values increase the probability of accepting uphill moves early in the search.
final_temp (float, default: 0.001 ) –

Target temperature \(T_f\) at the end of the schedule, used to derive the cooling rate when cooling_rate is None. Ignored when cooling_rate is provided explicitly.
cooling_rate (float | None, default: None ) –

Geometric cooling factor \(\\alpha \\in (0, 1)\) such that \(T \\leftarrow \\alpha T\) at each step. When None (default), \(\\alpha\) is derived automatically from initial_temp, final_temp, and max_iter so that the temperature reaches final_temp after max_iter steps.
time_limit (float, default: float('inf') ) –

Wall-clock budget in seconds. The algorithm stops early when either max_iter steps or the time limit is reached, whichever comes first. Defaults to float("inf") (no limit). With vectorized=True this is a single budget for the whole batch of starts, which all stop at the same iteration; with vectorized=False each start gets its own budget.
rng (torch.Generator | None, default: None ) –

PyTorch random number generator used for bit selection and acceptance sampling. When None (default), a new generator is created; pass an explicit generator for reproducibility across calls. Note that vectorized changes the order in which draws are consumed, so a given seed produces the same result only for a fixed value of vectorized.
stats (Literal['per_run', 'full'], default: 'per_run' ) –

When "per_run" (default), each run's retained bitstrings are counted as 1 instead of how many iterations were spent at each one, before any merging. This is mainly meant for top_k=1 together with merge=True, where the merged count directly reflects how many of the runs converged on each bitstring. With merge=True and top_k > 1, or whenever a bitstring is retained by more than one run, deduplicate sums those per-run 1s, so counts on the merged result are generally neither 1 nor uniform. When "full", counts instead reflect how many iterations were spent at each bitstring.
vectorized (bool, default: True ) –

When True (default), step every start forward together so each iteration costs a handful of batched tensor operations regardless of how many starts there are -- markedly faster for large batches. When False, anneal the starts one at a time; this is the reference implementation, kept for comparison. The two run the same algorithm but differ in time_limit scope and in RNG draw order (see time_limit and rng).

Returns:

Solution | list[Solution] –

When merge=True, a single Solution merging every start's results. When merge=False, one Solution per starting point (same order as starts). Either way, each Solution contains up to top_k unique bitstrings sorted by ascending energy, with their costs, counts (see stats), and probabilities.

Raises:

ValueError –

If top_k < 1.
ValueError –

If initial_temp <= 0.
ValueError –

If cooling_rate is None and final_temp <= 0.
ValueError –

If cooling_rate is provided but not in (0, 1).
ValueError –

If starts bitstrings do not have length instance.size.

Source code in qubosolver/solving/classical/simulated_annealing.py

@torch.no_grad()
def solve(
    instance: Instance,
    starts: Bitstrings | int = 1,
    *,
    merge: bool = True,
    top_k: int = 1,
    max_iter: int = 1000,
    initial_temp: float = 5.0,
    final_temp: float = 1e-3,
    cooling_rate: float | None = None,
    time_limit: float = float("inf"),
    rng: torch.Generator | None = None,
    stats: Literal["per_run", "full"] = "per_run",
    vectorized: bool = True,
) -> Solution | list[Solution]:
    r"""Run Simulated Annealing on a QUBO instance from each of a batch of starting points.

    For each starting bitstring, at each of `max_iter` steps a random bit is
    proposed for flipping.  The flip is always accepted when it reduces the
    energy; otherwise it is accepted with probability $\\exp(-\\Delta E / T)$.

    Up to `top_k` unique lowest-energy bitstrings encountered during each run
    are retained, along with how many iterations were spent at each one
    (whether or not the proposed flip at that iteration was accepted). The
    runs are independent.  By default (``merge=True``) the per-start results
    are merged into a single [`Solution`][]. Pass ``merge=False`` to instead
    get back the unmerged, one-per-start list.

    Example:
        Running a single explicit start requires promoting it to a batch of
        size 1 first, via [`torch.unsqueeze`][]:

        ```python
        solution = simulated_annealing(instance, start.unsqueeze(0))
        ```

        Passing ``merge=False`` returns the per-start results instead of a
        single merged `Solution`:

        ```python
        solutions = simulated_annealing(instance, starts, merge=False)
        ```

    Args:
        instance: The QUBO instance to solve.  Its coefficient matrix is
            symmetrised internally as ``(Q + Qᵀ) / 2``.
        starts: Either a batch of initial binary solutions, a tensor of
            shape ``(k, n)`` with values in ``{0, 1}`` (one independent run
            is performed per row), or an ``int`` giving the number of
            uniformly random starts to generate.
        merge: When ``True`` (default), merge the per-start results into a
            single [`Solution`][]. When ``False``, return the unmerged list of one
            [`Solution`][] per starting point (same order as `starts`).
        top_k: Maximum number of unique best solutions to keep per run,
            ordered by ascending energy.
        max_iter: Number of bit-flip proposals to perform.
        initial_temp: Starting temperature $T_0$.  Higher values increase the
            probability of accepting uphill moves early in the search.
        final_temp: Target temperature $T_f$ at the end of the schedule, used
            to derive the cooling rate when `cooling_rate` is ``None``.
            Ignored when `cooling_rate` is provided explicitly.
        cooling_rate: Geometric cooling factor $\\alpha \\in (0, 1)$ such that
            $T \\leftarrow \\alpha T$ at each step.  When ``None`` (default),
            $\\alpha$ is derived automatically from `initial_temp`,
            `final_temp`, and `max_iter` so that the temperature reaches
            `final_temp` after `max_iter` steps.
        time_limit: Wall-clock budget in seconds.  The algorithm stops early
            when either `max_iter` steps or the time limit is reached,
            whichever comes first.  Defaults to ``float("inf")`` (no limit).
            With ``vectorized=True`` this is a single budget for the whole
            batch of starts, which all stop at the same iteration; with
            ``vectorized=False`` each start gets its own budget.
        rng: PyTorch random number generator used for bit selection and
            acceptance sampling.  When ``None`` (default), a new generator is
            created; pass an explicit generator for reproducibility across
            calls.  Note that `vectorized` changes the order in which draws
            are consumed, so a given seed produces the same result only for a
            fixed value of `vectorized`.
        stats: When ``"per_run"`` (default), each run's retained bitstrings
            are counted as ``1`` instead of how many iterations were spent
            at each one, before any merging. This is mainly meant for
            ``top_k=1`` together with ``merge=True``, where the merged count
            directly reflects how many of the runs converged on each
            bitstring. With ``merge=True`` and ``top_k > 1``, or whenever a
            bitstring is retained by more than one run, [`deduplicate`][Solution.deduplicate] sums
            those per-run ``1``s, so counts on the merged result are
            generally neither ``1`` nor uniform. When ``"full"``, counts
            instead reflect how many iterations were spent at each
            bitstring.
        vectorized: When ``True`` (default), step every start forward together
            so each iteration costs a handful of batched tensor operations
            regardless of how many starts there are -- markedly faster for
            large batches. When ``False``, anneal the starts one at a time;
            this is the reference implementation, kept for comparison. The two
            run the same algorithm but differ in `time_limit` scope and in RNG
            draw order (see `time_limit` and `rng`).

    Returns:
        When ``merge=True``, a single [`Solution`][] merging every start's
            results.  When ``merge=False``, one [`Solution`][] per starting
            point (same order as `starts`).  Either way, each [`Solution`][]
            contains up to `top_k` unique bitstrings sorted by ascending energy,
            with their costs, counts (see `stats`), and probabilities.

    Raises:
        ValueError: If ``top_k < 1``.
        ValueError: If ``initial_temp <= 0``.
        ValueError: If ``cooling_rate`` is ``None`` and ``final_temp <= 0``.
        ValueError: If ``cooling_rate`` is provided but not in ``(0, 1)``.
        ValueError: If `starts` bitstrings do not have length `instance.size`.
    """
    if top_k <= 0:
        raise ValueError("top_k must be >= 1.")
    if rng is None:
        rng = torch_rng()
    if stats == "per_run" and top_k > 1:
        logger.info(
            f"stats='per_run' with top_k={top_k}: per-run counts are set to 1, but merging "
            "sums them across runs, so merged counts are not simply 1 per run."
        )

    n = instance.size

    alpha = _cooling_rate(
        max_iter=max_iter,
        initial_temp=initial_temp,
        final_temp=final_temp,
        cooling_rate=cooling_rate,
    )

    if isinstance(starts, int):
        starts = bitstrings.rand(starts, n, rng=rng)

    if starts.shape[0] == 0:
        return Solution() if merge else []

    if starts.shape[1] != n:
        raise ValueError(
            f"starts has bitstrings of length {starts.shape[1]}, but instance.size is {n}."
        )

    if instance.size == 0:
        count = starts.shape[0]
        return (
            Solution.zeros(0, count=count) if merge else [Solution.zeros(0) for _ in range(count)]
        )

    runner = _run_vectorized if vectorized else _run_sequential
    solutions = runner(
        instance,
        starts,
        top_k=top_k,
        max_iter=max_iter,
        initial_temp=initial_temp,
        alpha=alpha,
        time_limit=time_limit,
        rng=rng,
        stats=stats,
    )

    if merge:
        return Solution.concat(solutions).deduplicate()

    return solutions

tabu_search

Tabu Search solver for QUBO problems.

A single-neighborhood tabu search that explores bit-flip moves in parallel across multiple starting points.

Functions:

solve –

Perform Tabu Search on a QUBO instance to find low-cost bitstrings.

solve

solve(instance: Instance, *, starts: Bitstrings | int = 1, max_iter: int = 100, tabu_tenure: int = 7, max_no_improve: int = 20, time_limit: float = float('inf')) -> Solution

Perform Tabu Search on a QUBO instance to find low-cost bitstrings.

Runs one independent search per row of starts, each exploring single-bit-flip neighbors from its own starting point. A tabu list prevents revisiting recently flipped bits; aspiration overrides the tabu restriction whenever a move yields a new global best. All independent runs share the same stopping criteria and are deduplicated before being returned.

Parameters:

instance (Instance) –

The QUBO instance providing the cost matrix.
starts (Bitstrings | int, default: 1 ) –

Either a batch of initial binary solutions, one row per independent run, each of length n, or an int giving the number of uniformly random starts to generate. This random draw is not reproducible via a caller-supplied rng; callers who need reproducibility should sample their own Bitstrings (e.g. with a seeded bitstrings.rand) and pass it in directly.
max_iter (int, default: 100 ) –

Maximum number of search iterations.
tabu_tenure (int, default: 7 ) –

Number of iterations a bit-flip move stays tabu.
max_no_improve (int, default: 20 ) –

Maximum consecutive iterations without improvement before a run is considered stagnated. Search stops early when all independent runs have stagnated.
time_limit (float, default: float('inf') ) –

Wall-clock time budget in seconds. Defaults to float('inf') (no limit).

Returns:

Solution –

Deduplicated best bitstrings found across all runs, together with their objective values and occurrence counts, sorted by ascending cost.

Raises:

ValueError –

If starts bitstrings do not have length instance.size.

Source code in qubosolver/solving/classical/tabu_search.py

def solve(
    instance: Instance,
    *,
    starts: Bitstrings | int = 1,
    max_iter: int = 100,
    tabu_tenure: int = 7,
    max_no_improve: int = 20,
    time_limit: float = float("inf"),
) -> Solution:
    """Perform Tabu Search on a QUBO instance to find low-cost bitstrings.

    Runs one independent search per row of `starts`, each exploring
    single-bit-flip neighbors from its own starting point.  A tabu list
    prevents revisiting recently flipped bits; aspiration overrides the tabu
    restriction whenever a move yields a new global best.  All independent
    runs share the same stopping criteria and are deduplicated before being
    returned.

    Args:
        instance: The QUBO instance providing the cost matrix.
        starts: Either a batch of initial binary solutions, one row per
            independent run, each of length ``n``, or an ``int`` giving the
            number of uniformly random starts to generate. This random draw
            is *not* reproducible via a caller-supplied `rng`; callers who
            need reproducibility should sample their own [`Bitstrings`][]
            (e.g. with a seeded [`bitstrings.rand`][]) and pass it in
            directly.
        max_iter: Maximum number of search iterations.
        tabu_tenure: Number of iterations a bit-flip move stays tabu.
        max_no_improve: Maximum consecutive iterations without improvement
            before a run is considered stagnated.  Search stops early when
            **all** independent runs have stagnated.
        time_limit: Wall-clock time budget in seconds. Defaults to
            ``float('inf')`` (no limit).

    Returns:
        Deduplicated best bitstrings found across all runs, together with their objective
            values and occurrence counts, sorted by ascending cost.

    Raises:
        ValueError: If `starts` bitstrings do not have length `instance.size`.
    """
    if isinstance(starts, int):
        starts = bitstrings.rand(starts, instance.size)

    if starts.shape[1] != instance.size:
        raise ValueError(
            f"starts has bitstrings of length {starts.shape[1]}, "
            f"but instance.size is {instance.size}."
        )

    if instance.size == 0:
        return Solution.zeros(0, count=starts.shape[0])

    Q = instance.matrix
    device = Q.device
    n_bitstrings, n = starts.shape

    # Repeat x0 for each parallel run
    X = starts.detach().clone().to(Q)
    QX = X @ Q
    f_current = (X * QX).sum(dim=1)
    x_best = X.clone()
    f_best = f_current.clone()

    # Tabu list per run and bit
    tabu_list = torch.zeros((n_bitstrings, n), dtype=torch.int64, device=device)
    iter_since_last_improve = torch.zeros(n_bitstrings, dtype=torch.int64, device=device)

    deadline = time.perf_counter() + time_limit
    rows = torch.arange(n_bitstrings, device=device)
    cols = torch.arange(n, device=device)
    diagonal = Q.diagonal()
    dE_buffer = torch.empty_like(QX)

    for iteration in range(max_iter):
        if time.perf_counter() >= deadline:
            break

        # `f_current` and `QX` are accumulated incrementally below, so each
        # step adds a rounding error that leaves them a few ULPs off the true
        # x^T Q x. Recomputing them exactly every _REFRESH_EVERY iterations
        # keeps that error from growing unbounded, at the cost of one extra
        # matmul amortized over many iterations.
        if iteration % _REFRESH_EVERY == 0:
            QX = X @ Q
            f_current = (X * QX).sum(dim=1)

        # Tabu tenure counts down to 0 every iteration, regardless of whether
        # a move is made; a bit is tabu while its counter is still positive.
        tabu_list.sub_(1).clamp_(min=0)

        # Delta of each candidate one-bit-flip move, for every run at once;
        # avoids recomputing the full x^T Q x per candidate.
        dE = _flip_deltas(Q, X, QX, diagonal=diagonal, out=dE_buffer)
        f_candidates = f_current.unsqueeze(1) + dE

        # Tabu and aspiration
        tabu_mask = tabu_list > 0
        aspiration_mask = f_candidates < f_best.unsqueeze(1)
        allowed = (~tabu_mask) | aspiration_mask

        # Mask out disallowed moves
        f_masked = torch.where(allowed, f_candidates, torch.inf)

        # Pick best move per run
        best_moves = torch.argmin(f_masked, dim=1)
        move_mask = cols.unsqueeze(0) == best_moves.unsqueeze(1)

        # Apply the best move
        xi = X[rows, best_moves]
        step = 1.0 - 2.0 * xi
        X[rows, best_moves] = xi + step
        QX += step.unsqueeze(1) * Q[best_moves, :]
        # Read the new cost from `f_candidates`, not from the tabu-masked
        # `f_masked`: when every move of a run is disallowed, `f_masked` is
        # all-`inf` for that row and its minimum is the `inf` sentinel, not a
        # real cost. `f_current` is persistent state, so assigning that
        # sentinel here would make every later `f_current + dE` `inf` too --
        # including at allowed positions -- which also disables aspiration
        # (`inf < f_best` is never true) and stops the run searching.
        f_current = f_candidates[rows, best_moves]
        tabu_list[move_mask] = tabu_tenure

        # Update best solutions
        improved = f_current < f_best
        x_best[improved] = X[improved]
        f_best[improved] = f_current[improved]
        iter_since_last_improve += 1
        iter_since_last_improve[improved] = 0

        # Early stop if all stagnated
        if torch.all(iter_since_last_improve >= max_no_improve):
            break

    # `f_best` was accumulated incrementally, drifting from the true x^T Q x
    # by up to _REFRESH_EVERY steps of rounding error. `deduplicate` picks the
    # row to keep per bitstring based on that drifted cost, so skip its own
    # recompute (`update=False`) and instead recompute exactly via `_update`
    # right after.
    solution = Solution(
        bitstrings=bitstrings.as_tensor(x_best),
        costs=f_best,
        counts=vectori.zeros(n_bitstrings).fill_(1),
        probabilities=vector.zeros(n_bitstrings).fill_(1.0 / n_bitstrings),
    )
    return solution.deduplicate(update=False)._update(instance)

trivial_solution_search

Trivial QUBO solution detection.

Recognizes coefficient patterns whose optimal solution can be read off analytically without any search.

Functions:

solve –

Solve a QUBO when the coefficient structure is trivial.

solve

solve(instance: Instance) -> Solution

Solve a QUBO when the coefficient structure is trivial.

Three patterns are recognised:

All coefficients ≥ 0 — the all-zeros bitstring 0^n is optimal.
All coefficients ≤ 0 — the all-ones bitstring 1^n is optimal.
Diagonal matrix — each variable is independent; bits with a negative diagonal entry are set to 1, the rest to 0.

Parameters:

instance (Instance) –

The QUBO problem whose matrix is inspected.

Returns:

Solution –

A single-bitstring solution when a trivial case is detected, or an empty solution (no bitstrings) when none of the three patterns apply.

Source code in qubosolver/solving/classical/trivial_solution_search.py

def solve(instance: Instance) -> Solution:
    """Solve a QUBO when the coefficient structure is trivial.

    Three patterns are recognised:

    1. **All coefficients ≥ 0** — the all-zeros bitstring ``0^n`` is optimal.
    2. **All coefficients ≤ 0** — the all-ones bitstring ``1^n`` is optimal.
    3. **Diagonal matrix** — each variable is independent; bits with a
       negative diagonal entry are set to `1`, the rest to `0`.

    Args:
        instance: The QUBO problem whose matrix is inspected.

    Returns:
        A single-bitstring solution when a trivial case is
            detected, or an empty solution (no bitstrings) when none of the three patterns apply.
    """
    coeffs = instance.matrix
    n = instance.size

    # Case 1: all coeffs >= 0 → x = [0,...,0]
    if torch.all(coeffs >= 0):
        raw = bitstring.zeros(n)
        # always make a batch of one: shape (1, n)
        batch = raw.unsqueeze(0)
        cost = instance.cost(raw)
        return Solution(
            bitstrings=batch,
            counts=vectori.tensor([1]),
            costs=vector.tensor([cost]),
            probabilities=vector.tensor([1.0]),
        )

    # Case 2: all coeffs <= 0 → x = [1,...,1]
    if torch.all(coeffs <= 0):
        raw = torch.ones(n, dtype=bitstring.dtype())
        # always make a batch of one: shape (1, n)
        batch = raw.unsqueeze(0)
        cost = instance.cost(raw)
        return Solution(
            bitstrings=batch,
            counts=vectori.tensor([1]),
            costs=vector.tensor([cost]),
            probabilities=vector.tensor([1.0]),
        )

    # Case 3: diagonal cases
    # negative coeffs gets 1, positive gets 0
    diagonal = torch.diag(coeffs)
    if (torch.diag(diagonal) == coeffs).all():
        raw = (diagonal < 0).to(bitstring.dtype())
        cost = instance.cost(raw)
        batch = raw.unsqueeze(0)
        return Solution(
            bitstrings=batch,
            counts=vectori.tensor([1]),
            costs=vector.tensor([cost]),
            probabilities=vector.tensor([1.0]),
        )

    return Solution()