dwave-hybrid vs. qbsolv: really which works best?
Dear D-Wave folk,
I am an enthusiastic user of your tools to solve optimisation problems in QUBO format. Admittedly I had so far only used only classical heuristics such as SA and decomposition techniques as in QBSolv (I am leaving the quantum accelleration for future work). This latter solver is definitely my favourite and last release (0.3.2) works great! Now in my last look at the Ocean documentation I saw that "It is strongly recommended that you use dwave-hybrid instead" of QBSolv. So, I tried it, but with my great disappointment all example workflows in the repository (CPU only) I tried were performing much worse than QBSolv and sometimes of the neal SA package.
Best hybrid (python) workflows I tried reads as follow:
model = dimod.BinaryQuadraticModel.from_numpy_matrix(Q)
# define the QBSolv-like workflow
iteration = hybrid.Race(hybrid.InterruptableTabuSampler(),
hybrid.EnergyImpactDecomposer(size=50, rolling=True, rolling_history=0.15)
#| hybrid.QPUSubproblemAutoEmbeddingSampler()
| hybrid.TabuSubproblemSampler(timeout=10)
| hybrid.SplatComposer()
) | hybrid.ArgMin() | hybrid.TrackMin(output=True)
main = hybrid.Loop(iteration, max_iter=1, convergence=3)
# run the workflow
init_state = hybrid.State.from_sample(hybrid.min_sample(model), model)
response = main.run(init_state).result()
which I think should be basically the same as QBSolv itself. So I wonder if there's anything wrong in the workflow? Can I really get better performance (I assume that's why you strongly recommend it) with dwave-hybrid than QBSolv? And how (please avoid telling me to use QPU because that's not an answer :-))?
Many thanks for your help and support,
Andrea
Comments
Hi Andrea,
Our apologies for the delayed response!
We would like to gather a little more information about the problems you are running in order to better understand what is happening.
It sounds like you have tried running qbsolv with CPU resources, such as Tabu, as well as dwave-hybrid with Tabu.
And it sounds like the results were favourable for qbsolv from your experience here.
Which code examples did you run with these?
Our understanding is that you have not run qbsolv or dwave-hybrid with the QPU as the solver for either.
Is this correct?
If we understand correctly, what you are seeing is that there is a difference between the results from the dwave-hybrid code you have provided and those returned by qbsolv using the same solver.
Is this correct?
Have you tried the dwave-hybrid qbsolv implementation?
It looks quite similar to your code example at first glance. It should produce similar results to qbsolv.
Are you able to confirm any results you have (or haven't) seen from this library?
Thank you again for your patience and understanding!
Dear David,
thank you for your reply. I'll answer to your questions and attempt to clarify the issue.
Yes, I am running purely with CPU resources. My goal is, at first, to identify best solver (for my application) with CPU only. Later look for QPU assisted ones.
I have used example dwave-hybrid solvers found in https://github.com/dwavesystems/dwave-hybrid/blob/master/examples/ which includes the qbsolv-like workflow I posted earlier (with QPUsubsampler replaced by local Tabusampler). The qbsolv implementation you suggested here dwave-hybrid qbsolv implementation uses the QPU so it is out of scope at the moment.
To make my claim clearer I made a small script comparing QBSolv with several hybrid solvers. I applied them to a QUBO problem of typically 3000 nodes coming from a constrained graph-coloring like problem with a sparse matrix. I include the code below (I would include the data used but apparently there is no way to attach a file to this post).
An actual output read as:
CPU time QBSolv: 28.116265535354614
Minimum energy QBSolv: -1010.8800000000019
CPU time Hybrid_SA_TS: 7.594892263412476
Minimum energy Hybrid_SA_TS: -924.4000002457469
CPU time Hybrid_Dialectic: 173.93276596069336
Minimum energy Hybrid_Dialectic: -1010.8800000000001
CPU time Hybrid_QBSolv_like: 29.604060888290405
Minimum energy Hybrid_QBSolv_like: -950.8800000000001
CPU time Hybrid_Par_Tempering: 191.85742354393005
Minimum energy Hybrid_Par_Tempering: -966.880000245379
By running the test several times one can make the following observations:
1) CPU time and solution quality (lower energy found) vary greatly from run to run and for all solvers. This expected but not desirable.
2) On average, "Hybrid_Dialectic" delivers best result but with 10 time CPU-time than QBSolv. However Hybrid_Dialectic with some data set crashes often but not in a reproducible manner. Very annoying.
3) Hybrid implementation of QBsolv-like solver gives on average slightly worse results than QBSolv stand-alone with similar CPU-time
4) All other hybrid solver are worse in both solution quality and CPU time with respect to QBSolv.
Conclusion: It does not seem easy to get solid advantage in using the dwave hybrid module and solver compared with QBSolv with CPU only. Very different story may be when using QPU as well.
# Test (D-Wave) CPU-only solvers
# Load QUBO from pci optimisation problem and run various solvers
import numpy as np
import scipy.io as sio
import matplotlib.pyplot as plt
import sys
import dimod
import itertools
import neal
import numpy.matlib
import time
# for new sampler
import hybrid
from dwave_qbsolv import QBSolv
from dwave.system.samplers import DWaveSampler
from dwave.system.composites import AutoEmbeddingComposite
# load QUBO divided in minimisation Q1 matrix, Q2 constraints matrix,
# C is linear matrix constraints with known term b. C*x=b
filename = '3085_Q1_Q2_C_b_A_ncolors_18.npz' # larger problem but
# gives sometimes errors Hybrid-Dialectic-Search
#filename = '3085_Q1_Q2_C_b_A_ncolors_21.npz' # larger problem
#filename = '255_Q1_Q2_C_b.ncolors_21.npz' # small problem
data = np.load(filename) # large problem
Q1 = data['Q1']
Q2 = data['Q2']
C = data['C']
b = data['b']
# Make complete QUBO problem
P = 2 # Penalty weight for constraints equations
Q = Q1+P*Q2
#breakpoint()
# ------------------- Solve problem with QBSolv --------------------------------
QBSolv_iter = 50
#sampler = neal.SimulatedAnnealingSampler()
time_start=time.time()
QBSolv_response = QBSolv().sample_qubo(Q,num_repeats=QBSolv_iter) # solving with default tabu search
#response = QBSolv().sample_qubo(Q, solver=sampler)
#response = QBSolv().sample_qubo(Q, solver=sampler, solver_limit=subqubo_size)
time_stop=time.time()
CPUtime_QBSolv = time_stop -time_start
print('CPU time QBSolv: {}'.format(CPUtime_QBSolv))
print('Minimum energy QBSolv: {}'.format(QBSolv_response.data_vectors['energy'][0]))
# Solve with hybrid module
# ------------- 'Hybrid-SA-TSearch' --------------------------------------------
model = dimod.BinaryQuadraticModel.from_numpy_matrix(Q)
# construct a workflow that races Simulated Annealing against SA/Tabu on a subproblem
iteration = hybrid.Race(hybrid.SimulatedAnnealingProblemSampler(),
hybrid.EnergyImpactDecomposer(size=50)
| hybrid.RacingBranches(
hybrid.SimulatedAnnealingSubproblemSampler(num_sweeps=1000),
hybrid.TabuSubproblemSampler(tenure=20,timeout=10))
| hybrid.ArgMin('subsamples.first.energy')
| hybrid.SplatComposer()
) | hybrid.ArgMin('samples.first.energy')
main = hybrid.Loop(iteration, max_iter=2, convergence=3)
# run the workflow
time_start=time.time()
init_state = hybrid.State.from_sample(hybrid.utils.min_sample(model), model)
Hybrid_SA_TS_response = main.run(init_state).result()
time_stop=time.time()
CPUtime_Hybrid_SA_TS = time_stop -time_start
print('CPU time Hybrid_SA_TS: {}'.format(CPUtime_Hybrid_SA_TS))
print('Minimum energy Hybrid_SA_TS: {}'.format(Hybrid_SA_TS_response.samples.first.energy))
# ------------- 'Hybrid-Dialectic-Search'---------------------------------------
model = dimod.BinaryQuadraticModel.from_numpy_matrix(Q)
# construct a Dialectic Search workflow
generate_antithesis = ( hybrid.IdentityDecomposer()
| hybrid.RandomSubproblemSampler()
| hybrid.SplatComposer()
| hybrid.TabuProblemSampler())
generate_synthesis = ( hybrid.GreedyPathMerge()
| hybrid.TabuProblemSampler())
tracker = hybrid.TrackMin()
local_update = hybrid.LoopWhileNoImprovement(
hybrid.Parallel(hybrid.Identity(), generate_antithesis)
| generate_synthesis | tracker, max_tries=10)
global_update = hybrid.Loop(generate_antithesis | local_update, max_iter=1)
# run the workflow
time_start=time.time()
init_state = hybrid.State.from_sample(hybrid.min_sample(model), model)
final_state = global_update.run(init_state).result()
Hybrid_Dialectic_response = tracker.best
time_stop=time.time()
CPUtime_Hybrid_Dialectic = time_stop -time_start
print('CPU time Hybrid_Dialectic: {}'.format(CPUtime_Hybrid_Dialectic))
print('Minimum energy Hybrid_Dialectic: {}'.format(Hybrid_Dialectic_response.samples.first.energy))
# ------------------------- 'Hybrid-QBSolv-like' ------------------------------
model = dimod.BinaryQuadraticModel.from_numpy_matrix(Q)
# define the QBSolv-like workflow
iteration = hybrid.Race(hybrid.InterruptableTabuSampler(),
hybrid.EnergyImpactDecomposer(size=50, rolling=True, rolling_history=0.15)
#| hybrid.QPUSubproblemAutoEmbeddingSampler()
| hybrid.TabuSubproblemSampler()#(timeout=10)
| hybrid.SplatComposer()
) | hybrid.ArgMin() | hybrid.TrackMin(output=True)
main = hybrid.Loop(iteration, max_iter=50, convergence=3)
# run the workflow
time_start=time.time()
init_state = hybrid.State.from_sample(hybrid.min_sample(model), model)
Hybrid_QBSolv_like_response = main.run(init_state).result()
time_stop=time.time()
CPUtime_Hybrid_QBSolv_like = time_stop -time_start
print('CPU time Hybrid_QBSolv_like: {}'.format(CPUtime_Hybrid_QBSolv_like))
print('Minimum energy Hybrid_QBSolv_like: {}'.format(Hybrid_QBSolv_like_response.samples.first.energy))
# ------------------- Parallel tempering workflow: ----------------------------
from hybrid.reference.pt import FixedTemperatureSampler
from hybrid.reference.pt import SwapReplicaPairRandom
n_sweeps = 10000
n_replicas = 10
n_random_swaps = n_replicas - 1
n_iterations = 10
# replicas are initialized with random samples
bqm = dimod.BinaryQuadraticModel.from_numpy_matrix(Q)
state = hybrid.State.from_problem(bqm)
replicas = hybrid.States(*[state.updated() for _ in range(n_replicas)])
# get a reasonable beta range
beta_hot, beta_cold = neal.default_beta_range(bqm)
# generate betas for all branches/replicas
betas = np.geomspace(beta_hot, beta_cold, n_replicas)
# run replicas update/swap for n_iterations
# (after each update/sampling step, do n_replicas-1 random adjacent pair swaps)
update = hybrid.Branches(*[
FixedTemperatureSampler(beta=beta, num_sweeps=n_sweeps) for beta in betas])
swap = hybrid.Loop(SwapReplicaPairRandom(betas=betas), max_iter=n_random_swaps)
workflow = hybrid.Loop(update | swap, max_iter=n_iterations) \
| hybrid.MergeSamples(aggregate=True)
time_start=time.time()
Par_Tempering_response = workflow.run(replicas).result()
time_stop=time.time()
CPUtime_Par_Tempering = time_stop -time_start
print('CPU time Hybrid_Par_Tempering: {}'.format(CPUtime_Par_Tempering))
print('Minimum energy Hybrid_Par_Tempering: {}'.format(Par_Tempering_response.samples.first.energy))
Yes I don't see a clear advantage
Hi Andrea,
For the error you were seeing with the hybrid dialectic solver, if you could create an issue with the above code example (just the dialectic part) and the dataset that you had mentioned so we can attempt to reproduce the behaviour, that would be really helpful.
You can use this page to submit the issue:
https://github.com/dwavesystems/dwave-hybrid/issues/new
Unfortunately, comparing the compute times and results of CPU-only solver setups, might not be the most effective approach.
To start, each solver in general (CPU and QPU alike) performs well on some problems and not so well on others. This means that there is no one-solver-fits-all solution.
As you can imagine, choosing the best setup (e.g. qbsolv, dwave-hybrid) for a given problem doesn't guarantee that a different solver will perform well in that same setup.
Similarly dwave-hybrid and qbsolv are designed with different use-cases in mind, and also built using different technologies.
At its core, qbsolv is a solver that has been written in C - a compiled language - and has been optimized to perform well on a CPU.
On the other hand, dwave-hybrid is a framework written in Python, designed for creating classical-quantum hybrid workflows with an emphasis on ease of use, rather than performance.
Although qbsolv is capable of using the QPU solver, it blocks on calls to the QPU, which causes a serious drop in performance.
This issue was accounted for with dwave-hybrid, allowing for asynchronous access of the QPU, without blocking code execution while waiting for calls to return.
Our development team is working on improving dwave-hybrid and building out new functionality to better meet the needs of our users. Unfortunately qbsolv development is already in maintenance-only mode, and no future changes or improvements are planned.
If you would like to develop a solution to a problem in an iterative fashion, a great starting place is with an existing dwave-hybrid workflow, such as Kerberos. This base workflow can then be optimized by adjusting available parameters, and building out the workflow functionality to meet the needs of a specific problem.
Here is a link to some reference workflows like Kerberos mentioned above:
https://docs.ocean.dwavesys.com/en/stable/docs_hybrid/reference/reference.html
I hope this addresses your questions, and helps to clarify the difference in behaviour among the solvers a little better.
Of course, please feel free to ask more questions, or for clarification if needed.
Please sign in to leave a comment.