Reference : Compact quadratizations for pseudo-Boolean functions
Scientific journals : Article
Business & economic sciences : Quantitative methods in economics & management
Physical, chemical, mathematical & earth Sciences : Mathematics
Compact quadratizations for pseudo-Boolean functions
Boros, Endre [> >]
Crama, Yves mailto [Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
Rodriguez Heck, Elisabeth [RWTH Aachen University > > > >]
Journal of Combinatorial Optimization
Kluwer Academic Publishers
Yes (verified by ORBi)
[en] nonlinear binary optimization ; quadratic binary optimization ; pseudo-Boolean functions ; reformulation methods
[en] 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.
QuantOM - HEC

File(s) associated to this reference

Fulltext file(s):

Open access
article_quadrat_bounds ORBI.pdfAuthor preprint328.52 kBView/Open
Restricted access
Boros2020_Article_CompactQuadratizationsForPseud.pdfPublisher postprint396.51 kBRequest copy

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.