Quadratization of symmetric pseudo-Boolean functions

DOI10.1016/J.DAM.2016.01.001MaRDI QIDQ260013zbMATH OpenOpenAlexWikidataFDO

Authors Martin Anthony, Endre Boros, Aritanan Gruber, Yves Crama

Publication date 18 March 2016

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6535

zbMATH Keywords

nonlinear and quadratic binary optimizationreformulation methods for polynomialssymmetric (pseudo-)Boolean functions

Mathematics Subject Classification ID

Quadratic programming (90C20) Fuzzy sets and logic (in connection with information, communication, or circuits theory) (94D05) Boolean programming (90C09)

Abstract: A pseudo-Boolean function is a real-valued function $f(x)=f(x_1,x_2,ldots,x_n)$ of $n$ binary variables; that is, a mapping from ${0,1}^n$ to $mathbbR$. For a pseudo-Boolean function $f(x)$ on ${0,1}^n$, we say that $g(x,y)$ is a quadratization of $f$ if $g(x,y)$ is a quadratic polynomial depending on $x$ and on $m$ auxiliary binary variables $y_1,y_2,ldots,y_m$ such that $f(x)=ming(x,y):yin{0,1}^m$ for all $xin{0,1}^n$. By means of quadratizations, minimization of $f$ is reduced to minimization (over its extended set of variables) of the quadratic function $g(x,y)$. This is of some practical interest because minimization of quadratic functions has been thoroughly studied for the last few decades, and much progress has been made in solving such problems exactly or heuristically. A related paper cite{ABCG} initiated a systematic study of the minimum number of auxiliary $y$-variables required in a quadratization of an arbitrary function $f$ (a natural question, since the complexity of minimizing the quadratic function $g(x,y)$ depends, among other factors, on the number of binary variables). In this paper, we determine more precisely the number of auxiliary variables required by quadratizations of symmetric pseudo-Boolean functions $f(x)$, those functions whose value depends only on the Hamming weight of the input $x$ (the number of variables equal to $1$).

Recommendations

• Compact quadratizations for pseudo-Boolean functions
• A decomposition method for minimizing quadratic pseudo-Boolean functions
• Minimization of a quadratic pseudo-Boolean function
• scientific article; zbMATH DE number 1543344
• On pseudo-Boolean polynomials

Cites work

• scientific article; zbMATH DE number 5852793 (Why is no real title available?)
• scientific article; zbMATH DE number 446494 (Why is no real title available?)
• scientific article; zbMATH DE number 3473554 (Why is no real title available?)
• scientific article; zbMATH DE number 761425 (Why is no real title available?)
• scientific article; zbMATH DE number 3314813 (Why is no real title available?)
• Mixed integer nonlinear programming. Selected papers based on the presentations at the IMA workshop mixed-integer nonlinear optimization: Algorithmic advances and applications, Minneapolis, MN, USA, November 17--21, 2008
• Pseudo-Boolean optimization
• Quadratic reformulations of nonlinear binary optimization problems
• Size--Depth Tradeoffs for Threshold Circuits
• The threshold order of a Boolean function

Cited in

(11)

• Optimal quadratic reformulations of fourth degree pseudo-Boolean functions
• Solving unconstrained binary polynomial programs with limited reach: application to low autocorrelation binary sequences
• Quadratic reformulations of nonlinear binary optimization problems
• On the complexity of binary polynomial optimization over acyclic hypergraphs
• On the number of pseudo-Boolean metric functions
• A decomposition method for minimizing quadratic pseudo-Boolean functions
• Compact quadratizations for pseudo-Boolean functions
• Boolean convolution in the quaternionic setting
• Enhancing quantum annealing performance for the molecular similarity problem
• A semantic relatedness preserved subset extraction method for language corpora based on pseudo-Boolean optimization
• Efficient minimization of higher order submodular functions using monotonic Boolean functions

Describes a project that uses

Uses Software

• JBool

This page was built for publication: Quadratization of symmetric pseudo-Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q260013)