Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 00:43, 20 September 2019

Revision as of 13:53, 26 September 2019

Line 50:

Reducing high-order terms to quadratics can be done by a process called "quadratization", and several dozen quadratization methods are given in [[Nike Dattani]]'s 2019 book "Quadratization in disctete optimization and quantum mechanics"<ref name="Dattani"></ref>. The problem of optimizing higher-order pseudo-boolean functions is generally difficult. It is always possible to reduce a higher-order function to a quadratic function which is equivalent with respect to the optimisation, problem known as "higher-order [[clique (graph theory)|clique]] reduction" (HOCR), and the result of such reduction can be optimized with QPBO. Generic methods for reduction of arbitrary functions rely on specific substitution rules and in the general case they require the introduction of auxiliary variables.<ref name="fix" /> In practice most terms can be reduced without introducing additional variables, resulting in a simpler optimization problem, and the remaining terms can be reduced exactly, with addition of auxiliary variables, or approximately, without addition of any new variable.<ref name="elc" />

== References Notes==

<references>

<ref name="Dattani">Dattani (2019) [https://arxiv.org/pdf/1901.04405 Quadratization in discrete optimization and quantum mechanics] (Book).</ref>

Line 59:

<ref name="rother">Rother et al. (2007).</ref>

</references>

==References==

* {{cite journal|first1=Alain|last1=Billionnet|first2=Brigitte|last2=Jaumard|author2-link= Brigitte Jaumard |title=A decomposition method for minimizing quadratic pseudo-boolean functions|journal=Operations Research Letters|volume=8|number=3|publisher=Elsevier|pages=161–163|year=1989|url=https://www.sciencedirect.com/science/article/pii/0167637789900436}}

* {{cite conference|first1=Alexander|last1=Fix|first2=Aritanan|last2=Gruber|first3=Endre|last3=Boros|first4=Ramin|last4=Zabih|title=A graph cut algorithm for higher-order Markov random fields|conference=IEEE International Conference on Computer Vision|year=2011|pages=1020–1027|url=https://www.cs.cornell.edu/~afix/Papers/ICCV11.pdf}}