Quadratization of Pseudo-Boolean Functions

Endre Boros
Professor and Director of Rutgers Center for Operations Research (RUTCOR)

Date and Time: 

Wednesday, November 7, 2012 - 4:00pm

Event Location: 

Mohler Lab Room 451

Set functions, i.e., real mappings form the family of subsets of a nite set to the reals are known and widely used in discrete mathematics for almost a century, and in particular in the last 50 years. If we replace a finite set with its characteristic vector, then the same set function can be interpreted as a mapping from the set of binary vectors to the reals. Such mappings are called pseudo-Boolean functions and were introduced in the works of Peter L. Hammer in the 1960s. Pseudo-Boolean functions are dierent from set functions, only in the sense that their algebraic representation, a multilinear polynomial expression, is usually assumed to be available as an input representation.

The problem of minimizing a pseudo-Boolean function (over the set of binary vectors) appears to be the common form of numerous optimization problems, including the well-known MAX-SAT and MAX-CUT problems, and have applications in areas ranging from physics through chip design to computer vision, etc. Some of these applications lead to the minimization of a quadratic pseudo- Boolean function, and hence such quadratic binary optimization problems received ample attention in the past decades. One of the most frequently used technique is based on roof-duality, and aims at nding in polynomial time a simpler form of the given quadratic minimization problem, by fixing some of the variables at their provably optimum value (persistency) and decomposing the residual problem into variable disjoint smaller subproblems. The method in fact was found very eective in computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value. This algorithm was used by computer vision experts and a very ecient implementation, called QPBO, is freely downloadable.

In many applications of pseudo-Boolean optimization, in particular in vision problems, the objective function is a higher degree multilinear polynomial. For such problems there are substantially fewer effective techniques available. In particular, there is no analogue to the persistencies (fixing variables at their provably optimum value) provided by roof-duality for the quadratic case. On the other hand, more and more applications would demand efficient methods for the minimization of such higher degree pseudo-Boolean functions. This increased interest, in particular in the computer vision community, lead to a systematic study of methods to reduce a higher degree minimization problem to a quadratic one. We report on the most recent techniques and the computational success of those. This is joint research with Alex Fix, Ramin Zabih (Cornell), and Aritanan Gruber (Rutgers).

Bio Sketch: 

Dr. Endre Boros is a Distinguished Professor of Rutgers University, the State University of New Jersey, and Director of the Operations Research Center (RUTCOR). He is the author of over 15 book chapters and edited volumes, and over 165 research papers published in refereed journals and reviewed conference proceedings. Dr. Boros research interests cover a wide range of topics in discrete mathematics and operations research, including combinatorics, graph theory, combinatorial optimization, integer programming, algorithmic game theory, the theory of Boolean functions, and learning theory. Dr. Boros organized numerous workshops and sessions in larger conferences on Boolean and pseudo-Boolean optimization and is in charge of the corresponding stream of sessions at the EURO meetings. He is on the editorial boards of numerous international journals, Associate Editor of the Annals of Mathematics and Artifcial Intelligence, and Editor-in-Chief of two major journals of his area, the Annals of Operations Research and Discrete Applied Mathematics.