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+xj≤1
In this case, I can extend my QUBO formulation to the follows: xi*A*xj+(xi+xj−1) where penalty:(xi+xj−1)
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.
Comments
Hi Kai-Chun,
Using
( xi + xj −1 )as penalty for constraintxi + xj ≤ 1, will preferxi==0,xj==0overxi==1,xj==0andxi==0,xj==1.I recommend the penalty
( xi * xj )unless preferring 0,0 over 1,0 and 0,1 was intended.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!
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
While using the penalty (xi * xj) would weigh all three possible solutions equally
Thank you! Now I understand more.
Please sign in to leave a comment.