Pseudo-Boolean function: Difference between revisions

Revision as of 23:04, 18 October 2019

Latest revision as of 04:13, 21 June 2025

(43 intermediate revisions by 19 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. AnOne openpossible sourcereduction book on the subject, mainly written by [[Nike Dattani]], contains dozens of different quadratization methods<ref name="dattani">{{citationis

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

| last1 = Dattani | first1 = N.

| title = Quadratization in discrete optimization and quantum mechanics

| date = 2019-01-14| arxiv = 1901.04405

}}</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==

Line 53 ⟶ 45:

==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|author1=Boros, E.|author2=Hammer, P. L. |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=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 journal|author1=Crowston, R. |author2=Fellows, M. | author3= Gutin, G. |author4=Jones, M. | author5= Rosamond, F. |author6=Thomasse, S. | author7= Yeo, A.|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 conference |author1last1=Rother, |first1=C. |author2last2=Kolmogorov, |first2=V. |author3last3=Lempitsky, |first3=V. |author4last4=Szummer, |first4=M. |year=2007 |title=Optimizing Binary MRFs via Extended Roof Duality |conference= [[Conference on Computer Vision and Pattern Recognition]] |year=2007|url=http://research.microsoft.com/pubs/67978/cvpr07-QPBOpi.pdf}}

* {{cite journal|last=Ishikawa | first=H. |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=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 }}

* {{cite conference|author1=Kahl, F.|author2=Strandmark, P. |title=Generalized Roof Duality for Pseudo-Boolean Optimization| conference= [[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/}}

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

[[Category:Mathematical optimization]]