1 Answers
Quadratic pseudo-Boolean optimisation is a combinatorial optimization method for quadratic pseudo-Boolean functions in the form
in the binary variables x p ∈ { 0 , 1 } ∀ p ∈ V = { 1 , … , n } {\displaystyle x_{p}\in \{0,1\}\;\forall p\in V=\{1,\dots ,n\}} , with E ⊆ V × V {\displaystyle E\subseteq V\times V}. If f {\displaystyle f} is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if f {\displaystyle f} contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in polynomial time.
QPBO is a useful tool for inference on Markov random fields and conditional random fields, and has applications in computer vision problems such as image segmentation and stereo matching.