# QUBOTools.jl

## Introduction

The `QUBOTools.jl`

package implements codecs for QUBO (*Quadratic Unconstrained Binary Optimization*) instances.
Its purpose is to provide fast and reliable conversion between common formats used to represent such problems.
This allows for rapid leverage of many emergent computing architectures whose job is to solve this kind of optimization problem.

The term QUBO is widely used when referring to *boolean* problems of the form

with symmetric *Ising Models*, given by

where

## Getting Started

### Installation

```
julia> import Pkg
julia> Pkg.add("QUBOTools")
```

### Basic Usage

```
julia> using QUBOTools
julia> model = QUBOTools.read_model("problem.json")
julia> write("problem.qubo", model)
```

## Supported Formats

The `r`

and `w`

marks indicate that reading and writing modes are available for the corresponding file format, respectively.

###
BQPJSON `rw`

The BQPJSON format was designed at LANL-ANSI to represent Binary Quadratic Programs in a platform-independet fashion.
This is accomplished by using `.json`

files validated using a well-defined JSON Schema.

###
QUBO `rw`

The QUBO specification appears as the input format in many of D-Wave's applications. A brief explanation about it can be found in qbsolv's repository README.

###
Qubist `rw`

This is the simplest of all current supported formats.

###
MiniZinc `rw`

MiniZinc is a constraint modelling language that can be used as input for many solvers.

###
HFS `w`

HFS is a very low-level mapping of weights to D-Wave's chimera graph.

### Conversion Flowchart

**Bold arrows** indicate that a bijective (modulo rounding erros) conversion is available.
**Regular arrows** indicate that some non-critical information might get lost in the process, such as problem metadata.
**Dashed arrows** tell that even though a format conversion exists, important information such as scale and offset factors will be neglected.

```
flowchart TD;
MODEL["QUBOTools Model"];
BQPJSON["BQPJSON<br><code>Bool</code><br><code>Spin</code>"];
HFS(["HFS<br><code>Bool</code>"]);
MINIZINC(["MiniZinc<br><code>Bool</code><br><code>Spin</code>"]);
QUBO["QUBO<br><code>Bool</code>"];
QUBIST["Qubist<br><code>Spin</code>"];
QUBIST -.-> MODEL;
MODEL --> HFS;
MODEL --> QUBIST;
MODEL <==> MINIZINC;
MODEL <==> BQPJSON;
QUBO <==> MODEL;
```

## Backend

The `AbstractModel{D}`

abstract type is defined, where `D <: Domain`

.
Available variable domains are `BoolDomain`

and `SpinDomain`

, respectively,

**QUBOTools.jl** also exports the `StandardQUBOModel{S, U, T, D} <: AbstractModel{D}`

type, designed to work as a powerful standard backend for all other models.
Here, `S <: Any`

plays the role of variable indexing type and usually defaults to `Int`

.
It is followed by `U <: Integer`

, used to store sampled states of type `Vector{U}`

.

When `D <: SpinDomain`

, it is necessary that `U <: Signed`

.
`T <: Real`

is the type used to represent all coefficients.
It is also the choice for the energy values corresponding to each solution.
It's commonly set as `Float64`

.

This package's mathematical formulation was inspired by **BQPJSON**'s, and is given by

where

We defined our problems to follow a minimization sense by default.
The scaling factor

### JuMP Integration

One of the main ideas was to make JuMP / MathOptInterface integration easy and, in fact, the implemented backend does a lot of the the data crunching.
When `S`

is set to `MOI.VariableIndex`

and `T`

matches `Optimzer{T}`

, we can say that most of the hard work is done.