Hope to solve a basic optimization example

• 

  Mohammad D  (Report)

  August 31, 2021 19:59

  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𝑥₁ + 21𝑥₂ + 19𝑥₃)

            Constraints: 𝑥₁ + 𝑥₂ + 𝑥₃ = 2

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

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

            Objective: 𝑚𝑖𝑛(17𝑥₁ + 21𝑥₂ + 19𝑥₃)

            Constraints: (𝑥₁ + 𝑥₂ + 𝑥₃ – 2)²  *squared to avoid negative values

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

            𝑚𝑖𝑛(17𝑥₁ + 21𝑥₂ + 19𝑥₃) + 𝛾(𝑥₁ + 𝑥₂ + 𝑥₃ – 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
• 

  Tianxiang Y  (Report)

  August 31, 2021 23:57

  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
• 

  Mohammad D  (Report)

  September 03, 2021 22:47

  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.