QUBO formulation regarding penalty

During the formulation of a QUBO matrix I have a question regarding penalty formulation. Once I'm done with QUBO formulation such as xi*A*xj where A is the QUBO matrix, xi and xj are binary variables.

However, the variables xi and xj shall satisfy the constraint such as xi+xj1

In this case, I can extend my QUBO formulation to the follows: xi*A*xj+(xi+xj1) where penalty:(xi+xj1)

I would like to know whether my formulation regarding penalty is correct? I suppose yes because once both xi and xj and xj violate the constraint, it will deliver positive energy as penalty, otherwise 0 or negative energy.

On the other hand, based on the documentation regarding problem formulation, the approach to solve inequalities (as penalty) is using slack variable. I think the reason why they do this is they try to solve the problem without building QUBO matrix directly, correct?

Thank you for your answer.

1

Comments

4 comments
  • Hi Kai-Chun,

    Using ( xi + xj −1 ) as penalty for constraint xi + xj ≤ 1, will prefer xi==0xj==0 over xi==1xj==0 and xi==0xj==1.

    I recommend the penalty ( xi * xj ) unless preferring 0,0 over 1,0 and 0,1 was intended.

    QUBO = xi * A * xj + ( xi * xj )
    Objective = xi * A * xj
    Constraint = xi + xj ≤ 1
    where A is the QUBO matrix, and xi and xj are binary variables
    0
    Comment actions Permalink
  • Hi Mohammad,

    Thank you for your explanation. If I get your idea correctly, i.e. negative energy is always better than zero or positive energy. 

    However, I still have a question regarding your penalty formulation xi * xj because your penalty value also delivers 0,0 which is the best assignment of both variables. Can you please explain why this penalty term is better?

    Thank you for your explanation again! 

    0
    Comment actions Permalink
  • Hi Kai-Chun,

    Yes, the minimum energy state is preferred. 

    The following three solutions: (xi==0, xj==0), (xi==0, xj==1) and (xi==1, xj==0) all match the constraint of  xi + xj ≤ 1 . However, since the minimum energy state is preferred, using the penalty (xi + xj - 1) will prefer xi==0, xj==0 over the other two solutions

    penalty (xi + xj - 1)
    --------------
    xi==0, xj==0 = -1
    xi==0, xj==1 = 0
    xi==1, xj==0 = 0
    xi==1, xj==1 = 1

    While using the penalty (xi * xj) would weigh all three possible solutions equally

    penalty (xi * xj)
    --------------
    xi==0, xj==0 = 0
    xi==0, xj==1 = 0
    xi==1, xj==0 = 0
    xi==1, xj==1 = 1

     

     

    0
    Comment actions Permalink
  • Thank you! Now I understand more.

    0
    Comment actions Permalink

Please sign in to leave a comment.

Didn't find what you were looking for?

New post