3

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.

Rogue8989
  • 31
  • 2

2 Answers2

1

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$.

MonteNero
  • 3,344
  • 7
  • 24
0

The following naive generalization might be useful:

\begin{equation} 1 - \sum_\limits{i=1}^{n}x_i + \sum\limits_{\substack{\{j,k\}\in \{1,...,n\}^2\\ j\not=k}} x_j x_k \end{equation}

If all variables are set to $0$, this expression has a value of $1$. If one or two variables are set to $1$, the expression's value is $0$. If $m>2$ variables are set to $1$, its value is $1-m+$$m \choose 2$. Since $m \choose 2$$\ge m$, the expression's value is at least $1$. Thus, minimizing this expression guarantees that at least one variable is set to $1$. Nevertheless, it also forces your solution to have less than three variables set to $1$, i.e., $\sum\limits_{i=1}^n x_i \le 2$. You could partition your set of variables to avoid the effect of this last extra constraint.

For instance,

\begin{equation} 1-x_1-x_2-x_3+x_1x_2+x_1x_3+x_2x_3 \end{equation}

equals 1 when $x_1=x_2=x_3=1$. Thus, such assignment of values is unfeasible, i.e., it does not correspond to the minimum value of 0.

jesús garcía
  • 1
  • 1