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?

• Hi Tianxiang,

We can follow these general guidelines to develop a QUBO

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

`#examplebqm = dimod.BinaryQuadraticModel({'x': 1, 'y': 1, 'z': 1}, {}, 0.0, 'BINARY')  # objectivebqm.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

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

Problem Solving Handbook

Please let us know if you have any questions.

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,

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