Optimization Online


Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

Christopher Hojny (c.hojny***at***tue.nl)
Marc E. Pfetsch (pfetsch***at***opt.tu-darmstadt.de)
Matthias Walter (m.walter***at***utwente.nl)

Abstract: Polynomial optimization problems over binary variables can be expressed as integer programs using a linearization with extra monomials in addition to those arising in the given polynomial. We characterize when such a linearization yields an integral relaxation polytope, generalizing work by Del Pia and Khajavirad (SIAM Journal on Optimization, 2018) and Buchheim, Crama and Rodríguez-Heck (European Journal of Operations Research, 2019). We also present an algorithm that finds these extra monomials for a given polynomial to yield an integral relaxation polytope or determines that no such set of extra monomials exists. In the former case, our approach yields an algorithm to solve the given polynomial optimization problem as a compact LP, and we complement this with a purely combinatorial algorithm.

Keywords: polynomial optimization, linearization, integer linear programming

Category 1: Integer Programming ((Mixed) Integer Nonlinear Programming )

Category 2: Combinatorial Optimization (Polyhedra )


Download: [PDF]

Entry Submitted: 11/15/2019
Entry Accepted: 11/15/2019
Entry Last Modified: 05/14/2020

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society