## Abstract

We consider the multilinear polytope which arises naturally in binary polynomial optimization. Del Pia and Di Gregorio introduced the class of odd β

-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 β

-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. Finally, we report about computational results of our prototype implementation. The simple odd β

-cycle inequalities sometimes help to close more of the integrality gap in the experiments; however, the preliminary implementation has substantial computational cost, suggesting room for improvement in the separation algorithm.

-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 β

-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. Finally, we report about computational results of our prototype implementation. The simple odd β

-cycle inequalities sometimes help to close more of the integrality gap in the experiments; however, the preliminary implementation has substantial computational cost, suggesting room for improvement in the separation algorithm.

Original language | English |
---|---|

Number of pages | 36 |

Journal | Mathematical programming |

DOIs | |

Publication status | Published - 7 Jul 2023 |

## Keywords

- UT-Hybrid-D