Quadratization and convexification in polynomial binary optimization

Yves Crama (), Sourour Elloumi (), Amélie Lambert () and Elisabeth Rodríguez-Heck ()
Additional contact information
Yves Crama: HEC-Management School of the University of Liège
Sourour Elloumi: ENSTA Paris, Institut Polytechnique de Paris
Amélie Lambert: CEDRIC-Cnam
Elisabeth Rodríguez-Heck: RWTH Aachen University

Journal of Combinatorial Optimization, 2025, vol. 50, issue 3, No 6, 47 pages

Abstract: Abstract In this paper, we discuss several reformulations and solution approaches for the problem of minimizing a polynomial in binary variables (P). We review and integrate different literature streams to describe a methodology consisting of three distinct phases, together with several possible variants for each phase. The first phase determines a recursive decomposition of each monomial of interest into pairs of submonomials, down to the initial variables. The decomposition gives rise to a so-called quadratization scheme. The second phase builds a quadratic reformulation of (P) from a given quadratization scheme, by associating a new auxiliary variable with each submonomial that appears in the scheme. A quadratic reformulation of (P) is obtained by enforcing relations between the auxiliary variables and the monomials that they represent, either through linear constraints or through penalty terms in the objective function. The resulting quadratic problem (QP) is non-convex in general and is still difficult to solve. At this stage we introduce the third phase of the resolution process, which consists in convexifying (QP). We consider different types of convexification methods, including complete linearization or quadratic convex reformulations. Mathematical properties of the different phases are formally established and some relations between them are clarified. Finally, we present some experimental results which illustrate the discussion and which support the practical relevance of quadratic reformulation methods.

Keywords: Nonlinear binary optimization; Quadratic binary optimization; Reformulation; Convexification (search for similar items in EconPapers)
Date: 2025
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-025-01334-y Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:50:y:2025:i:3:d:10.1007_s10878-025-01334-y

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-025-01334-y

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().