A pseudo-Boolean function is a mapping from $\mathcal{B}^n = \{0, 1\}^n$ to $\mathbb{R}$.

Following is a pseudo-Boolean function.

$$s_1 s_4 - s_2 s_3 - s_3 s_5 - s_2 s_5 + s_1 + s_4 - s_1 s_3 - s_1 s_5 - s_3 s_5 + s_2 s_4 + s_2 + s_4 - s_1 - s_2 + 3 s_1 s_2$$

Here, $s_i$'s are the Boolean variables taking values from $\{0, 1\}$. It has two solutions for the global minima, $01101$ and $10101$.

I would like to know what is the best known algorithm to generate a pseudo-Boolean function from a given list of solutions.

  • 1
    $\begingroup$ "best" by what metric? How do you plan to evaluate answers? $\endgroup$
    – D.W.
    Aug 8 '15 at 6:37
  • $\begingroup$ @D.W., time complexity. $\endgroup$ Aug 8 '15 at 15:10

There's a straightforward way to construct a function $f_z:\{0,1\}^n \to \mathbb{R}$ that is zero at only a single point $z=(z_1,\dots,z_n)$ and strictly positive everywhere else: namely,

$$f_z(x_1,\dots,x_n) = (x_1-z_1)^2 + (x_2-z_2)^2 + \dots + (x_n-z_n)^2.$$

Based on this, we can easily construct a function $g : \{0,1\}^n \to \mathbb{R}$ that is zero at only the points $z[1],\dots,z[k]$ and strictly positive elsewhere: namely,

$$g(x) = f_{z[1]}(x) \cdot f_{z[2]}(x) \cdots f_{z[n]}(x).$$

It follows immediately that the pseudo-Boolean function $g$ has global minima at exactly the points $z[1],\dots,z[k]$ and no others, so it meets all your criteria. This "algorithm" is simple and efficient.

  • $\begingroup$ In my case, I am not even sure whether the global minima is $0$. I just know that I want the given solutions to have the least functional value. It could be any real number. $\endgroup$ Aug 9 '15 at 16:44
  • 2
    $\begingroup$ @OmarShehab, I have no idea what you are trying to say. My answer meets all the requirements listed in your question. If there was some additional requirement that you forgot to include, I suggest you edit the question to state it explicitly. (If you want the global minima to have a value other than $0$, say the value $v$, then use the function $g(x)+v$ instead of $g(x)$.) $\endgroup$
    – D.W.
    Aug 10 '15 at 1:04
  • $\begingroup$ Agreed. Accepted. $\endgroup$ Aug 11 '15 at 17:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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