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;

Automatic Interface

PSR Quantum Optimization Toolchain