Abstract
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 by introducing additional auxiliary 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.
| Original language | English (US) |
|---|---|
| Pages (from-to) | 115-144 |
| Number of pages | 30 |
| Journal | Mathematical Programming |
| Volume | 162 |
| Issue number | 1-2 |
| DOIs | |
| State | Published - Mar 1 2017 |
Fingerprint
All Science Journal Classification (ASJC) codes
- Software
- Mathematics(all)
Keywords
- Nonlinear binary optimization
- Pseudo-Boolean functions
- Quadratic binary optimization
- Reformulation methods
Cite this
}
Quadratic reformulations of nonlinear binary optimization problems. / Anthony, Martin; Boros, Endre; Crama, Yves; Gruber, Aritanan.
In: Mathematical Programming, Vol. 162, No. 1-2, 01.03.2017, p. 115-144.Research output: Contribution to journal › Article
TY - JOUR
T1 - Quadratic reformulations of nonlinear binary optimization problems
AU - Anthony, Martin
AU - Boros, Endre
AU - Crama, Yves
AU - Gruber, Aritanan
PY - 2017/3/1
Y1 - 2017/3/1
N2 - 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 by introducing additional auxiliary 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.
AB - 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 by introducing additional auxiliary 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.
KW - Nonlinear binary optimization
KW - Pseudo-Boolean functions
KW - Quadratic binary optimization
KW - Reformulation methods
UR - http://www.scopus.com/inward/record.url?scp=84973103255&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84973103255&partnerID=8YFLogxK
U2 - 10.1007/s10107-016-1032-4
DO - 10.1007/s10107-016-1032-4
M3 - Article
AN - SCOPUS:84973103255
VL - 162
SP - 115
EP - 144
JO - Mathematical Programming
JF - Mathematical Programming
SN - 0025-5610
IS - 1-2
ER -