Groupe d’études et de recherche en analyse des décisions

A Decomposition Method for Minimizing Quadratic Pseudoboolean Functions

A Billionnet et Brigitte Jaumard

A decomposition method is proposed for minimizing quadratic pseudoboolean functions. The result is: minimum of f = ∑pi=1 (minimum of fi), where the function f is a sum of quadratic monomials, fi is a sum of monomials of f and each monomial of f appears in at most one fi.

, 8 pages