Is it possible to terminate sample_qubo when it finds a target solution ?

I am using LeapHybridSampler for solving a QUBO problem by  sample_qubo.

What I want to do is:

1. give a target energy value to sample_qubo, and

2. terminate sample_qubo as soon as it finds a solution with the target energy value or less,

because I want to evaluate the time-to-solution for the target energy.

Is this possible ?

If not, is there an alternative way to evaluate the time-to-solution of LeapHybridSampler ?

0

Comments

5 comments
  • Hi Koji,
    Unfortunately, there isn't a feature available at the moment to terminate sample_qubo when a solution with a target energy is found.

    To help us isolate potential alternative methods, could you please provide any steps you have taken so far to evaluate the time-to-solution for the specific problem?

    While it sounds like an interesting use case for a feature request, could you please tell us a bit more about what you are looking to solve with the feature?

    Best Regards,
    Tanjid

    0
    Comment actions Permalink
  • Hi, Tanjid,

      Thank you very much for your comments.

    I am now evaluating the performance of  several QUBO solvers including LeapHybridSampler. I want to evaluate the time-to-solution(tts) of QUBO problems generated by several kinds of optimization problems, for which the optimal solutions are known. Since the optimal solutions of them are known, it makes sense to evaluate the tts to obtain the optimal solutions. I can obtain the tts of the other QUBO solvers, but cannot obtain that of LeapHybridSampler.

    Also, I think this feature is mandatory for practical use of QUBO solvers. Probably, users want to specify both (A) time limit and (B) target energy when they start a QUBO solver. A QUBO solver terminates as soon as it finds a solution less than or equal to the target energy before the time limit. If the time limit exceeds, it just outputs the best solution obtained in the time limit. For a user who needs a solution of a target energy as soon as possible and the computing time is limited,  this feature is very helpful.

    Best regards,

    Koji

    0
    Comment actions Permalink
  • Hi Koji,

    Thank you for providing details around the use case. We have put in a feature request with our development team.

    In HSS (Hybrid Solver Services) BQM Sampler, the answer is slightly different for each time the problem is run, implying that the longer the solver runs, the better the average solution quality becomes.

    A feasible approach is by creating your own problems in the same problem class with an identified target energy and benchmarking your problems to obtain TTS (time-to-solution) from gathered metrics for probability of success for different time limits where the solution is found at the target energy.

     

    A hypothetical example:
    On an experiment with 10 attempts to run solvers for each time limit, double the time limit until the probability of success is at a rate that you are comfortable with, and you can roughly translate those data into TTS (time-to-solution) by calculating time_limit ÷ probability_success:

    • 3s: 0/10 success (3s÷(0/10)=infinite)
      6s: 1/10 success (6s÷(1/10)=60s)
      12s: 9/10 success (12s÷(9/10)=13s)

    In these cases, the last set of tests at 12s is the one with the smallest TTS.

    Here are resources that may be beneficial for your understanding of calculating TTS:

    Although, these methods are a bit QPU centric, they explain the concept well enough to build an understanding of how you can derive a similar method for HSS-BQM

     

    Best Regards,

    Tanjid

    0
    Comment actions Permalink
  • Dear Tanjid,

      Thank you very much for your reply.

    I understand how we can estimate the TTS.

    However, it is too costly to get such data to estimate the TTS.

    It would be nice if the API accepts a target energy, we can get the TTS for it directly.

    Koji

    0
    Comment actions Permalink
  • Hi Koji,

    Thank you for the details. We have already submitted a feature request based on your request and included additional information regarding the cost of finding the solution.

    With kind regards,

    Tanjid

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post