Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 18:19, 5 October 2019

Revision as of 21:12, 5 October 2019

Line 48:

== Higher order terms ==

ReducingThe problem of optimizing highhigher-order termspseudo-boolean tofunctions quadraticsis cangenerally bedifficult. done by aThe process calledof "quadratization",reducing anda severalhigh-order dozenfunction quadratizationto methodsa arequadratic givenone inis [[Nikeknown Dattani]]'s 2019 bookas "Quadratization in disctete optimization and quantum mechanicsquadratization".<ref name="Dattanidattani">< /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" />

==Notes==

<references>

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

<ref name="review">Kolmogorov and Rother (2007).</ref>

<ref name="fix">Fix et al. (2011).</ref>

Line 62:

==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| pages=161–163|year=1989|url=https://www.sciencedirect.com/science/article/pii/0167637789900436|doi=10.1016/0167-6377(89)90043-6}}

* {{cite arXiv|title=Quadratization in discrete optimization and quantum mechanics|eprint=1901.04405|first=Nike|last=Dattani|author-link=Nike Dattani|year=2019}}

* {{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= [[International Conference on Computer Vision]] |year=2011|pages=1020–1027|url=https://www.cs.cornell.edu/~afix/Papers/ICCV11.pdf}}

* {{cite conference|first1=Hiroshi|last1=Ishikawa|title=Higher-Order Clique Reduction Without Auxiliary Variables|conference= [[Conference on Computer Vision and Pattern Recognition]]|year=2014|publisher=IEEE|pages=1362–1269|url=https://www.cv-foundation.org/openaccess/content_cvpr_2014/papers/Ishikawa_Higher-Order_Clique_Reduction_2014_CVPR_paper.pdf}}