Quadratizations of symmetric pseudo-boolean functions: Sub-linear bounds on the number of auxiliary variables

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

Research output: Contribution to conferencePaper

2 Scopus citations

Abstract

The problem of minimizing a pseudo-Boolean function with no additional constraints arises in a variety of applications. A quadratization is a quadratic reformulation of the nonlinear problem obtained by introducing a set of auxiliary binary variables which can be optimized using quadratic optimization techniques. Using the well-known result that a pseudo-Boolean function can be uniquely expressed as a multilinear polynomial, any pseudo-Boolean function can be quadratized by providing a quadratization for negative monomials and one for positive monomials. A desirable property for a quadratization is to introduce small number of auxiliary variables. For the case of negative monomials there exists a quadratization using a single auxiliary variable which is, in addition, submodular. However, much less is known for positive monomials. The best lower bound on the number of variables required by a quadratization in the literature is (Formula presented.). We present here new quadratizations of the positive monomial that significantly improve this lower bound decreasing it to a logarithmic bound. This lower bound is derived from a more general result, stating that a quadratization with a logarithmic number of variables can be defined for exact k out-of-n functions, which is a more general class of symmetric functions. Moreover, for exact k-out-of-n functions we also prove that a logarithmic number of variables is necessary when requiring certain symmetry conditions to the quadratization. Finally, we provide quadratizations for general symmetric functions using O(n) auxiliary variables. This upper bound nicely matches a lower bound of Ω(n) variables that was recently introduced.

Original languageEnglish (US)
StatePublished - Jan 1 2018
Event2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018 - Fort Lauderdale, United States
Duration: Jan 3 2018Jan 5 2018

Conference

Conference2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018
CountryUnited States
CityFort Lauderdale
Period1/3/181/5/18

    Fingerprint

All Science Journal Classification (ASJC) codes

  • Applied Mathematics
  • Artificial Intelligence

Cite this

Boros, E., Crama, Y., & Rodríguez-Heck, E. (2018). Quadratizations of symmetric pseudo-boolean functions: Sub-linear bounds on the number of auxiliary variables. Paper presented at 2018 International Symposium on Artificial Intelligence and Mathematics, ISAIM 2018, Fort Lauderdale, United States.