1
$\begingroup$

I am trying to formulate a problem as QUBO problem and am not able to transform the inequality constraint.

$$ \sum_i^N x_i \geq 1 $$ into a suitable penalty function. For N = 2, the penalty term can be written as $$ P(1-x_1-x_2+x_1x_2)$$ as mentioned in A Tutorial on Formulating and Using QUBO Models. Can someone help me in generalising the above constraint to equivalent penalty.

$\endgroup$

1 Answer 1

0
$\begingroup$

It would help if you used slack variables and squared penalties. One way of doing it is by defining the following penalty $$P\left(\sum_{i=1}^{N}x_i - 1 - Z \right)^2,$$ where $Z$ is an integer variable such that $0 \leq Z \leq N-1$.

If you use the D-Wave API, I believe you can easily define an integer (discrete) variable $Z$. If you use something else, you may need to express $Z$ as an expansion of auxiliary binary variables: $$ Z = \sum_{k=0}^{M-1} 2^ky_k + ry_M, $$ where $M = \lfloor \log_2 Z \rfloor$ and $r$ is the remainder so that $Z \leq N-1$. The remainder can be written as $r = N + 1 - 2^M$. For more details on this, see Section 2.4.

Intuitively, whenever $\sum_i x_i \geq 1$, the values of $Z$ make the entire penalty term disappear. However, when $\sum_i x_i =0$, no matter what $Z$ is, we get the penalty $P(1 + Z)^2$.

$\endgroup$

Your Answer

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

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