Search Algorithms

  • Short Name: TS
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
Tabu Search is a heuristic optimization method that works with the help of a tabu list. Initially, random states are chosen in the solution landscape. Afterwards, an iterative search for energetically better states in the neighborhood is started from these states. According to a tabu strategy, states are added to the tabu list that are not allowed to be selected as successor states for a tabu duration. The tabu search ends as soon as there are no better successor states in the neighborhood. The resulting state is therefore the solution to the problem.

Usage via LunaSolve

# Example of using TS using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="TS",
    provider="dwave",
    solver_parameters={
        "num_reads": None,
        "tenure": None,
        "timeout": 100,
        "initial_states_generator": "random",
        "initial_states": None,
        "seed": None,
        "num_restarts": 1000000,
        "energy_threshold": None,
        "coefficient_z_first": None,
        "coefficient_z_restart": None,
        "lower_bound_z": None,
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding TS using the Luna backend as an algorithm to LunaBench
algorithms = {
    "TS": {
        "location": "cloud",
        "provider": "dwave",
    },
}

Backends

This algorithm can be run on the following backends:

Luna

Tabu Search available on Luna
Luna provides powerful servers designed to run classical algorithms. These servers offer the computational capacity required to efficiently solve non-quantum tasks, ensuring high performance for optimization and other classical workloads.
Parameters
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the tabu algorithm. If num_reads is not explicitly given, it is selected to match the number of initial states given. If initial states are not provided, only one read is performed.
    Default: None

  • Name
    tenure
    Type
    int | None
    Description

    Tabu tenure, which is the length of the tabu list, or number of recently explored solutions kept in memory. Default is a quarter of the number of problem variables up to a maximum value of 20.
    Default: None

  • Name
    timeout
    Type
    float
    Description

    Maximum running time per read in milliseconds.
    Default: 100

  • Name
    initial_states_generator
    Type
    Literal["none", "tile", "random"]
    Description

    Defines the expansion of initial_states if fewer than num_reads are specified: 'none': if the number of initial states specified is smaller than num_reads, raises ValueError. 'tile': reuses the specified initial states if fewer than num_reads or truncates if greater. 'random': expands the specified initial states with randomly generated states if fewer than num_reads or truncates if greater.
    Default: "random"

  • Name
    initial_states
    Type
    Any | None
    Description

    One or more samples, each defining an initial state for all the problem variables. Initial states are given one per read, but if fewer than num_reads initial states are defined, additional values are generated as specified by initial_states_generator.
    Default: None

  • Name
    seed
    Type
    int | None
    Description

    32-bit unsigned integer seed to use for the PRNG. If the timeout parameter is not None, results from the same seed may not be identical between runs due to finite clock resolution.
    Default: None

  • Name
    num_restarts
    Type
    int
    Description

    Maximum number of tabu search restarts per read. Setting this value to zero results in a simple tabu search.
    Default: 1000000

  • Name
    energy_threshold
    Type
    float | None
    Description

    Terminate when an energy lower than or equal to energy_threshold is found.
    Default: None

  • Name
    coefficient_z_first
    Type
    int | None
    Description

    max(bqm.num_variables*coefficient_z_first, lower_bound_z) bounds the number of variable updates considered in the first simple tabu search (STS). Variable updates arising from the STS greedy-descent subroutine, invoked upon discovery of new global optima, are excluded from the count. The coefficient defaults to 10_000 for small problems (up to 500 variables) and 25_000 for larger problems.
    Default: None

  • Name
    coefficient_z_restart
    Type
    int | None
    Description

    Controls the number of variable updates on restarted simple tabu search stages, matching the description for coefficient_z_first. The coefficient defaults to coefficient_z_first/4
    Default: None

  • Name
    lower_bound_z
    Type
    int | None
    Description

    Sets a minimum number of variable updates on all simple tabu searches, see coefficient_z_first. The bound defaults to 500_000.
    Default: None

  • Short Name: DS
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
The Dialectic Search Solver uses a path search between two states representing the thesis and antithesis. A greedy search is used to reduce the energy by applying bit flips in an attempt to find the solution.

For the Dialectic Search Solver, if the target keyword is set, the max_iter keyword is ignored. If the timeout keyword is provided, the max_time keyword is ignored. However, both can be used as equivalents. Both options are available for a more convenient interaction over multiple different solvers expecting different parameter names, esentially tuning the same thing.

Usage via LunaSolve

# Example of using DS using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="DS",
    provider="dwave",
    solver_parameters={
        "decomposer": {
            "size": 10,
            "min_gain": None,
            "rolling": True,
            "rolling_history": 1.0,
            "silent_rewind": True,
            "traversal": "energy",
        },
        "tabu_antithesis": {
            "num_reads": None,
            "tenure": None,
            "timeout": 100,
            "initial_states_generator": "random",
        },
        "tabu_synthesis": {
            "num_reads": None,
            "tenure": None,
            "timeout": 100,
            "initial_states_generator": "random",
        },
        "loop": {
            "max_iter": 100,
            "max_time": 5,
            "convergence": 3,
            "target": None,
            "rtol": 1e-05,
            "atol": 1e-08,
        },
        "max_tries": 100,
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding DS using the Luna backend as an algorithm to LunaBench
algorithms = {
    "DS": {
        "location": "cloud",
        "provider": "dwave",
    },
}

Backends

This algorithm can be run on the following backends:

Luna

Dialectic Search available on Luna
Luna provides powerful servers designed to run classical algorithms. These servers offer the computational capacity required to efficiently solve non-quantum tasks, ensuring high performance for optimization and other classical workloads.
Parameters
  • Name
    decomposer
    Type
    Decomposer
    Description

    Decomposer parameters.
    Default: Decomposer(size=10, min_gain=None, rolling=True, rolling_history=1.0, silent_rewind=True, traversal='energy')

  • Name
    tabu_antithesis
    Type
    Tabu
    Description

    Tabu parameters for the antithesis phase.
    Default: Tabu(num_reads=None, tenure=None, timeout=100, initial_states_generator='random')

  • Name
    tabu_synthesis
    Type
    Tabu
    Description

    Tabu parameters for the synthesis phase.
    Default: Tabu(num_reads=None, tenure=None, timeout=100, initial_states_generator='random')

  • Name
    loop
    Type
    Loop
    Description

    Parameters for the main loop of the algorithm.
    Default: Loop(max_iter=100, max_time=5, convergence=3, target=None, rtol=1e-05, atol=1e-08)

  • Name
    max_tries
    Type
    int | None
    Description

    Maximum number of times the synthesis phase is run for the same input state. On each improvement, the better state is used for the next input state, and the try/trial counter is reset.
    Default: 100

Decomposer
  • Name
    size
    Type
    int
    Description

    Nominal number of variables in the subproblem. Actual subproblem can be smaller, depending on other parameters (e.g. min_gain).
    Default: 10

  • Name
    min_gain
    Type
    float | None
    Description

    Minimum reduction required to BQM energy, given the current sample. A variable is included in the subproblem only if inverting its sample value reduces energy by at least this amount.
    Default: None

  • Name
    rolling
    Type
    bool
    Description

    If True, successive calls for the same problem (with possibly different samples) produce subproblems on different variables, selected by rolling down the list of all variables sorted by decreasing impact.
    Default: True

  • Name
    rolling_history
    Type
    float
    Description

    Fraction of the problem size, as a float in range 0.0 to 1.0, that should participate in the rolling selection. Once reached, subproblem unrolling is reset. Min: 0.0, Max: 1.0
    Default: 1.0

  • Name
    silent_rewind
    Type
    bool
    Description

    If False, raises :exc:EndOfStream when resetting/rewinding the subproblem generator upon the reset condition for unrolling.
    Default: True

  • Name
    traversal
    Type
    Literal["energy", "bfs", "pfs"]
    Description

    Traversal algorithm used to pick a subproblem of size variables. Options are: energy: Use the next size variables in the list of variables ordered by descending energy impact. bfs: Breadth-first traversal seeded by the next variable in the energy impact list. pfs: Priority-first traversal seeded by variables from the energy impact list, proceeding with the variable on the search boundary that has the highest energy impact.
    Default: "energy"

Tabu
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the tabu algorithm. If num_reads is not explicitly given, it is selected to match the number of initial states given. If initial states are not provided, only one read is performed.
    Default: None

  • Name
    tenure
    Type
    int | None
    Description

    Tabu tenure, which is the length of the tabu list, or number of recently explored solutions kept in memory. Default is a quarter of the number of problem variables up to a maximum value of 20.
    Default: None

  • Name
    timeout
    Type
    float
    Description

    Maximum running time per read in milliseconds.
    Default: 100

  • Name
    initial_states_generator
    Type
    Literal["none", "tile", "random"]
    Description

    Defines the expansion of initial_states if fewer than num_reads are specified: 'none': if the number of initial states specified is smaller than num_reads, raises ValueError. 'tile': reuses the specified initial states if fewer than num_reads or truncates if greater. 'random': expands the specified initial states with randomly generated states if fewer than num_reads or truncates if greater.
    Default: "random"

Loop
  • Name
    max_iter
    Type
    int | None
    Description

    Maximum number of iterations.
    Default: 100

  • Name
    max_time
    Type
    int
    Description

    Time in seconds after which the algorithm will stop.
    Default: 5

  • Name
    convergence
    Type
    int
    Description

    Number of iterations with unchanged output to terminate algorithm.
    Default: 3

  • Name
    target
    Type
    float | None
    Description

    Energy level that the algorithm tries to reach.
    Default: None

  • Name
    rtol
    Type
    float
    Description

    Relative tolerance for convergence.
    Default: 1e-05

  • Name
    atol
    Type
    float
    Description

    Absolute tolerance for convergence.
    Default: 1e-08

This solver is only available for commercial and academic licenses.
  • Short Name: QLTS
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
QBSolv Like Tabu Search breaks down the problem and solves the parts individually using a classic solver that uses Tabu Search. This particular implementation uses hybrid.TabuSubproblemSampler as a sampler for the subproblems to achieve a QBSolv like behaviour.

Usage via LunaSolve

# Example of using QLTS using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="QLTS",
    provider="dwave",
    solver_parameters={
        "qbsolv_like": {
            "decomposer_size": 50,
            "rolling": True,
            "rolling_history": 0.15,
            "cpu_count_multiplier": 1,
            "loop": {
                "max_iter": 100,
                "max_time": 5,
                "convergence": 3,
                "target": None,
                "rtol": 1e-05,
                "atol": 1e-08,
            },
        },
        "tabu_search": {
            "num_reads": None,
            "tenure": None,
            "timeout": 100,
            "initial_states_generator": "random",
        },
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding QLTS using the Luna backend as an algorithm to LunaBench
algorithms = {
    "QLTS": {
        "location": "cloud",
        "provider": "dwave",
    },
}

Backends

This algorithm can be run on the following backends:

Luna

QBSolv Like Tabu Search available on Luna
Luna provides powerful servers designed to run classical algorithms. These servers offer the computational capacity required to efficiently solve non-quantum tasks, ensuring high performance for optimization and other classical workloads.
Parameters
  • Name
    qbsolv_like
    Type
    QBSOLVLike
    Description

    Parameters for the QbSolveLike solver.
    Default: QBSOLVLike(decomposer_size=50, rolling=True, rolling_history=0.15, cpu_count_multiplier=1, loop=Loop(max_iter=100, max_time=5, convergence=3, target=None, rtol=1e-05, atol=1e-08))

  • Name
    tabu_search
    Type
    Tabu
    Description

    Parameters for the Tabu Search.
    Default: Tabu(num_reads=None, tenure=None, timeout=100, initial_states_generator='random')

QBSOLVLike
  • Name
    decomposer_size
    Type
    int
    Description

    Size for the decomposer.
    Default: 50

  • Name
    rolling
    Type
    bool
    Description

    Whether to use rolling for the solver.
    Default: True

  • Name
    rolling_history
    Type
    float
    Description

    Rolling history for the solver.
    Default: 0.15

  • Name
    cpu_count_multiplier
    Type
    int
    Description

    CPU count multiplier for the solver.
    Default: 1

  • Name
    loop
    Type
    Loop
    Description

    Parameters for the main loop of the algorithm.
    Default: Loop(max_iter=100, max_time=5, convergence=3, target=None, rtol=1e-05, atol=1e-08)

Tabu
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the tabu algorithm. If num_reads is not explicitly given, it is selected to match the number of initial states given. If initial states are not provided, only one read is performed.
    Default: None

  • Name
    tenure
    Type
    int | None
    Description

    Tabu tenure, which is the length of the tabu list, or number of recently explored solutions kept in memory. Default is a quarter of the number of problem variables up to a maximum value of 20.
    Default: None

  • Name
    timeout
    Type
    float
    Description

    Maximum running time per read in milliseconds.
    Default: 100

  • Name
    initial_states_generator
    Type
    Literal["none", "tile", "random"]
    Description

    Defines the expansion of initial_states if fewer than num_reads are specified: 'none': if the number of initial states specified is smaller than num_reads, raises ValueError. 'tile': reuses the specified initial states if fewer than num_reads or truncates if greater. 'random': expands the specified initial states with randomly generated states if fewer than num_reads or truncates if greater.
    Default: "random"

Loop
  • Name
    max_iter
    Type
    int | None
    Description

    Maximum number of iterations.
    Default: 100

  • Name
    max_time
    Type
    int
    Description

    Time in seconds after which the algorithm will stop.
    Default: 5

  • Name
    convergence
    Type
    int
    Description

    Number of iterations with unchanged output to terminate algorithm.
    Default: 3

  • Name
    target
    Type
    float | None
    Description

    Energy level that the algorithm tries to reach.
    Default: None

  • Name
    rtol
    Type
    float
    Description

    Relative tolerance for convergence.
    Default: 1e-05

  • Name
    atol
    Type
    float
    Description

    Absolute tolerance for convergence.
    Default: 1e-08

Was this page helpful?