Pseudo-Boolean function: Difference between revisions

Revision as of 04:30, 21 April 2025

Revision as of 18:13, 5 June 2025

Line 2:

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

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

where {{math|1='''B''' = {{mset|0, 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==

Line 30:

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=Kahl2011>{{cite conference |last1=Kahl |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 and no indication on how to assign the three variables. Using the second reduction, we obtain the (tight) lower bound of -2 and the optimal assignment of every variable (which is <math> {(0,1,1)}</math>).