# QUBO formulation: tackle constraint with multiplication of two variables

Hi there,

Currently I have got the constraint like this a+ab <= 1 which can be reformulated to equality by adding slack variable as follows:

(a+ab-1+slack)^2 = 0

Now, I can get all coefficients by calculating the reformulated equality. As the result, I get the follows:

-a+b+1-slack+2aslack+2abslack

My question is how can I get the value of b by D-Wave in this case? Does anyone have experience in terms of such kind of constraint? Thank you for your answer.

Best regards,

• Hi Kai-Chun,

Can you please clarify whether ab and the slack variable (let’s call it s) are all binary variables?

If that is the case, then it is a NAND constraint whenever either a or b is 0, implying the following:

a + ab <= 1 --> a + b <= 1

For demonstration purpose, let’s assume that s is the slack variable. The reformulation could follow as the example from Reformulating a Problem [Constraints: Linear Inequality (Penalty Functions)]:

a + b <= 1

(a + b + s – 1)^2 = 0

2ab + 2as + 2bs – a – b – s + 1 = 0

In that case, you can use Ocean’s dwave_networkx as demonstrated in the example (i.e. Q_constraint1 = {('a', 'a'): -1, ('b', 'b'): -1, ('s, 's'): -1('a', 'b'): 2, ('a', 's'): 2, ('b', 's'): 2})

I hope that helps.

Best Regards,

Tanjid Islam

• Hi Tanjid,

Thank you for your reply. In my case, a and b are binary variables but the slack variable can either be binary or non-binary.

I think your example is for the case where a, b, and s are binary, correct? But sometimes the binary variable could be an integer value. Do you have any idea how can I deal with it?

Best regards,
Kai-Chun

• Hi Kai-Chun,

Q1: For the example, is it correct that the case is valid when ALL of a, b, and s are binary?

If both variables a and b are binary, then it is a NAND constraint whenever either a or b is 0. implying the following:

a + ab <= 1 --> a + b <= 1

Q2: Do you have any idea how to deal with the case when the binary variable could be an integer value?

Can you please elaborate on this question?

Best Regards,

Tanjid

• Hi Tanjid,

In this case, we can reformulate the inequality above to a+b-2<=0 which can be reformulate to equality again, namely a+b+s-2=0. If we square the the equality, we'll get

a^2+2ab+2as+2bs+s^2+4=0.

Since s is non-binary thus we need to represent s in binary way, correct?

Regarding my original question regrading solving the equation (a+ab-1+slack)^2 = 0, I've found this article which helps me to solve my problem.

Thank you and all the best,

Kai-Chun

• Hi Kai-Chun,

If `a` and `b` are binary, then `a + ab <= 2` is satisfied for all the possible assignments to `a` and `b:`

``0 + 0*0 <= 21 + 1*0 <= 20 + 0*1 <= 21 + 1*1 <= 2``

In this case, there would be no use of the slack variable `s`. Please let me know if this answers your questions.

Best regards,
Tanjid

• Hi Tanjid,