Quadratization of symmetric pseudo-Boolean functions

详细信息    查看全文

• 作者：Martin Anthony^a ; ^{m.anthony@lse.ac.uk" class="auth_mail" title="E-mail the corresponding author} ; Endre Boros^b ; ^{endre.boros@rutgers.edu" class="auth_mail" title="E-mail the corresponding author} ; Yves Crama^c ; ^{yves.crama@ulg.ac.be" class="auth_mail" title="E-mail the corresponding author} ; Aritanan Gruber^d ; ^{gruber@ime.usp.br" class="auth_mail" title="E-mail the corresponding author}
• 关键词：Symmetric (pseudo-)Boolean functions ; Nonlinear and quadratic binary optimization ; Reformulation methods for polynomials
• 刊名：Discrete Applied Mathematics
• 出版年：2016
• 出版时间：20 April 2016
• 年：2016
• 卷：203
• 期：Complete
• 页码：1-12
• 全文大小：401 K

文摘

A pseudo-Boolean function   is a real-valued function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si1.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=bddf5f2a9b1d68e62c65ed83c219cde6" title="Click to view the MathML source">f(x)=f(x₁,x₂,…,x_n)class="mathContainer hidden">class="mathCode">$f\left(x\right)=f(x_1,x_2,\dots ,x_n)$ of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si2.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=5a62bc19ee28eb63816a3c9ed84e4cc7" title="Click to view the MathML source">nclass="mathContainer hidden">class="mathCode">$n$ binary variables, that is, a mapping from class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si3.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=e94a121cfd2e7b77428bc2fdfb5ac0fc" title="Click to view the MathML source">{0,1}ⁿclass="mathContainer hidden">class="mathCode">${\{0,1\}}^n$ to class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si4.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=109931bb1dc261dcbe819252f3efc463" title="Click to view the MathML source">Rclass="mathContainer hidden">class="mathCode">$\mathbb{R}$. For a pseudo-Boolean function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si5.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=a574c1fd1534e3aed056859473e0adfa" title="Click to view the MathML source">f(x)class="mathContainer hidden">class="mathCode">$f\left(x\right)$ on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si3.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=e94a121cfd2e7b77428bc2fdfb5ac0fc" title="Click to view the MathML source">{0,1}ⁿclass="mathContainer hidden">class="mathCode">${\{0,1\}}^n$, we say that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si7.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=ca91c3ced9956e1c6f11b0fd60a9acf1" title="Click to view the MathML source">g(x,y)class="mathContainer hidden">class="mathCode">$g(x,y)$ is a quadratization   of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si8.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=59e87b5b06cc2c60142f40be22dc3ce7" title="Click to view the MathML source">fclass="mathContainer hidden">class="mathCode">$f$ if class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si7.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=ca91c3ced9956e1c6f11b0fd60a9acf1" title="Click to view the MathML source">g(x,y)class="mathContainer hidden">class="mathCode">$g(x,y)$ is a quadratic polynomial depending on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si10.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=469d05a841a9bdd642cbee06037a0ff8" title="Click to view the MathML source">xclass="mathContainer hidden">class="mathCode">$x$ and on class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si11.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=dd2eb8a7ff451e55434685db7fb98670" title="Click to view the MathML source">mclass="mathContainer hidden">class="mathCode">$m$auxiliary   binary variables class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si12.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=eea19a8fa1c134439442dfabe6371f13" title="Click to view the MathML source">y₁,y₂,…,y_mclass="mathContainer hidden">class="mathCode">$y_1,y_2,\dots ,y_m$ such that class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si13.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=5d2a34fd0b713b5688d75d4937584ecd" title="Click to view the MathML source">f(x)=min{g(x,y):y∈{0,1}^m}class="mathContainer hidden">class="mathCode">$f\left(x\right)=min\{g(x,y):y\in {\{0,1\}}^m\}$ for all class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si14.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=7427ff47a553f44388de25cbe9b2e3aa" title="Click to view the MathML source">x∈{0,1}ⁿclass="mathContainer hidden">class="mathCode">$x\in {\{0,1\}}^n$. By means of quadratizations, minimization of class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si8.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=59e87b5b06cc2c60142f40be22dc3ce7" title="Click to view the MathML source">fclass="mathContainer hidden">class="mathCode">$f$ is reduced to minimization (over its extended set of variables) of the quadratic function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si7.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=ca91c3ced9956e1c6f11b0fd60a9acf1" title="Click to view the MathML source">g(x,y)class="mathContainer hidden">class="mathCode">$g(x,y)$. This is of 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 by Anthony et al. (2015) initiated a systematic study of the minimum number of auxiliary class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si17.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=9fb597cf47537a4ac4f305efe44094e3" title="Click to view the MathML source">yclass="mathContainer hidden">class="mathCode">$y$-variables required in a quadratization of an arbitrary function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si8.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=59e87b5b06cc2c60142f40be22dc3ce7" title="Click to view the MathML source">fclass="mathContainer hidden">class="mathCode">$f$ (a natural question, since the complexity of minimizing the quadratic function class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si7.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=ca91c3ced9956e1c6f11b0fd60a9acf1" title="Click to view the MathML source">g(x,y)class="mathContainer hidden">class="mathCode">$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 class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si5.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=a574c1fd1534e3aed056859473e0adfa" title="Click to view the MathML source">f(x)class="mathContainer hidden">class="mathCode">$f\left(x\right)$, those functions whose value depends only on the Hamming weight of the input class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0166218X16000020&_mathId=si10.gif&_user=111111111&_pii=S0166218X16000020&_rdoc=1&_issn=0166218X&md5=469d05a841a9bdd642cbee06037a0ff8" title="Click to view the MathML source">xclass="mathContainer hidden">class="mathCode">$x$ (the number of variables equal to 1).