Skip to content

JuliaQUBO/ToQUBO.jl

Folders and files

NameName
Last commit message
Last commit date

Latest commit

Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 
Β 

Repository files navigation

ToQUBO.jl πŸŸ₯🟩πŸŸͺ🟦

Introduction

ToQUBO.jl is a Julia package to reformulate general optimization problems into QUBO (Quadratic Unconstrained Binary Optimization) instances. This tool aims to convert a broad range of JuMP problems for straightforward application in many physics and physics-inspired solution methods whose normal optimization form is equivalent to the QUBO. These methods include quantum annealing, quantum gate-circuit optimization algorithms (Quantum Optimization Alternating Ansatz, Variational Quantum Eigensolver), other hardware-accelerated platforms, such as Coherent Ising Machines and Simulated Bifurcation Machines, and more traditional methods such as simulated annealing. During execution, ToQUBO.jl encodes both discrete and continuous variables, maps constraints, and computes their penalties, performing a few model optimization steps along the process. A simple interface to connect various annealers and samplers as QUBO solvers is defined in QUBODrivers.jl.

ToQUBO.jl was written as a MathOptInterface (MOI) layer that automatically maps between input and output models, thus providing a smooth JuMP modeling experience.

Getting Started

Installation

ToQUBO is available via Julia's Pkg:

julia> using Pkg

julia> Pkg.add("ToQUBO")

Simple Example

using JuMP
using ToQUBO
using QUBODrivers

model = Model(() -> ToQUBO.Optimizer(ExactSampler.Optimizer))

@variable(model, x[1:3], Bin)
@constraint(model, 0.3*x[1] + 0.5*x[2] + 1.0*x[3] <= 1.6)
@objective(model, Max, 1.0*x[1] + 2.0*x[2] + 3.0*x[3])

optimize!(model)

for i = 1:result_count(model)
    xi = value.(x, result = i)
    yi = objective_value(model, result = i)

    println("f($xi) = $yi")
end

List of Interpretable Constraints

Below, we present a list containing all⁴ MOI constraint types and their current reformulation support by ToQUBO.

Linear constraints

Mathematical Constraint MOI Function MOI Set Status
$\vec{a}' \vec{x} \le \beta$ ScalarAffineFunction LessThan βœ”οΈ
$\vec{a}' \vec{x} \ge \alpha$ ScalarAffineFunction GreaterThan ♻️
$\vec{a}' \vec{x} = \beta$ ScalarAffineFunction EqualTo βœ”οΈ
$\alpha \le \vec{a}' \vec{x} \le \beta$ ScalarAffineFunction Interval ♻️
$x_i \le \beta$ VariableIndex LessThan βœ”οΈ
$x_i \ge \alpha$ VariableIndex GreaterThan βœ”οΈ
$x_i = \beta$ VariableIndex EqualTo βœ”οΈ
$\alpha \le x_i \le \beta$ VariableIndex Interval βœ”οΈ
$A \vec{x} + b \in \mathbb{R}_{+}^{n}$ VectorAffineFunction Nonnegatives ♻️
$A \vec{x} + b \in \mathbb{R}_{-}^{n}$ VectorAffineFunction Nonpositives ♻️
$A \vec{x} + b = 0$ VectorAffineFunction Zeros ♻️

Conic constraints

Mathematical Constraint MOI Function MOI Set Status
$\left\lVert{}{A \vec{x} + b}\right\rVert{}_{2} \le \vec{c}' \vec{x} + d$ VectorAffineFunction SecondOrderCone πŸ“–
$y \ge \left\lVert{}{\vec{x}}\right\rVert{}_{2}$ VectorOfVariables SecondOrderCone πŸ“–
$2 y z \ge \left\lVert{}{\vec{x}}\right\rVert{}_{2}^{2}; y, z \ge 0$ VectorOfVariables RotatedSecondOrderCone πŸ“–
$\left( \vec{a}'_1 \vec{x} + b_1,\vec{a}'_2 \vec{x} + b_2,\vec{a}'_3 \vec{x} + b_3 \right) \in E$ VectorAffineFunction ExponentialCone ❌
$A(\vec{x}) \in S_{+}$ VectorAffineFunction PositiveSemidefiniteConeTriangle ❌
$B(\vec{x}) \in S_{+}$ VectorAffineFunction PositiveSemidefiniteConeSquare ❌
$\vec{x} \in S_{+}$ VectorOfVariables PositiveSemidefiniteConeTriangle ❌
$\vec{x} \in S_{+}$ VectorOfVariables PositiveSemidefiniteConeSquare ❌

Quadratic constraints

Mathematical Constraint MOI Function MOI Set Status
$\vec{x} Q \vec{x} + \vec{a}' \vec{x} + b \ge 0$ ScalarQuadraticFunction GreaterThan ♻️
$\vec{x} Q \vec{x} + \vec{a}' \vec{x} + b \le 0$ ScalarQuadraticFunction LessThan βœ”οΈ
$\vec{x} Q \vec{x} + \vec{a}' \vec{x} + b = 0$ ScalarQuadraticFunction EqualTo βœ”οΈ
Bilinear matrix inequality VectorQuadraticFunction PositiveSemidefiniteCone ❌

Discrete and logical constraints

Mathematical Constraint MOI Function MOI Set Status
$x_i \in \mathbb{Z}$ VariableIndex Integer βœ”οΈ
$x_i \in \left\lbrace{0, 1}\right\rbrace$ VariableIndex ZeroOne βœ”οΈ
$x_i \in \left\lbrace{0}\right\rbrace \cup \left[{l, u}\right]$ VariableIndex Semicontinuous βŒ›
$x_i \in \left\lbrace{0}\right\rbrace \cup \left[{l, l + 1, \dots, u - 1, u}\right]$ VariableIndex Semiinteger βŒ›
ΒΉ VectorOfVariables SOS1 βœ”οΈ
Β² VectorOfVariables SOS2 πŸ“–
$y = 1 \implies \vec{a}' \vec{x} \in S$ VectorAffineFunction Indicator πŸ“–

ΒΉ At most one component of x can be nonzero

Β² At most two components of x can be nonzero, and if so they must be adjacent components

Symbol Meaning
βœ”οΈ Available
♻️ Available through BridgesΒ³
❌ Unavailable
βŒ› Under Development (Available soon)
πŸ“– Under Research

Β³ MOI Bridges provide equivalent constraint mapping.

⁴ If you think this list is incomplete, consider creating an Issue or opening a Pull Request.

Citing ToQUBO.jl

If you use ToQUBO.jl in your work, we kindly ask you to include the following citation:

@software{toqubo:2023,
  author       = {Pedro Maciel Xavier and Pedro Ripper and Tiago Andrade and Joaquim Dias Garcia and David E. Bernal Neira},
  title        = {{ToQUBO.jl}},
  month        = {feb},
  year         = {2023},
  publisher    = {Zenodo},
  version      = {v0.1.5},
  doi          = {10.5281/zenodo.7644291},
  url          = {https://doi.org/10.5281/zenodo.7644291}
}