1. D-Wave Systems
  2. Community
  3. Coding Tips and Tricks

QUBO formulation: tackle constraint with multiplication of two variables

Avatar
Kai-Chun L
Follow

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,

0

Comments

6 comments
Sort by Date Votes
  • Avatar
    Tanjid I  (Report)

    Hi Kai-Chun,

    Can you please clarify whether a, b 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

    0
    Comment actions Permalink
  • Avatar
    Kai-Chun L  (Report)

    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?

    Thank you for your reply again!

    Best regards,
    Kai-Chun

    0
    Comment actions Permalink
  • Avatar
    Tanjid I  (Report)

    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

    0
    Comment actions Permalink
  • Avatar
    Kai-Chun L  (Report)

    Hi Tanjid,

    Thank you for your answer. I mean how about a+b<=2 (for any value greater than 2)

    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

    0
    Comment actions Permalink
  • Avatar
    Tanjid I  (Report)

    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 <= 2
    1 + 1*0 <= 2
    0 + 0*1 <= 2
    1 + 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

    0
    Comment actions Permalink
  • Avatar
    Kai-Chun L  (Report)

    Hi Tanjid,

    Thank you for your answer. My question is solved. Thanks!

     

    Best regards,

    Kai-Chun

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post