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

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.
  • 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

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.
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

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.

Was this page helpful?