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

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;

psrenergy / Anneal.jl

readme