Pseudo-Boolean optimization

By Endre Boros, Peter Ladislaw Hammer. 2002

965 citations recorded by the source corpus.

This survey examines the state of the art of a variety of problems related to pseudo-Boolean optimization, i.e. to the optimization of set functions represented by closed algebraic expressions. The main parts of the survey examine general pseudo-Boolean optimization, the specially important case of quadratic pseudo-Boolean optimization (to which every pseudo-Boolean optimization can be reduced), several other important special classes, and approximation algorithms.

Subfields: Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computational Theory and Mathematics

Citations in the corpus

Determinantal Point Processes for Machine Learning (2012, background): “More recently, certain types of inference in binary MRFs with associative (or submodular) potentials ψ have been shown to be tractable [17, 79, 146].”
Learning with Submodular Functions: A Convex Optimization Perspective (2011, background): “V. Equivalently, they may be deﬁned as functions on the vertices of the hyper-cube, i.e, {0,1}p where pis the cardinality of the base set V—they are then often referred to as pseudo-boolean functions [27]. Among these set-functions, submodular functions play an important role, similar to convex func”
Object Detection and Tracking for Autonomous Navigation in Dynamic Environments (2010, methodology): “This follows directly from the definition of submodularity (Boros and Hammer, 2002) 3.”
Learning to Estimate and Remove Non-uniform Image Blur (2013, background): “Although the minimization of an energy function such as that in Equation (3) is in general an NP-hard problem [2], it can be shown that it reduces to a min-cut/max-flow problem for ordered labels, such as ours [10, 19], and so its global optimum can be found by an efficient polynomial algorithm.”
Contextually guided semantic labeling and search for three-dimensional point clouds (2013, background): “The relaxation solution ŷcut has an interesting property called Persistence (Hammer et al., 1984; Boros and Hammer, 2002).”
Higher-order clique reduction in binary graph cut (2009, methodology): “This method by Boros, Hammer, and their co-workers [2] [4] [9] is variously called QPBO[15] or roof-duality[26].”
Playing with Duality: An overview of recent primal?dual approaches for solving large-scale optimization problems (2014, neutral): “GRAPH-CUTS AND MRF OPTIMIZATION For certain MRFs, optimizing their cost is known to be equivalent to solving a polynomial mincut problem [86], [87].”
Semantic Labeling of 3D Point Clouds for Indoor Scenes (2011, background): “The relaxation solution ŷcut has an interesting property called Persistence [2, 10].”
MAP Estimation of Semi-Metric MRFs via Hierarchical Graph Cuts (2009, methodology): “The algorithm is initialized by: (i) picking a random permutation π of the label indices{1, 2, · · · , H}, which defines a priority ordering on the cluster centers; and (ii) choosing a value of β ∈ [1, 2]”
Quantum Bridge Analytics I: a tutorial on formulating and using QUBO models (2019, background): “See [15] [16] and [43] for further discussions of QUBO and the Max Cut problem.”
Contextually Guided Semantic Labeling and Search for 3D Point Clouds (2011, background): “5 , 1 } atthesolution)[10]. alsobesolvedasaquadraticpseudo-Booleanoptimizationproblemusingagraph-cutmethod λ i 2 are the ﬁrst three Furthermore,thisrelaxationcan alsobesolvedasaquadraticpseudo-Booleanoptimizationproblemusingagraph-cutmethod[25],whichisordersofmagnitudefasterthanusingageneralpurposeL”
Video Pop-up: Monocular 3D Reconstruction of Dynamic Scenes (2014, methodology): “Finding an optimal move is formulated as a pseudo Boolean optimisation [4] and solved using graph-cuts [5].”
Minor-embedding in adiabatic quantum computation: I. The parameter setting problem (2008, methodology): “4 For example, this was used in the reduction from general (higher-order) unconstrained binary optimization to the quadratic one (see [8]).”
The unconstrained binary quadratic programming problem: a survey (2014, methodology): “A simple procedure (see for instance Hammer and Rudeanu 1968; Hansen 1979; Hansen et al. 1993; Boros and Hammer 2002) for ﬁnding an appropriate penalty for any linear constraint is given as follows: Consider the general constrained problem of the form This model accommodates both quadratic and…”
Relating Things and Stuff by High-Order Potential Modeling (2012, background): “Under the assumption that the projection of the energy is pairwise and submodular, it can be exactly solved using graph cuts [18,19].”
Minimizing Energies with Hierarchical Costs (2012, background): “A binary energy of form E′ = D′ +V ′ can be minimized efficiently by a graph cut if E′(x) is a submodular function (Boros and Hammer 2002; Kolmogorov and Zabih 2004).”