Hope to solve a basic optimization example

Hi

I am trying to use quantum annealing to solve the most basic optimization problem

I have followed most of the tutorials, and I have not found how to turn the problem into a binary one. For example:

I just want to 

Min: Ax+By+Cz

s.t      x+y+z=D

A,B,C,D are constant.

I know this can tell the answer at a glance, but for me as a beginner, I think it is a good example.

Or more complicated:

Min: xln(x/D) + yln(y/D) + zln(z/D)

s.t.  x+y+z=D

What to do next?

0

Comments

3 comments
  • Hi Tianxiang,

    We can follow these general guidelines to develop a QUBO

         1. Write out your objective and constraints in your problem domain.

         2. Convert your objective and constraints to math statements with binary variables.

         3. Make your objective and constraints “QUBO appropriate”.

    •      Objective is a minimization function
    •      Constraints are satisfied at their minimum values

         4. Combine your objective and constraints.

                   Ising or QUBO = min (objective+ 𝛾(constraints))

     

    With the example provided, if the x, y, z variables in objective and constraint are binary and:

              If objective is: min(Ax + By + Cz)

              If only constraint is: x + y + z = D

    Then the Ising or QUBO equivalent would be:

              min (Ax + By + Cz) + 𝛾(x + y + z – D)^2

    #example
    bqm = dimod.BinaryQuadraticModel({'x': 1, 'y': 1, 'z': 1}, {}, 0.0, 'BINARY')  # objective

    bqm.update(dimod.generators.combinations(['x', 'y', 'z'], D))

     

    Here’s another example problem we can convert to QUBO

    Problem: There are 3 boxes with values 17, 19, 21. Pick the pair of boxes with the smallest sum.

    Step 1: Write out your objective and constraints in your problem domain.

              Objective:  Minimize the sum of the boxes chosen

              Constraints: Pick exactly two boxes

    Step 2: Convert your objective and constraints to math statements with binary variables.

              variables: 𝑥𝑖 = 1 if box 𝑖 is selected, 𝑥𝑖 = 0 if box 𝑖 is not selected

              Objective: min (17𝑥1 + 21𝑥2 + 19𝑥3)

              Constraints: 𝑥1 + 𝑥2 + 𝑥3 = 2

    Step 3: Make your objective and constraints “QUBO appropriate”.

    • Objective is a minimization function
    • Constraints are satisfied at their minimum values

              Objective: 𝑚𝑖𝑛(17𝑥1 + 21𝑥2 + 19𝑥3)

              Constraints: (𝑥1 + 𝑥2 + 𝑥3 – 2)2  *squared to avoid negative values

    Step 4: Combine your objective and constraints.  min(objective+ 𝛾(constraints))

              𝑚𝑖𝑛(17𝑥1 + 21𝑥2 + 19𝑥3) + 𝛾(𝑥1 + 𝑥2 + 𝑥3 – 2)^2

     

    Here are some additional resources that may be helpful

    Knapsack Example (good beginner example that uses the hybrid solver)

    Problem Solving Handbook

    (video) Quantum Computing Tutorial Part 1: Quantum annealing, QUBOs and more

    (video) Quantum Computing Tutorials Part 2: QUBOs and Embedding

    (video) Quantum Programming 101: Solving a Problem From End to End | D-Wave Webinar

     

    I hope this was helpful!

    Please let us know if you have any questions.

     

    0
    Comment actions Permalink
  • Hi Mohammad

    Thank you so much for your help, your answer helped me sort out the process, and it helped me a lot.

     

    I have tried the method you mentioned and made very good progress. But I still ran into problems.

    I think the advantage of quantum computing is to solve complex nonlinear problems, So I simply wrote a nonlinear objective function.

    Like that example:

    Min: xln(x/D) + yln(y/D) + zln(z/D)

    s.t.  x+y+z=D

    About 2. Convert your objective and constraints to math statements with binary variables.

    I don't know how to convert the logarithmic form, whether it is using the Ocean library or mathematical methods.

    Can you provide me with some ideas in this regard? If quantum annealing is not suitable for this type of problem, can you please provide me with a paper or literature?

    Thank you for all your help.

    Sincerely,

     

    0
    Comment actions Permalink
  • Hi Tianxiang,

    The objective function that the hardware solves requires linear terms and quadratic terms, where the terms can be multiplied by real numbers (biases). We must use an objective function that meets those requirements.

    I don’t believe you can form a valid objective function using logarithmic functions since binary variables are either (0,1) for QUBO, or (-1,+1) for Spin Glass, and the logarithm of a negative number (e.g. -1) is an imaginary number; the logarithm of 0 is Undefined.

     

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post