Séminaires en optimisation GERAD/CRC-ONDI : « Quadratization of Pseudo-Boolean Functions »

Set functions, i.e., real mappings form the family of subsets of a finite 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 (Hammer and Rudeanu, 1968). Pseudo-Boolean functions are different 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 (Hammer, Hansen, Simeone, 1984), and aims at finding 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 (Boros and Hammer, 1989). The method in fact was found very effective in
computer vision problems, where frequently it can fix up to 80-90% of the variables at their provably optimum value (Boros, Hammer, Sun and Tavares,
2008). This algorithm was used by computer vision experts and a very efficient implementation, called QPBO, is freely downloadable (Rother, Kolmogorov,
Lempitsky and Szummer, 2007).

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.

Joint research with Alex Fix (Cornell University), Aritanan Gruber (Rutgers University), and Ramin Zabih (Cornell University).

---------------------------------------

Important

Ce séminaire vous permettra d’échanger avec le conférencier et les chercheurs présents autour de boissons et de collations.
Nous vous remercions de confirmer votre présence.
(http://doodle.com/e9gmu9htxrfaimpy)