## 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.

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

Title of host publication | Integer Programming and Combinatorial Optimization. IPCO 2022 |

Subtitle of host publication | 23rd International Conference, IPCO 2022, Eindhoven, The Netherlands, June 27–29, 2022, Proceedings |

Editors | Karen Aardal, Laura Sanità |

Place of Publication | Cham |

Publisher | Springer |

Pages | 181–194 |

Number of pages | 14 |

ISBN (Electronic) | 978-3-031-06901-7 |

ISBN (Print) | 978-3-031-06900-0 |

DOIs | |

Publication status | Published - 2022 |

Event | 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 - Eindhoven, Netherlands Duration: 27 Jun 2022 → 29 Jun 2022 Conference number: 23 |

### Publication series

Name | Lecture Notes in Computer Science |
---|---|

Publisher | Springer |

Volume | 13265 |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 23rd International Conference on Integer Programming and Combinatorial Optimization, IPCO 2022 |
---|---|

Abbreviated title | IPCO |

Country/Territory | Netherlands |

City | Eindhoven |

Period | 27/06/22 → 29/06/22 |

## Keywords

- Binary polynomial optimization
- Cutting planes
- Separation algorithm
- 22/2 OA procedure