Quadratic reformulations of nonlinear binary optimization problems

Martin Anthony, Endre Boros, Yves Crama, Aritanan Gruber

Research output: Contribution to journalArticle

7 Citations (Scopus)

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 languageEnglish (US)
Pages (from-to)115-144
Number of pages30
JournalMathematical Programming
Volume162
Issue number1-2
DOIs
StatePublished - Mar 1 2017

Fingerprint

Auxiliary Variables
Reformulation
Objective function
Binary
Optimization Problem
Quadratic Polynomial
Computer Vision
Upper and Lower Bounds
Heuristics
Upper bound
Computer vision
Polynomials
Class

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Nonlinear binary optimization
  • Pseudo-Boolean functions
  • Quadratic binary optimization
  • Reformulation methods

Cite this

Anthony, Martin ; Boros, Endre ; Crama, Yves ; Gruber, Aritanan. / Quadratic reformulations of nonlinear binary optimization problems. In: Mathematical Programming. 2017 ; Vol. 162, No. 1-2. pp. 115-144.
@article{428bbe22457c487d9e092ef0f42595ab,
title = "Quadratic reformulations of nonlinear binary optimization problems",
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.",
keywords = "Nonlinear binary optimization, Pseudo-Boolean functions, Quadratic binary optimization, Reformulation methods",
author = "Martin Anthony and Endre Boros and Yves Crama and Aritanan Gruber",
year = "2017",
month = "3",
day = "1",
doi = "10.1007/s10107-016-1032-4",
language = "English (US)",
volume = "162",
pages = "115--144",
journal = "Mathematical Programming",
issn = "0025-5610",
publisher = "Springer-Verlag GmbH and Co. KG",
number = "1-2",

}

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 journalArticle

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 -