Pseudo-Boolean function: Difference between revisions

Revision as of 04:55, 13 August 2019

Latest revision as of 04:13, 21 June 2025

(48 intermediate revisions by 21 users not shown)

Line 1:

{{Short description|Generalization of binary functions}}

In [[mathematics]] and [[optimization]], a '''pseudo-Boolean function''' is a [[function (mathematics)|function]] of the form

:<math>f: \mathbf{B}^n \rightarrowto \mathbb{R},</math>,

where {{math|1='''B'''&nbsp; =&nbsp; {{mset|0,&nbsp; 1}}}} is a ''[[Boolean ___domain]]'' and ''{{mvar|n''}} is a nonnegative [[integer]] called the [[arity]] of the function. A [[Boolean function]] is then a special case, where the values are also restricted to 0, or 1.

==Representations==

Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Citecite journal |urllast1=Hammer |first1=P.L. |titlelast2=Rosenberg |first2=I. |last3=Rudeanu |first3=S.|date=1963 |title=On the determination of the minima of pseudo-Boolean functions|last = Hammer|first language=ro P.L.|date = 1963|journal = Studii ¸siși Cercetaricercetări Matematice|doimatematice = |pmid = |access-date = |last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue = 14|publisher = |pages = 359–364|language = Romanian|issn = 0039-4068}}</ref><ref>{{Citecite book |titlelast1=Hammer |first1=Peter L. |last2=Rudeanu |first2=Sergiu |year=1968 |title=Boolean Methods in Operations Research and Related Areas|last = Hammer|first = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|___location = |pages = |last2 = Rudeanu|first2 = Sergiu}}</ref>

Any pseudo-Boolean function can be written uniquely as a [[multi-linear]] polynomial:<ref>{{Cite journal|url = |title = On the determination of the minima of pseudo-Boolean functions|last = Hammer|first = P.L.|date = 1963|journal = Studii ¸si Cercetari Matematice|doi = |pmid = |access-date = |last2 = Rosenberg|first2 = I.|last3 = Rudeanu|first3 = S.|issue = 14|publisher = |pages = 359–364|language = Romanian|issn = 0039-4068}}</ref><ref>{{Cite book|title = Boolean Methods in Operations Research and Related Areas|last = Hammer|first = Peter L.|publisher = Springer|year = 1968|isbn = 978-3-642-85825-3|___location = |pages = |last2 = Rudeanu|first2 = Sergiu}}</ref>

:<math>f(\boldsymbol{x}) = a + \sum_i a_ix_i + \sum_{i<j}a_{ij}x_ix_j + \sum_{i<j<k}a_{ijk}x_ix_jx_k + \ldots</math>

The '''degree''' of the pseudo-Boolean function is simply the degree of the [[polynomial]] in this representation.

In many settings (e.g., in [[Analysis of Boolean functions|Fourier analysis of pseudo-Boolean functions]]), a pseudo-Boolean function is viewed as a function <math>f</math> that maps <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Again in this case we can uniquely write <math>f</math> as a multi-linear polynomial:

<math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i, </math> where <math> \hat{f}(I) </math> are Fourier coefficients of <math>f</math> and <math>[n]=\{1,...,n\}</math>.

==Optimization==

Minimizing (or, equivalently, maximizing) a pseudo-Boolean function is [[NP-hard]]. This can easily be seen by formulating, for example, the [[maximum cut]] problem as maximizing a pseudo-Boolean function.<ref name="boroshammer" Boros2002/>

===Submodularity===

The [[submodular set function]]s can be viewed as a special class of pseudo-Boolean functions, which is equivalent to the condition

:<math> f(\boldsymbol{x}) + f(\boldsymbol{y}) \ge f(\boldsymbol{x} \wedge \boldsymbol{y}) + f(\boldsymbol{x} \vee \boldsymbol{y}), \; \forall \boldsymbol{x}, \boldsymbol{y}\in \mathbf{B}^n\,. </math>

