Compact quadratizations for pseudo-Boolean functions

Endre Boros, Yves Crama, Elisabeth Rodríguez-Heck

Research output: Contribution to journalArticle

Abstract

The problem of minimizing a pseudo-Boolean function, that is, a real-valued function of 0–1 variables, arises in many applications. A quadratization is a reformulation of this nonlinear problem into a quadratic one, obtained by introducing a set of auxiliary binary variables. A desirable property for a quadratization is to introduce a small number of auxiliary variables. We present upper and lower bounds on the number of auxiliary variables required to define a quadratization for several classes of specially structured functions, such as functions with many zeros, symmetric, exact k-out-of-n, at least k-out-of-n and parity functions, and monomials with a positive coefficient, also called positive monomials. Most of these bounds are logarithmic in the number of original variables, and we prove that they are best possible for several of the classes under consideration. For positive monomials and for some other symmetric functions, a logarithmic bound represents a significant improvement with respect to the best bounds previously published, which are linear in the number of original variables. Moreover, the case of positive monomials is particularly interesting: indeed, when a pseudo-Boolean function is represented by its unique multilinear polynomial expression, a quadratization can be obtained by separately quadratizing its monomials.

Original languageEnglish (US)
Pages (from-to)687-707
Number of pages21
JournalJournal of Combinatorial Optimization
Volume39
Issue number3
DOIs
StatePublished - Apr 1 2020

All Science Journal Classification (ASJC) codes

  • Control and Optimization
  • Applied Mathematics
  • Discrete Mathematics and Combinatorics
  • Computer Science Applications
  • Computational Theory and Mathematics

Keywords

  • Nonlinear binary optimization
  • Pseudo-Boolean functions
  • Quadratic binary optimization
  • Reformulation methods

Fingerprint Dive into the research topics of 'Compact quadratizations for pseudo-Boolean functions'. Together they form a unique fingerprint.

  • Cite this