Article (Scientific journals)
Quadratic reformulations of nonlinear binary optimization problems
Anthony, Martin; Boros, Endre; Crama, Yves et al.
2017In Mathematical Programming, 162, p. 115-144
Peer Reviewed verified by ORBi
 

Files


Full Text
Quadratization_Revision April2016.pdf
Author preprint (383.77 kB)
Download

All documents in ORBi are protected by a user license.

Send to



Details



Keywords :
nonlinear binary optimization; quadratic binary optimization; pseudo-Boolean functions; reformulation methods
Abstract :
[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.
Research center :
QuantOM HEC-ULiège
Disciplines :
Mathematics
Quantitative methods in economics & management
Author, co-author :
Anthony, Martin
Boros, Endre
Crama, Yves  ;  Université de Liège > HEC-Ecole de gestion : UER > Recherche opérationnelle et gestion de la production
Gruber, Aritanan
Language :
English
Title :
Quadratic reformulations of nonlinear binary optimization problems
Publication date :
2017
Journal title :
Mathematical Programming
ISSN :
0025-5610
eISSN :
1436-4646
Publisher :
Springer
Volume :
162
Pages :
115-144
Peer reviewed :
Peer Reviewed verified by ORBi
Name of the research project :
PAI P7/36 Comex
Funders :
BELSPO - SPP Politique scientifique - Service Public Fédéral de Programmation Politique scientifique
Available on ORBi :
since 04 August 2015

Statistics


Number of views
256 (22 by ULiège)
Number of downloads
328 (4 by ULiège)

Scopus citations®
 
39
Scopus citations®
without self-citations
36
OpenCitations
 
26

Bibliography


Similar publications



Contact ORBi