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,




  • 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!

    Comment actions Permalink
  • 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
    # ------------------- Solve problem with QBSolv --------------------------------
    QBSolv_iter = 50
    #sampler = neal.SimulatedAnnealingSampler()
    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)
    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.RacingBranches(
    | hybrid.ArgMin('subsamples.first.energy')
    | hybrid.SplatComposer()
    ) | hybrid.ArgMin('samples.first.energy')
    main = hybrid.Loop(iteration, max_iter=2, convergence=3)
    # run the workflow
    init_state = hybrid.State.from_sample(hybrid.utils.min_sample(model), model)
    Hybrid_SA_TS_response = main.run(init_state).result()
    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
    init_state = hybrid.State.from_sample(hybrid.min_sample(model), model)
    final_state = global_update.run(init_state).result()
    Hybrid_Dialectic_response = tracker.best
    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
    init_state = hybrid.State.from_sample(hybrid.min_sample(model), model)
    Hybrid_QBSolv_like_response = main.run(init_state).result()
    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)
    Par_Tempering_response = workflow.run(replicas).result()
    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   

    Comment actions Permalink
  • 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:

    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:

    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.

    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post