Skip to content

TabuSearch

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.


Compatible Backends

The TabuSearch algorithm supports the following backends:

By default, TabuSearch uses the DWave backend.


Initialization

The following section outlines the default configurations of TabuSearch. You can also specify other compatible backends for the algorithm. When backend=None is specified, the default backend will be initialized automatically. In this case, if the backend requires a token, it will be taken from the environment variables.

Default Configuration
from luna_quantum.solve.parameters.algorithms import TabuSearch

algorithm = TabuSearch(
    backend=None,
    num_reads=None,
    tenure=None,
    timeout=100,
    seed=None,
    num_restarts=1000000,
    energy_threshold=None,
    coefficient_z_first=None,
    coefficient_z_restart=None,
    lower_bound_z=None,
    initial_states=None,
    initial_states_generator='random'
)

Parameter Details

For a complete overview of available parameters and their usage, see the TabuSearch API Reference.


Usage

from luna_quantum import LunaSolve

LunaSolve.authenticate("<YOUR_LUNA_API_KEY>")

# Define your model and algorithm
model = ...
algorithm = ...

solve_job = algorithm.run(model, name="my-solve-job")

API Reference

Bases: TabuSearchParams, LunaAlgorithm[DWave]

Extended parameters for the Tabu Search optimization algorithm.

Tabu Search is a metaheuristic that enhances local search by maintaining a "tabu list" of recently visited solutions to avoid cycling. It systematically explores the solution space by allowing non-improving moves when no improving moves exist, while preventing revisiting recent solutions.

This class extends the basic TabuSearch with additional parameters for fine-tuning the search process, including restart strategies and early termination conditions.

Attributes:

Name Type Description
initial_states Any | None

Starting states for the search. Allows the algorithm to begin from promising regions rather than random points. If fewer states than num_reads are provided, additional states are generated according to initial_states_generator. Default is None (random starting states).

seed int | None

Random seed for reproducible results. With identical parameters and seed, results will be identical (unless timeout limits are reached, as finite clock resolution can affect execution). Default is None (random seed).

num_restarts int

Maximum number of tabu search restarts per read. Restarts help escape deep local minima by starting fresh from new points after the initial search stalls. Setting to zero results in a simple tabu search without restarts. Default is 1,000,000, allowing many restarts if needed.

energy_threshold float | None

Target energy value that triggers termination if found. Allows early stopping when a sufficiently good solution is discovered. Default is None (run until other stopping criteria are met).

coefficient_z_first int | None

Controls the number of variable updates in the first simple tabu search (STS). The actual limit is max(variables*coefficient_z_first, lower_bound_z). Defaults to 10,000 for small problems (≤500 variables) and 25,000 for larger ones. Higher values allow more thorough exploration of the initial solution neighborhood.

coefficient_z_restart int | None

Controls the number of variable updates in restarted tabu searches. Similar to coefficient_z_first but for restart phases. Default is coefficient_z_first/4, allowing faster exploration during restarts. This typically results in broader but less deep searches after restarts.

lower_bound_z int | None

Minimum number of variable updates for all tabu searches. Ensures a thorough search even for small problems. Default is 500,000. Setting too low may result in premature termination before finding good solutions.

num_reads int | None

Number of independent runs of the tabu algorithm, each producing one solution. Multiple reads increase the chance of finding the global optimum by starting from different initial states. If None, matches the number of initial states provided (or performs just one read if no initial states are given).

tenure int | None

Length of the tabu list - the number of recently visited solutions that are forbidden. Larger values help escape deeper local minima but may slow exploration. Default is 1/4 of the number of variables up to a maximum of 20. A good tenure balances diversification (exploring new regions) with intensification (focusing on promising areas).

timeout float

Maximum running time in milliseconds per read before the algorithm stops, regardless of convergence. Default is 100, which is suitable for small to medium-sized problems. For larger problems, consider increasing this value to allow sufficient exploration time.

initial_states_generator Literal[none, tile, random]

Controls how to handle situations where fewer initial states are provided than num_reads:

  • "none": Raises an error if insufficient initial states
  • "tile": Reuses provided states by cycling through them
  • "random": Generates additional random states as needed

Default is "random", which maximizes search space coverage when the number of provided initial states is insufficient.

backend class-attribute instance-attribute

backend: BACKEND_TYPE | None = Field(default=None, exclude=True, repr=False)

coefficient_z_first class-attribute instance-attribute

coefficient_z_first: int | None = None

coefficient_z_restart class-attribute instance-attribute

coefficient_z_restart: int | None = None

energy_threshold class-attribute instance-attribute

energy_threshold: float | None = None

initial_states class-attribute instance-attribute

initial_states: Any | None = None

initial_states_generator class-attribute instance-attribute

initial_states_generator: Literal['none', 'tile', 'random'] = 'random'

lower_bound_z class-attribute instance-attribute

lower_bound_z: int | None = None

model_config class-attribute instance-attribute

model_config = ConfigDict(
    arbitrary_types_allowed=True, extra="allow", validate_assignment=True
)

num_reads class-attribute instance-attribute

num_reads: int | None = None

num_restarts class-attribute instance-attribute

num_restarts: int = 1000000

seed class-attribute instance-attribute

seed: int | None = None

tenure class-attribute instance-attribute

tenure: int | None = Field(default=None, le=20)

timeout class-attribute instance-attribute

timeout: float = 100

get_compatible_backends classmethod

get_compatible_backends() -> tuple[type[DWave], ...]

Check at runtime if the used backend is compatible with the solver.

Returns:

Type Description
tuple[type[IBackend], ...]

True if the backend is compatible with the solver, False otherwise.

get_default_backend classmethod

get_default_backend() -> DWave

Return the default backend implementation.

This property must be implemented by subclasses to provide the default backend instance to use when no specific backend is specified.

Returns:

Type Description
IBackend

An instance of a class implementing the IBackend interface that serves as the default backend.

run

run(
    model: Model | str,
    name: str | None = None,
    backend: BACKEND_TYPE | None = None,
    client: LunaSolve | str | None = None,
    *args: Any,
    **kwargs: Any,
) -> SolveJob

Run the configured solver.

Parameters:

Name Type Description Default
model Model or str

The model to be optimized or solved. It could be an Model instance or a string identifier representing the model id.

required
name str | None

If provided, the name of the job. Defaults to None.

None
backend BACKEND_TYPE | None

Backend to use for the solver. If not provided, the default backend is used.

None
client LunaSolve or str

The client interface used to interact with the backend services. If not provided, a default client will be used.

None
*args Any

Additional arguments that will be passed to the solver or client.

()
**kwargs Any

Additional keyword parameters for configuration or customization.

{}

Returns:

Type Description
SolveJob

The job object containing the information about the solve process.