Reference : Quadratic reformulations of nonlinear binary optimization problems
Scientific journals : Article
Physical, chemical, mathematical & earth Sciences : Mathematics
Business & economic sciences : Quantitative methods in economics & management
Quadratic reformulations of nonlinear binary optimization problems
Anthony, Martin []
Boros, Endre []
Crama, Yves mailto [Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production >]
Gruber, Aritanan []
Mathematical Programming
Yes (verified by ORBi)
[en] nonlinear binary optimization ; quadratic binary optimization ; pseudo-Boolean functions ; reformulation methods
[en] Very large nonlinear unconstrained binary optimization problems arise in a broad array of applications. Several exact or heuristic techniques have proved quite successful for solving many of these problems when the objective function is a quadratic polynomial. However, no similarly efficient methods are available for the higher degree case. Since high degree objectives are becoming increasingly important in certain application areas, such as computer vision, various techniques have been recently developed to reduce the general case to the quadratic one, at the cost of increasing the number of variables. In this paper we initiate a systematic study of these quadratization approaches. We provide tight lower and upper bounds on the number of auxiliary variables needed in the worst-case for general objective functions, for bounded-degree functions, and for a restricted class of quadratizations. Our upper bounds are constructive, thus yielding new quadratization procedures. Finally, we completely characterize all ``minimal'' quadratizations of negative monomials.
Politique Scientifique Fédérale (Belgique) = Belgian Federal Science Policy
PAI P7/36 Comex

File(s) associated to this reference

Fulltext file(s):

Open access
Quadratization_Revision April2016.pdfAuthor preprint374.78 kBView/Open

Bookmark and Share SFX Query

All documents in ORBi are protected by a user license.