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
http://hdl.handle.net/2268/184526
Quadratic reformulations of nonlinear binary optimization problems
English
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 []
2017
Mathematical Programming
Springer
162
115-144
Yes (verified by ORBi)
International
0025-5610
1436-4646
[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.
QuantOM HEC-ULg
Politique Scientifique Fédérale (Belgique) = Belgian Federal Science Policy
PAI P7/36 Comex
Researchers
http://hdl.handle.net/2268/184526
10.1007/s10107-016-1032-4

File(s) associated to this reference

Fulltext file(s):

FileCommentaryVersionSizeAccess
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.