Quadratic reformulations of nonlinear binary optimization problems

• 成果类型: Article
• 署名作者: Anthony, Martin; Boros, Endre; Crama, Yves; Gruber, Aritanan
• 署名单位: University of London; London School Economics & Political Science; Rutgers University System; Rutgers University New Brunswick; Rutgers University System; Rutgers University New Brunswick; University of Liege; Universidade de Sao Paulo
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-016-1032-4
• 发表日期: 2017
• 页码: 115-144
• 关键词: generalized roof duality; local search heuristics; graph cuts; energy minimization; unions; qubo

摘要

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.