This is an important class of pseudo-boolean functions, because they can be [[Submodular set function#Submodular Minimization|minimized in polynomial time]].

This is an important class of pseudo-boolean functions, because they can be [[Submodular set function#Submodular set function minimization|minimized in polynomial time]]. Note that minimization of a submodular function is a polynomially solvable problem independent on the presentation form, for e.g. pesudo-Boolean polynomials, opposite to maximization of a submodular function which is NP-hard, Alexander Schrijver (2000).

===Roof Duality===

If ''f'' is a quadratic polynomial, a concept called ''roof duality'' can be used to obtain a lower bound for its minimum value.<ref name="boroshammer"Boros2002>{{cite journal |last1=Boros and|first1=E. |last2=Hammer, |first2=P. L. |year=2002 |title=Pseudo-Boolean Optimization |journal=[[Discrete Applied Mathematics]] |doi=10.1016/S0166-218X(01)00341-9 |doi-access=free |volume=123 |issue=1–3 |pages=155–225 |hdl=2268/202427 |url=http://orbi.ulg.ac.be/handle/2268/202427|hdl-access=free }}</ref> Roof duality may also provide a partial assignment of the variables, indicating some of the values of a minimizer to the polynomial. Several different methods of obtaining lower bounds were developed only to later be shown to be equivalent to what is now called roof duality.<ref name="boroshammer" Boros2002/>

===Quadratizations===

If the degree of ''f'' is greater than 2, one can always employ ''reductions'' to obtain an equivalent quadratic problem with additional variables.<ref name="ishikawa2011">Ishikawa, 2011</ref> One possible reduction is

:<math>\displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(2-x_1-x_2-x_3) </math>

There are other possibilities, for example,

:<math> \displaystyle -x_1x_2x_3=\min_{z\in\mathbf{B}}z(-x_1+x_2+x_3)-x_1x_2-x_1x_3+x_1. </math>

Different reductions lead to different results. Take for example the following [[Cubic function|cubic polynomial]]:<ref name="kahlstrandmark"Kahl2011>{{cite conference |last1=Kahl and|first1=F. |last2=Strandmark, |first2=P. |year=2011|title=Generalized Roof Duality for Pseudo-Boolean Optimization |conference=[[International Conference on Computer Vision]] |url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}</ref>

:<math> \displaystyle f(\boldsymbol{x})=-2x_1+x_2-x_3+4x_1x_2+4x_1x_3-2x_2x_3-2x_1x_2x_3. </math>

Using the first reduction followed by roof duality, we obtain a lower bound of -3−3 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2−2 and the optimal assignment of every variable (which is <math> {(0,1,1)}</math>).

===Polynomial Compression Algorithms===

Consider a pseudo-Boolean function <math> f </math> as a mapping from <math>\{-1,1\}^n</math> to <math>\mathbb{R}</math>. Then <math> f(x)= \sum_{I\subseteq [n]}\hat{f}(I)\prod_{i\in I}x_i. </math> Assume that each coefficient <math>\hat{f}(I)</math> is integral. Then for an integer <math>k</math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math>k</math> is NP-complete. It is proved in <ref name=Crowston2011>{{cite journal |last1=Crowston |first1=R. |last2=Fellows |first2=M. |last3=Gutin |first3=G. |last4=Jones |first4=M. |last5=Rosamond |first5=F. |last6=Thomasse |first6=S. |last7=Yeo |first7=A. |year=2011 |title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average. |journal=Proc. Of FSTTCS 2011 |arxiv=1104.1135 |bibcode=2011arXiv1104.1135C}}</ref> that in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k).</math> Let <math>r</math> be the degree of the above multi-linear polynomial for <math>f</math>. Then <ref name=Crowston2011/> proved that in polynomial time we can either solve P or reduce the number of variables to <math>r(k-1)</math>.

Then for an integer <math> k </math> the problem P of deciding whether <math> f(x) </math> is more or equal to <math> k </math> is NP-complete. It is proved in <ref name="crow">Crowston et al., 2011</ref> that

in polynomial time we can either solve P or reduce the number of variables to <math> O(k^2\log k) </math>.

Let <math> r </math> be the degree of the above multi-linear polynomial for <math> f </math>. Then <ref name="crow">Crowston et al., 2011</ref> proved that in polynomial time we can either solve P or reduce the number of variables to <math> r(k-1) </math>.

==See also==

*[[Boolean function]]

*[[Quadratic pseudo-Boolean optimization]]

==References==

* {{cite journal|last=Boros|author2=Hammer |title=Pseudo-Boolean Optimization|journal=Discrete Applied Mathematics|year=2002|volume=123|issue=1–3 |pages=155–225 |doi=10.1016/S0166-218X(01)00341-9}}

* {{cite journal|last=Crowston |author2=Fellows, Gutin |author3=Jones, Rosamond |author4=Thomasse, Yeo|title=Simultaneously Satisfying Linear Equations Over GF(2): MaxLin2 and Max-r-Lin2 Parameterized Above Average.|journal=Proc. Of FSTTCS 2011|year=2011|arxiv=1104.1135|bibcode=2011arXiv1104.1135C}}

* {{cite journal|last=Ishikawa|title=Transformation of general binary MRF minimization to the first order case|journal=IEEE Transactions on Pattern Analysis and Machine Intelligence|year=2011|volume=33|number=6|pages=1234–1249|doi=10.1109/tpami.2010.91|pmid=20421673|citeseerx=10.1.1.675.2183}}

* {{cite journal|last=Rother|author2=Kolmogorov|author3=Lempitsky|author4=Szummer|title=Optimizing Binary MRFs via Extended Roof Duality|journal=International Conference on Computer Vision and Pattern Recognition|year=2007|url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}

* {{cite journal|last=Kahl|author2=Strandmark |title=Generalized Roof Duality for Pseudo-Boolean Optimization|journal=International Conference on Computer Vision |year=2011|url=http://www.maths.lth.se/vision/publdb/reports/pdf/kahl-strandmark-iccv-11.pdf}}

* {{cite journal|last=O'Donnell|first=Ryan|title=Some topics in analysis of Boolean functions|journal={{ECCC|2008|08|055}}|year=2008|url=http://www.eccc.uni-trier.de/eccc-reports/2008/TR08-055/}}

==Notes==

<references />

==References==

* {{cite journal |last=Ishikawa |first=H. |year=2011 |title=Transformation of general binary MRF minimization to the first order case |journal=[[IEEE Transactions on Pattern Analysis and Machine Intelligence|year=2011|volume=33|number=6|pages=1234–1249]] |doi=10.1109/tpami.2010.91 |pmid=20421673 |citeseerx=10.1.1.675.2183 |s2cid=17314555 |volume=33 |number=6 |pages=1234–1249}}

* {{cite journal |last=O'Donnell |first=Ryan | author-link = Ryan O'Donnell (computer scientist)|year=2008 |title=Some topics in analysis of Boolean functions |journal={{ECCC |2008|08|055}}|yearissn=20081433-8092 |url=httphttps://www.eccc.uni-trierweizmann.deac.il/eccc-reportsreport/2008/TR08-055/}}

* {{cite journalconference |lastlast1=Rother |first1=C. |author2last2=Kolmogorov |author3first2=V. |last3=Lempitsky |first3=V. |author4last4=Szummer |first4=M. |year=2007 |title=Optimizing Binary MRFs via Extended Roof Duality |journalconference=International [[Conference on Computer Vision and Pattern Recognition|year=2007]] |url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}

* {{cite journal |last=Schrijver |first=Alexander |date=November 2000 |title=A Combinatorial Algorithm Minimizing Submodular Functions in Strongly Polynomial Time |journal=Journal of Combinatorial Theory |doi=10.1006/jctb.2000.1989 |volume=80 |issue=2 |pages=346–355|doi-access=free }}

[[Category:Mathematical optimization]]