3
$\begingroup$

During the formulation of a QUBO matrix I have a question regarding penalty formulation. Once I'm done with QUBO formulation such as $x_{i}Ax_{j}$ where A is the QUBO matrix, $x_{i}$ and $x_{j}$ are binary variables.

However, the variables $x_{i}$ and $x_{j}$ shall satisfy the constraint such as $x_{i}+x_{j} \leq 1$

In this case, I can extend my QUBO formulation to the follows: $x_{i}Ax_{j}+\underbrace{(x_{i}+x_{j}-1)}_{Penalty}$

I would like to know whether my formulation regarding penalty is correct? I suppose yes because once both $x_{i}$ and $x_{j}$ 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 by D-Wave, the approach by D-Wave 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.

$\endgroup$

1 Answer 1

0
$\begingroup$

Unfortunately, your penalty term is not correct. When working with QUBO, penalties should be equal to zero for all feasible solutions to the problem.

The proper way express $x_i + x_j \leq 1$ as a penalty is writing it as $\gamma x_i x_j$ where $\gamma$ is a positive penalty scaler (assuming you minimize). Note that if $x_i = 1$ and $x_j = 0$ (or vice versa) then $\gamma x_i x_j = 0$. So the penalty does not contribute to the objective function in any way, as it suppose to do.

However, if $x_i, x_j = 1$. Then, clearly your constraint is violated and you get a penalty of $\gamma x_i x_j = \gamma$.

Regarding the D-wave documentation about inequality constraints. Yes, this is indeed correct. In general, you need to have slack variables to keep your penalties to be zero for all feasible solutions. I can give a general example. Suppose we have inequality constraint $$\tag{1} q^Tx \leq c$$ where $q \in \mathbb{Z}_+^n$ is a vector of coefficients and $x \in \{0,1\}^n$ is a vector of decision variables. To incorporate this into the objective function you convert (1) into a squared penalty $$\gamma (q^Tx - z)^2$$ where $z$ is an integer slack variable such that $0 \leq z \leq c$. When the constraint (1) is satisfied $\gamma (q^Tx - z)^2 = 0$ because the slack variable takes on the value of $q^Tx$, i.e. $q^Tx = z$. However, if the constraint is violated, then we have $q^Tx > c$. Since $z \leq c$ we get a non-zero penalty term, $\gamma (q^Tx - z)^2>0$.

Now, our problem should be QUBO, but we have an integer, non-binary variable $z$! This means we need to express $z$ as a binary expansion such that $z \leq c$. This is a bit tricky but doable. I just give one possible way of doing it and it is not the best way of doing it! We can express $z$ as $$z = \sum_{k=1}^c ky_k$$ where $y_k \in \{0,1\}$. This makes sure that $z$ can take on any integer value between $0$ and $c$. There are many other more efficient and clever ways of expressing $z$ such that $z \leq c$.

Note that this only applies to $q$ being an integer vector with positive entries. If it is rational, the situation becomes slightly more complicated. But the idea is the same.

$\endgroup$
7
  • $\begingroup$ Thank you for your detailed explanation. Regarding the binary encoding of z, we can use log to get the value of c. For the example at the beginning, is it necessary always apply alpha (I mean alphaxixj)? I can actually do in this way: (xi-xj-1+slack)^2=0. Can you please explain it? Thanks! $\endgroup$ Commented Jun 26, 2022 at 14:30
  • $\begingroup$ Nice, log trick is even better for expressing $z$. For the example at the beginning, it is better to use $\alpha x_i x_j$ because it is simple, does not require exta variables and squaring. What you wrote is suboptimal because you have much more terms and variable interactions. Every additional binary variable doubles the search space, and squaring unnecessarily introduces interaction $x_i z, x_j z$ which makes the problem harder and requires more qubit interactions on hardware side. So there is no point in doing so. Also what you proposed in the comment is also incorrect. $\endgroup$
    – MonteNero
    Commented Jun 26, 2022 at 19:04
  • $\begingroup$ Do you mean (xi-xj-1+slack)^2 = 0 I'm pretty sure it is correct because it's the trick from the D-Wave document. By the way, is it OK to get rid of alpha? I suppose yes. $\endgroup$ Commented Jun 28, 2022 at 6:13
  • $\begingroup$ even at the conceptual level $(x_i - x_j - 1 + z)^2 = 0$ doesn't make sense. Why do you write it as equality? It is not an equation, it is a penalty term. Second, plug in the vector $(1,1)$ then according to your weird equation you get $(1 - 1 -1+ z)^2 = (z - 1)^2$. What is the point of this? Your slack variable $z$ will take on value $1$ and then the penalty is zero. But your solution $(1,1)$ is in fact infeasible. Knowing folks at D-Wave I'm sure whatever they wrote is correct but you seem to be confused about something else. $\endgroup$
    – MonteNero
    Commented Jun 29, 2022 at 1:27
  • $\begingroup$ Thank you for your answer. Based on the document of D-Wave (docs.dwavesys.com/docs/latest/…) you can transform inequality to equality, isn't it? And can you please explain why do we need to plug the vector (1,1) because this is actually the solution space which we are looking for. Thank you for the explanation. $\endgroup$ Commented Jun 30, 2022 at 12:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.