Simple odd $β$-cycle inequalities for binary polynomial optimization

Alberto Del Pia, Matthias Walter

Research output: Working paperProfessional

2 Downloads (Pure)

Abstract

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd $\beta$-cycle inequalities valid for this polytope, showed that these generally have Chvátal rank 2 with respect to the standard relaxation and that, together with flower inequalities, they yield a perfect formulation for cycle hypergraph instances. Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. We introduce a weaker version, called simple odd $\beta$-cycle inequalities, for which we establish a strongly polynomial-time separation algorithm for arbitrary instances. These inequalities still have Chvátal rank 2 in general and still suffice to describe the multilinear polytope for cycle hypergraphs.
Original languageEnglish
Publication statusPublished - 8 Nov 2021

Keywords

  • cs.DM
  • math.CO
  • 90C57
  • G.2.0

Fingerprint

Dive into the research topics of 'Simple odd $β$-cycle inequalities for binary polynomial optimization'. Together they form a unique fingerprint.

Cite this