Quadratic pseudo-Boolean optimization

is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if

contains non-submodular terms then the algorithm produces a partial solution with specific optimality properties, in both cases in polynomial time.

[1] 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.

of the quadratic terms satisfy the submodularity condition then the function can be efficiently optimised with graph cut optimization.

It is indeed possible to represent it with a non-negative weighted 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, Edmonds–Karp, and 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.

Such method produces results generally superior to submodular approximations of the target function.

[1] QPBO produces a solution where each variable assumes one of three possible values: true, false, and undefined, noted in the following as 1, 0, and

The algorithm can be divided in three steps: graph construction, max-flow computation, and assignment of values to the variables.

After re-parametrising the function to normal form,[note 1] a pair of edges is added to the graph for each term

: The minimum cut of the graph can be computed with a max-flow algorithm.

Once the minimum cut is known, each variable receives a value depending upon the position of its corresponding nodes

belongs to the connected component containing the sink then the variable will have value of 0.

belong to the same connected component, then the value of the variable will be undefined.

[3] However, computing an optimal solution for the subset of undefined variables is still a NP-hard problem.

[1] Different exact and approximate strategies to minimise the number of undefined variables exist.

[2] 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 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.