Anneal.jl

🔵 QUBO Annealing & Sampling MOI Interfaces
Author psrenergy
Popularity
15 Stars
Updated Last
1 Year Ago
Started In
March 2022

Anneal.jl 🔴🟢🟣🔵

Warning This package was archived. Consider using QUBODrivers instead.

Introduction

This package aims to provide a common MOI-compliant API for QUBO Sampling & Annealing machines. It also contains a few testing tools, including utility samplers for performance comparison and sanity checks, and some basic analysis features.

QUBO

Problems assigned to solvers defined within Anneal.jl's interface are given by

$$\begin{array}{rl} \text{QUBO}:~ \displaystyle \min_{\vec{x}} & \displaystyle \alpha \left[{ \vec{x}' Q \vec{x} + \beta }\right] \\ \text{s.t.} & \displaystyle \vec{x} \in S \cong \mathbb{B}^{n} \end{array}$$

where $Q \in \mathbb{R}^{n \times n}$ is a symmetric matrix. Maximization is automatically converted to minimization in a transparent fashion during runtime.

Quick Start

Installation

julia> ]add Anneal

or

julia> import Pkg; Pkg.add("Anneal")

Example

using JuMP
using Anneal

model = Model(ExactSampler.Optimizer)

Q = [
    -1.0  2.0  2.0
     2.0 -1.0  2.0
     2.0  2.0 -1.0
]

@variable(model, x[1:3], Bin)
@objective(model, Min, x' * Q * x)

optimize!(model)

for i = 1:result_count(model)
    xᵢ = value.(x; result=i)
    yᵢ = objective_value(model; result=i)
    println("f($xᵢ) = $yᵢ")
end

Utility Samplers

Module Name Descripition Package
ExactSampler Sequentially samples all possible states by exaustive enumeration. Finds the global optimum but can't be used for models with much more than 20 variables. Anneal.jl
IdentitySampler Samples the exact same state defined as warm start. Anneal.jl
RandomSampler Randomly samples states by regular or biased coin tossing. It is commonly used to compare new solving methods to a random guessing baseline. Anneal.jl

Interfaces

Module Name Descripition Package
DWave Wrapper for D-Wave's Quantum Annealing API. DWave.jl
DWaveNeal Wrapper for D-Wave's open-source Simulated Annealing sampler. DWaveNeal.jl
QuantumAnnealingInterface Wrapper for LANL's Quantum Annealing simulator QuantumAnnealingInterface.jl

Heuristics

Module Name Descripition Package
GreedyDescent Stochastic greedy descent algorithm. IsingSolvers.jl
ILP Integer Linear Programming apporach using a regular MIP solver chosen by the user. IsingSolvers.jl
MCMCRandom Monte Carlo Markov Chain Random sampler IsingSolvers.jl

If you implemented your own sampler interface using Anneal.jl, consider opening an issue or submiting a pull request to add it to the list.

Interface (aka. integrating your own sampler)

There are two options to consider when using Anneal.jl, namely AbstractSampler and AutomaticSampler. As the diagram below indicates, the automatic type is a subtype of the general, abstract one.

flowchart TB;
    OPTIMIZER(["<code>MOI.AbstractOptimizer</code>"]);
    ABSTRACT(["<code>AbstractSampler</code>"]);
    AUTOMATIC(["<code>AutomaticSampler</code>"]);
    
    OPTIMIZER --> ABSTRACT --> AUTOMATIC;

    subgraph UTILITY [Utility]
        direction LR
        EXACT["<code>ExactSampler</code>"];
        IDENTITY["<code>IdentiySampler</code>"];
        RANDOM["<code>RandomSampler</code>"];
    end
    
    subgraph HEURISTICS [Heuristics]
        direction LR
        GREEDY["<code>IsingSolvers.GreedyDescent</code>"];
        ILP["<code>IsingSolvers.ILP</code>"];
        MCMC["<code>IsingSolvers.MCMCRandom</code>"];
    end
    
    subgraph INTERFACES [Interfaces]
        direction LR
        DWAVE["<code>DWave</code>"];
        DWAVENEAL["<code>DWaveNeal</code>"];
        QUANTUMANNEALING["<code>QuantumAnnealingInterface</code>"];
    end
       
    AUTOMATIC --> UTILITY;
    AUTOMATIC --> INTERFACES;
    AUTOMATIC --> HEURISTICS;
Loading

Automatic Interface

PSR Quantum Optimization Toolchain

ToQUBO.jl Anneal.jl QUBOTools.jl

Used By Packages

No packages found.