Quadratic pseudo-Boolean optimization: Difference between revisions

Revision as of 08:28, 2 October 2019

Revision as of 18:11, 5 October 2019

Line 16:

then the function can be efficiently optimised with [[graph cut optimization]]. It is indeed possible to represent it with a non-negative weighted [[graph (discrete mathematics)|graph]], and the global minimum can be found in polynomial time by computing a [[minimum cut]] of the graph, which can be computed with algorithms such as [[Ford–Fulkerson algorithm|Ford–Fulkerson]], [[Edmonds–Karp algorithm|Edmonds–Karp]], and [[Boykov–Kolmogorov algorithm|Boykov–Kolmogorov]]'s.

If the function is not submodular, then the problem is [[NP-hard]] in the general case and it is not always possible to solve it exactly in polynomial time. It is possible to replace the target function with a similar but submodular approximation, e.g. by removing all non-submodular terms or replacing them with submodular approximations, but such approach is generally sub-optimal and it produces satisfying results only if the number of non-submodular terms is relatively small. <ref name="review" />

QPBO builds an extended graph, introducing a set of auxiliary variables ideally equivalent to the negation of the variables in the problem. If the nodes in the graph associated to a variable (representing the variable itself and its negation) are separated by the [[minimum cut]] of the graph in two different connected components, then the optimal value for such variable is well defined, otherwise it is not possible to infer it. Such method produces results generally superior to submodular approximations of the target function.<ref name="review" />