D-Wave Tabu Sampler

A dimod sampler that uses the MST2 multistart tabu search algorithm.

class TabuSampler[source]

A tabu-search sampler.

Examples

This example solves a two-variable Ising model.

>>> from tabu import TabuSampler
>>> samples = TabuSampler().sample_ising({'a': -0.5, 'b': 1.0}, {'ab': -1})
>>> list(samples.data()) 
[Sample(sample={'a': -1, 'b': -1}, energy=-1.5, num_occurrences=1)]
>>> samples.first.energy
-1.5
sample(bqm, initial_states=None, initial_states_generator='random', num_reads=None, seed=None, tenure=None, timeout=20, num_restarts=1000000, energy_threshold=None, **kwargs)[source]

Run a multistart tabu search on a given binary quadratic model.

Parameters

  • bqm (BinaryQuadraticModel) – The binary quadratic model (BQM) to be sampled.

  • initial_states (SampleSet, optional, default=None) – 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.

  • initial_states_generator (str, 'none'/'tile'/'random', optional, default='random') –

    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.

  • num_reads (int, optional, default=len(initial_states) or 1) – 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.

  • seed (int (32-bit unsigned integer), optional) – 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.

  • tenure (int, optional) – 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.

  • timeout (int, optional, default=20) – Total running time per read in milliseconds.

  • num_restarts (int, optional, default=1,000,000) – Number of tabu search restarts per read.

  • energy_threshold (float, optional) – Terminate when an energy lower than energy_threshold is found.

Returns

A dimod SampleSet object.

Return type

SampleSet

Examples

This example samples a simple two-variable Ising model.

>>> import dimod
>>> bqm = dimod.BQM.from_ising({}, {'ab': 1})

>>> import tabu
>>> sampler = tabu.TabuSampler()

>>> samples = sampler.sample(bqm)
>>> samples.record[0].energy
-1.0