Examples

Solving a simple MaxCut problem using the Ising formulation

The following is a simple example of using the AOC optimizer to solve a MaxCut problem. Searching for the maximum cut of a graph can be converted to an Ising optimization problem (by negating the adjacency matrix of the graph and searching for the spin assignment that minimized the Hamiltonian); it is also equivalent to a Quadratic Unconstrained Binary Optimization (QUBO) problem (transformation not shown here).

using Dates
using JSON
using AOCoptimizer
using AOCoptimizer: graph_cut_from_hamiltonian
using AOCoptimizer.Solver: solve_mixed_ising, find_best
using AOCoptimizer.Solver: get_solver_results_summary

# Necessary to explicitly initialize the AOCoptimizer package
AOCoptimizer.init()

graph = Float32.([
    0 1 0 0 1
    1 0 1 0 0
    0 1 0 1 0
    0 0 1 0 1
    1 0 0 1 0
])

# observe that we optimize the negative of the adjacency matrix of the graph
sol = solve_mixed_ising(Float32, -graph, Second(10))
best = find_best(sol)
cut = graph_cut_from_hamiltonian(graph, best.Objective)
println("Energy: ", best.Objective, "; Cut: ", cut)
println("Assignment: ", best.Vars)
println("Group 1: ", findall(best.Vars .== 1))
println("Group 2: ", findall(best.Vars .== -1))

[ Info: Registering engines
[ Info: Registering local CPU engine
[ Info: Registering default solvers
┌ Warning: Range of iterations adjusted from 500…20000 to 500…18708
└ @ AOCoptimizer.Solver ~/work/AOCoptimizer.jl/AOCoptimizer.jl/src/Solver/core.jl:264
Energy: -3.0; Cut: 4.0
Assignment: Float32[-1.0, 1.0, -1.0, 1.0, 1.0]
Group 1: [2, 4, 5]
Group 2: [1, 3]

More statistics reported as follows:

println(JSON.json(get_solver_results_summary(sol), 4));

{
    "obj_best_found": -3.0,
    "success_rate": 0.7790909090909091,
    "num_operations_to_solution": 7.202650004236125e6,
    "time_per_sample": 1.0845454545454545,
    "time_to_solution": 3.307617954344789,
    "iterations_total": 2361700,
    "counts_total": 1714,
    "num_samples_total": 2200
}

Detailed measurements are collected in the sol object:

println("Number of solver iterations in deep search: ", length(sol[:deep_search].results))
if length(sol[:deep_search].results) > 0
    println("Sample set of measurements:")
    lx = min(10, size(sol[:deep_search].results[1].Measurements, 1))
    ly = min(10, size(sol[:deep_search].results[1].Measurements, 2))
    show(stdout, MIME"text/plain"(), sol[:deep_search].results[1].Measurements[1:lx, 1:ly])
end

Number of solver iterations in deep search: 22
Sample set of measurements:
10×10 Matrix{Float32}:
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  -3.0  5.0  5.0
 -3.0  -3.0  -3.0  -3.0   5.0  -3.0  -3.0  -3.0  5.0  5.0

Solving a simple Mixed-Ising problem

The following is a simple example of solving a Mixed-Ising problem. The first three variables are either -1 or 1 (spin variables), while the last four variables are continuous (in the range $[-1, 1]$).

using Dates
using AOCoptimizer
using AOCoptimizer.Solver: solve_mixed_ising, find_best

AOCoptimizer.init()

number_of_binaries = 3

Q = Float32.([
       0.0 -234.0   2.0 -180.0  122.0  172.0  -48.0
    -234.0    0.0 -40.0  -72.0   88.0  124.0  -82.0
       2.0  -40.0   0.0   10.0  -56.0  -40.0  -82.0
    -180.0  -72.0  10.0 -214.0  130.0   68.0  -86.0
     122.0   88.0 -56.0  130.0 -150.0  -88.0   32.0
     172.0  124.0 -40.0   68.0  -88.0 -168.0  -88.0
     -48.0  -82.0 -82.0  -86.0   32.0  -88.0 -246.0
])

q = Float32.([
        1,
        135,
        -119,
        101,
        -139,
        -14,
        145
])

sol = solve_mixed_ising(Float32, Q, q, number_of_binaries, Second(10))
best = find_best(sol)

(Objective = -654.262f0, Vars = Float32[-1.0, 1.0, -1.0, 0.59758, 0.03313011, -0.25868678, 0.6724908], Info = (Annealing = 0.02954549f0, Gradient = 0.011554374f0, Momentum = 0.98761415f0), Label = "deep_search")

The values of the binaries are:

println("Binaries: ", best.Vars[1:number_of_binaries])

Binaries: Float32[-1.0, 1.0, -1.0]

The values of the continuous variables are:

println("Continuous: ", best.Vars[number_of_binaries+1:end])

Continuous: Float32[0.59758, 0.03313011, -0.25868678, 0.6724908]

Solving a simple `QUMO` problem

Let's solve now a simple optimization problem that combines both binary and continuous variables (QUMO). In the example below, we have 3 binary variables and 4 continuous variables. Using the default interface, it is expected that the first variables are binary; e.g., in the example below, the variable number_of_binaries signifies that the first 3 variables are binary, and this parameter is passed to the solve_qumo function. Moreover, it is expected that the first number_of_binaries diagonal elements of the matrix Q are zero.

using Dates
using AOCoptimizer
using AOCoptimizer.Solver: solve_qumo, find_best

AOCoptimizer.init()

number_of_binaries = 3

Q = [
    0.0  -936.0     8.0  -360.0   244.0   344.0   -96.0
 -936.0     0.0  -160.0  -144.0   176.0   248.0  -164.0
    8.0  -160.0     0.0    20.0  -112.0   -80.0  -164.0
 -360.0  -144.0    20.0  -214.0   130.0    68.0   -86.0
  244.0   176.0  -112.0   130.0  -150.0   -88.0    32.0
  344.0   248.0   -80.0    68.0   -88.0  -168.0   -88.0
  -96.0  -164.0  -164.0   -86.0    32.0   -88.0  -246.0
]

q = [
  930.0
 1366.0
  -86.0
  585.0
 -447.0
 -526.0
  569.0
]

sol = solve_qumo(Float32, Q, q, number_of_binaries, Second(10))
best = find_best(sol)

(Objective = -2111.4702f0, Vars = Float32[0.0, 1.0, 0.0, 1.0, -0.14007771, -1.0, 1.0], Info = (Annealing = 1.7632564f0, Gradient = 0.0047452394f0, Momentum = 0.9626141f0), Label = "phase_2")