Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials

Christopher Hojny, Marc E. Pfetsch, Matthias Walter

    Research output: Working paper

    87 Downloads (Pure)

    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). 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.
    Original languageEnglish
    PublisherArXiv.org
    Number of pages27
    Publication statusPublished - 15 Nov 2019

    Publication series

    NameArxiv.org
    PublisherCornell University

    Keywords

    • cs.DM
    • math.CO
    • 90C57
    • G.1.6; G.2.1

    Fingerprint

    Dive into the research topics of 'Integrality of Linearizations of Polynomials over Binary Variables using Additional Monomials'. Together they form a unique fingerprint.

    Cite this