Quadratic Unconstrained Binary Optimization

Problem Definition

Quadratic Unconstrained Binary Optimization (QUBO) is a boolean optimization problem. The objective is to maximize or minimize the following quadratic form by varying $x$:

\[y = x^T Q x\]

where $x$ is a $n$-dimensional boolean vector and $Q$ is a real square matrix. Without loss of generality, we focus on the minimization in this package. This problem is naturally similar with the spin glass problem on a hypergraph except that the flavors are $(0, 1)$ rather than $(-1,1)$. We can notice that $Q$ is the adjacency matrix, where the diagonal terms correspond to the external magnetic field.

Interfaces

To define a QUBO problem, there are two ways:

We can directly specify the $Q$ matrix;
Or we can specify a simple graph and the weights associated with edges.

julia> using ProblemReductions, Graphs
       # Matrix method
julia> Q = [1. 0 0; 0 1 0; 0 0 1]3×3 Matrix{Float64}:
 1.0  0.0  0.0
 0.0  1.0  0.0
 0.0  0.0  1.0
julia> QUBO01 = QUBO(Q)
       # Graph methodQUBO{Float64}([1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])
julia> graph = SimpleGraph(3){3, 0} undirected simple Int64 graph
julia> QUBO02 = QUBO(graph, Float64[], [1., 1., 1.])QUBO{Float64}([1.0 0.0 0.0; 0.0 1.0 0.0; 0.0 0.0 1.0])

Besides, the required functions, variables, flavors, and evaluate, and optional functions, findbest, are implemented for the [QUBO] problem.

julia> variables(QUBO01)  # degrees of freedom3-element Vector{Int64}:
 1
 2
 3
julia> variables(QUBO02)3-element Vector{Int64}:
 1
 2
 3
julia> flavors(QUBO01)  # flavors of the vertices2-element Vector{Int64}:
 0
 1
julia> evaluate(QUBO01, [0, 1, 0])1.0
julia> evaluate(QUBO02, [0, 1, 0])1.0
julia> findbest(QUBO01, BruteForce())  # solve the problem with brute force1-element Vector{Vector{Int64}}:
 [0, 0, 0]
julia> findbest(QUBO02, BruteForce())1-element Vector{Vector{Int64}}:
 [0, 0, 0]