Simulated Annealing

Simulated Annealing

  • Short Name: SA
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
Simulated Annealing is a probabilistic technique for approximating the global optimum of a given function. It performs well on problems where approximate global optima are more desirable than exact local optima. For more details, check the D-Wave website.

Usage via LunaSolve

# Example of using SA using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="SA",
    provider="dwave",
    solver_parameters={
        "num_reads": None,
        "num_sweeps": 1000,
        "beta_range": None,
        "beta_schedule_type": "geometric",
        "initial_states_generator": "random",
        "num_sweeps_per_beta": 1,
        "seed": None,
        "beta_schedule": None,
        "initial_states": None,
        "randomize_order": False,
        "proposal_acceptance_criteria": "Metropolis",
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding SA using the Luna backend as an algorithm to LunaBench
algorithms = {
    "SA": {
        "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.
Parameters
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the simulated annealing 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
    num_sweeps
    Type
    int | None
    Description

    Number of sweeps used in annealing.
    Default: 1000

  • Name
    beta_range
    Type
    list[float] | tuple[float, float] | None
    Description

    A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. The schedule is applied linearly in beta. Default range is set based on the total bias associated with each node.
    Default: None

  • Name
    beta_schedule_type
    Type
    Literal["linear", "geometric"]
    Description

    Beta schedule type, or how the beta values are interpolated between the given 'beta_range'.
    Default: "geometric"

  • 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 an error. '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
    num_sweeps_per_beta
    Type
    int
    Description

    Number of sweeps to perform at each beta. One sweep consists of a sequential Metropolis update of all spins.
    Default: 1

  • Name
    seed
    Type
    int | None
    Description

    Seed to use for the PRNG. Specifying a particular seed with a constant set of parameters produces identical results. If not provided, a random seed is chosen.
    Default: None

  • Name
    beta_schedule
    Type
    Sequence[float] | None
    Description

    Sequence of beta values swept. Format must be compatible with numpy.array(beta_schedule, dtype=float). Values should be non-negative.
    Default: None

  • 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 additional values are generated as specified by initial_states_generator. See ~dimod.as_samples for a description of 'samples-like.
    Default: None

  • Name
    randomize_order
    Type
    bool
    Description

    When True, each spin update selects a variable uniformly at random. This method is ergodic, obeys detailed balance and preserves symmetries of the model. When False, updates proceed sequentially through the labeled variables on each sweep so that all variables are updated once per sweep. This method:

    • can be non-ergodic in special cases when used with proposal_acceptance_critera=='Metropolis'.
    • can introduce a dynamical bias as a function of variable order.
    • has faster per spin update than the True method.
      Default: False
  • Name
    proposal_acceptance_criteria
    Type
    Literal["Gibbs", "Metropolis"]
    Description

    When 'Gibbs', each spin flip proposal is accepted according to the Gibbs criteria. When 'Metropolis', each spin flip proposal is accepted according to the Metropolis-Hastings criteria.
    Default: "Metropolis"

Population Annealing

  • Short Name: PA
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
Population Annealing uses a sequential Monte Carlo method to minimize the energy of a population. The population consists of walkers that can explore their neighborhood during the cooling process. Afterwards, walkers are removed and duplicated using bias to lower energy. Eventually, a population collapse occurs where all walkers are in the lowest energy state.

Usage via LunaSolve

# Example of using PA using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="PA",
    provider="dwave",
    solver_parameters={
        "fixed_temperature_sampler": {
            "num_sweeps": 10000,
            "num_reads": None,
        },
        "max_iter": 20,
        "max_time": 2,
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding PA using the Luna backend as an algorithm to LunaBench
algorithms = {
    "PA": {
        "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.
Parameters
  • Name
    fixed_temperature_sampler
    Type
    FixedTemperatureSampler
    Description

    Parameters for the fixed temperature sampler.
    Default: FixedTemperatureSampler(num_sweeps=10000, num_reads=None)

  • Name
    max_iter
    Type
    int
    Description

    Maximum number of iterations. Default is 20.
    Default: 20

  • Name
    max_time
    Type
    int
    Description

    Maximum time in seconds that the algorithm is allowed to run. Default is 2.
    Default: 2

FixedTemperatureSampler
  • Name
    num_sweeps
    Type
    int
    Description

    Number of sweeps for the sampler.
    Default: 10000

  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads for the sampler.
    Default: None

Parallel Tempering

  • Short Name: PT
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
Parallel Tempering uses multiple optimization procedures per temperature. During the cooling process, an exchange of replicas can take place between the parallel procedures, thus enabling higher energy mountains to be overcome.

Usage via LunaSolve

# Example of using PT using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="PT",
    provider="dwave",
    solver_parameters={
        "n_replicas": 2,
        "random_swaps_factor": 1,
        "fixed_temperature_sampler": {
            "num_sweeps": 10000,
            "num_reads": None,
        },
        "cpu_count_multiplier": 5,
        "loop": {
            "max_iter": 100,
            "max_time": 5,
            "convergence": 3,
            "target": None,
            "rtol": 1e-05,
            "atol": 1e-08,
        },
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding PT using the Luna backend as an algorithm to LunaBench
algorithms = {
    "PT": {
        "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.
Parameters
  • Name
    n_replicas
    Type
    int
    Description

    Number of replicas for the parallel tempering. Default is 2.
    Default: 2

  • Name
    random_swaps_factor
    Type
    int
    Description

    Factor for random swaps. Default is 1.
    Default: 1

  • Name
    fixed_temperature_sampler
    Type
    FixedTemperatureSampler
    Description

    Parameters for the fixed temperature sampler.
    Default: FixedTemperatureSampler(num_sweeps=10000, num_reads=None)

  • Name
    cpu_count_multiplier
    Type
    int
    Description

    Multiplier for the CPU count. Default is 5.
    Default: 5

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

FixedTemperatureSampler
  • Name
    num_sweeps
    Type
    int
    Description

    Number of sweeps for the sampler.
    Default: 10000

  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads for the sampler.
    Default: None

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

Repeated Reverse Simulated Annealing

This solver is only available for commercial and academic licenses.
  • Short Name: RRSA
  • Algorithm Type: Classical
  • Category: Classical
  • Native Input Format: BQM
Repeated Reverse Simulated Annealing finds the solution to a problem using an annealing process. Initially, random states are chosen in the solution landscape. Afterwards, as the temperature decreases, states are chosen that are more energetically favorable. At the end of the complete annealing process, the resulting states make up the solution.

Usage via LunaSolve

# Example of using RRSA using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="RRSA",
    provider="dwave",
    solver_parameters={
        "simulated_annealing": {
            "num_reads": None,
            "num_sweeps": None,
            "beta_range": None,
            "beta_schedule_type": "geometric",
            "initial_states_generator": "random",
            "num_sweeps_per_beta": 1,
            "beta_schedule": None,
            "randomize_order": False,
            "proposal_acceptance_criteria": "Metropolis",
        },
        "num_reads_per_iter": None,
        "initial_states": None,
        "timeout": 5.0,
        "max_iter": 10,
        "target": None,
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding RRSA using the Luna backend as an algorithm to LunaBench
algorithms = {
    "RRSA": {
        "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.
Parameters
  • Name
    simulated_annealing
    Type
    RRSimulatedAnnealing
    Description

    Simulated Annealing params in each iteration.
    Default: RRSimulatedAnnealing(num_reads=None, num_sweeps=None, beta_range=None, beta_schedule_type='geometric', initial_states_generator='random', num_sweeps_per_beta=1, beta_schedule=None, randomize_order=False, proposal_acceptance_criteria='Metropolis')

  • Name
    num_reads_per_iter
    Type
    list[int] | None
    Description

    Number of reads in each iteration. Use num_reads_per_iter[i] in iteration i, and num_reads_per_iter[-1] once the list is exhausted. If the parameter is None, fall back to simulated_annealing.num_reads. Min length: 1.
    Default: None

  • 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 additional values are generated as specified by initial_states_generator. See ~dimod.as_samples for a description of 'samples-like.
    Default: None

  • Name
    timeout
    Type
    float
    Description

    Timeout for the solver.
    Default: 5.0

  • Name
    max_iter
    Type
    int
    Description

    Maximum number of iterations for the solver.
    Default: 10

  • Name
    target
    Type
    Any | None
    Description

    The target energy for the solver.
    Default: None

RRSimulatedAnnealing
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the simulated annealing 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
    num_sweeps
    Type
    int | None
    Description

    Number of sweeps used in annealing.
    Default: None

  • Name
    beta_range
    Type
    list[float] | tuple[float, float] | None
    Description

    A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. The schedule is applied linearly in beta. Default range is set based on the total bias associated with each node.
    Default: None

  • Name
    beta_schedule_type
    Type
    Literal["linear", "geometric"]
    Description

    Beta schedule type, or how the beta values are interpolated between the given 'beta_range'.
    Default: "geometric"

  • 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 an error. '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
    num_sweeps_per_beta
    Type
    int
    Description

    Number of sweeps to perform at each beta. One sweep consists of a sequential Metropolis update of all spins.
    Default: 1

  • Name
    beta_schedule
    Type
    Sequence[float] | None
    Description

    Sequence of beta values swept. Format must be compatible with numpy.array(beta_schedule, dtype=float). Values should be non-negative.
    Default: None

  • Name
    randomize_order
    Type
    bool
    Description

    When True, each spin update selects a variable uniformly at random. This method is ergodic, obeys detailed balance and preserves symmetries of the model. When False, updates proceed sequentially through the labeled variables on each sweep so that all variables are updated once per sweep. This method:

    • can be non-ergodic in special cases when used with proposal_acceptance_critera=='Metropolis'.
    • can introduce a dynamical bias as a function of variable order.
    • has faster per spin update than the True method.
      Default: False
  • Name
    proposal_acceptance_criteria
    Type
    Literal["Gibbs", "Metropolis"]
    Description

    When 'Gibbs', each spin flip proposal is accepted according to the Gibbs criteria. When 'Metropolis', each spin flip proposal is accepted according to the Metropolis-Hastings criteria.
    Default: "Metropolis"

QBSolv Like Simulated Annealing

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

Usage via LunaSolve

# Example of using QLSA using the Luna backend in LunaSolve
solution = ls.solution.create(
    optimization_id=optimization.id,
    solver_name="QLSA",
    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,
            },
        },
        "simulated_annealing": {
            "num_reads": None,
            "num_sweeps": 1000,
            "beta_range": None,
            "beta_schedule_type": "geometric",
            "initial_states_generator": "random",
        },
    },
    qpu_tokens=None,
)

Usage via LunaBench

# Example of adding QLSA using the Luna backend as an algorithm to LunaBench
algorithms = {
    "QLSA": {
        "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.
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
    simulated_annealing
    Type
    SimulatedAnnealing
    Description

    Parameters for the Simulated Annealing.
    Default: SimulatedAnnealing(num_reads=None, num_sweeps=1000, beta_range=None, beta_schedule_type='geometric', 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)

SimulatedAnnealing
  • Name
    num_reads
    Type
    int | None
    Description

    Number of reads. Each read is generated by one run of the simulated annealing 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
    num_sweeps
    Type
    int | None
    Description

    Number of sweeps used in annealing.
    Default: 1000

  • Name
    beta_range
    Type
    list[float] | tuple[float, float] | None
    Description

    A 2-tuple defining the beginning and end of the beta schedule, where beta is the inverse temperature. The schedule is applied linearly in beta. Default range is set based on the total bias associated with each node.
    Default: None

  • Name
    beta_schedule_type
    Type
    Literal["linear", "geometric"]
    Description

    Beta schedule type, or how the beta values are interpolated between the given 'beta_range'.
    Default: "geometric"

  • 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 an error. '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?