Penalty formulation regarding inequalitties

Question

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.

Answer 1

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.