Quadratic pseudo-Boolean optimization
Quadratic pseudo-Boolean optimisation (QPBO) is a combinatorial optimization method for quadratic pseudo-Boolean functions in the form in the binary variables formula_2, with formula_3. If formula_4 is submodular then QPBO produces a global optimum equivalently to graph cut optimization, while if formula_4 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. Optimization of non -submodular functions. If the coefficients formula_6 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. 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. Properties. 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 formula_8 respectively. The solution has the following two properties. Algorithm. The algorithm can be divided in three steps: graph construction, max-flow computation, and assignment of values to the variables. When constructing the graph, the set of vertices formula_23  contains the source and sink nodes formula_24 and formula_25, and a pair of nodes formula_26 and formula_27 for each variable. After re-parametrising the function to normal form, a pair of edges is added to the graph for each term formula_28: The minimum cut of the graph can be computed with a max-flow algorithm. In the general case, the minimum cut is not unique, and each minimum cut correspond to a different partial solution, however it is possible to build a minimum cut such that the number of undefined variables is minimal. Once the minimum cut is known, each  variable receives a value depending upon the position of its corresponding nodes formula_26 and formula_27: if formula_26 belongs to the connected component containing the source and formula_27 belongs to the connected component containing the sink then the variable will have value of 0. Vice versa, if formula_26 belongs to the connected component containing the sink and formula_27 to the one containing the source, then the variable will have value of 1. If both nodes formula_26 and formula_27 belong to the same connected component, then the value of the variable will be undefined. The way undefined variables can be handled is  dependent upon the context of the problem. In the general case, given a partition of the graph in two sub-graphs and two solutions, each one optimal for one of the sub-graphs, then it is possible to combine the two solutions into one solution optimal for the whole graph in polynomial time. However, computing an optimal solution for the subset of undefined variables is still a NP-hard problem. In the context of iterative algorithms such as formula_61-expansion, a reasonable approach is to leave the value of undefined variables unchanged, since the persistence property guarantees that the target  function will have non-increasing value. Different exact and approximate strategies to minimise the number of undefined variables exist. Higher order terms. 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 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. 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.