Reference : Compact quadratizations for pseudo-Boolean functions
E-prints/Working papers : First made available on ORBi
Physical, chemical, mathematical & earth Sciences : Mathematics
Business & economic sciences : Quantitative methods in economics & management
http://hdl.handle.net/2268/229971
Compact quadratizations for pseudo-Boolean functions
English
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 mailto [Université de Liège - ULiège > HEC Liège : UER > Recherche opérationnelle et gestion de la production >]
2018
No
[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
Researchers
http://hdl.handle.net/2268/229971

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
Open access
article_quadrat_bounds ORBI.pdfAuthor preprint328.52 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.