QUBO Solvers

Solvers, Annealers & Samplers

ToQUBO.jl's main goal is to make use of parameterized stochastic optimization solvers, particularly those relying on non-conventional hardware such as Quantum Annealing and other Ising Machines. A few MOI-compliant interfaces for annealers and samplers are bundled within ToQUBO.jl via the QUBODrivers.jl companion package. Some of them are presented below.

Simulated Annealing

Provided by D-Wave's open-source code libraries, this Simulated Annealing engine implements some of the features and configurations you would find using the Quantum API. Its adoption is recommended for basic usage, tests, and research due to its robustness, simplicity and ease of use. The DWave.jl's DWave.Neal module uses QUBODrivers.jl to deliver an interface to this sampler.

Quantum Annealing

Interfacing with D-Wave's quantum annealer is one of the milestones we expect to achieve with this package. Like other proprietary optimization resources such as Gurobi, FICO® Xpress and IBM® CPLEX®, this requires licensing and extra steps are needed to get an access token. In a first moment, for those willing to get started, the DWave.Neal optimizer might be enough to learn the ropes.

Random Sampling

This sampler is implemented for test purposes and simply assigns 0 or 1 to each variable according to a given probability bias $0 \le p \le 1$, which defaults to $p = 0.5$. After running the using QUBODrivers command, RandomSampler.Optimizer will be available.

Exact Solver (Exhaustive Enumeration)

Also made to be used in tests, the ExactSolver.Optimizer interface runs through all possible state configurations, which implies in an exponential time complexity on the number of variables. Thus, only problems with at most $\approxeq 20$ variables should be provided since visiting $2^{20} \approxeq 10^{6}$ states can already take up to a few seconds.

Mixed-Integer Quadratic Programming

The most accessible alternative to the forementioned methods are Mixed-Integer Quadratic Programming (MIQP) solvers such as Gurobi, CPLEX, SCIP and BARON. These are not intended to be of regular use alongside ToQUBO.jl since providing a QUBO reformulation will usually make things harder for non-specialized solvers. Yet, there are still a few cases where they may be suitable, such as tests, benchmarks, or any other situation where global optimality is a must.