Quadratic pseudo-Boolean optimization

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form f ( x ) = w 0 + ∑ p ∈ V w p ( x p ) + ∑ ( p , q ) ∈ E w p q ( x p , x q ) {\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})} 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.

Source: Wikipedia — Quadratic pseudo-Boolean optimization (CC BY-SA 4.0)

Quadratic pseudo-Boolean optimization

Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for minimizing quadratic pseudo-Boolean functions in the form f ( x ) = w 0 + ∑ p ∈ V w p ( x p ) + ∑ ( p , q ) ∈ E w p q ( x p , x q ) {\displaystyle f(\mathbf {x} )=w_{0}+\sum _{p\in V}w_{p}(x_{p})+\sum _{(p,q)\in E}w_{pq}(x_{p},x_{q})} 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.

This neuron ends here.

Source: Wikipedia "Quadratic pseudo-Boolean optimization" · CC BY-SA 4.0

Share this article: X · Bluesky
Privacy Policy