Content deleted Content added
Citation bot (talk | contribs) Removed parameters. | Use this bot. Report bugs. | Suggested by Dominic3203 | Category:Mathematical optimization | #UCB_Category 74/126 |
Tags: Mobile edit Mobile web edit Advanced mobile edit |
||
| (3 intermediate revisions by 3 users not shown) | |||
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 23:
===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=Boros2002>{{cite journal |last1=Boros |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=Boros2002/>
===Quadratizations===
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
===Polynomial Compression Algorithms===
| |||