The multilinear polytope arises naturally in binary polynomial optimisation 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.
- Speaker
- Date
- Friday 2 Dec 2022, 12:00 - 13:00
- Type
- Seminar
- Spoken Language
- English
- Room
- C2-3
- Building
- Theil Building
Moreover, they describe a separation algorithm in case the instance is a cycle hypergraph. In the talk I will introduce a weaker version, called simple odd β-cycle inequalities, and illustrate 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.
The talk is rounded up with computational results for the implementation in SCIP. This is joint work with Alberto Del Pia.
About Matthias Walter
Matthias Walter is an assistant professor at the University of Twente.
He works on solving techniques for mixed-integer programs (MIPs) on the practical side (branch-and-cut, branch-and-price) as well as polyhedral combinatorics on the theoretical side.
Organisers
Michal Mankowski and Olga Kuryatnikova
More information
Secretariat Econometrics
Phone: +31 (0)10 408 12 59/ 12 64
Email: eb-secr@ese.eur.nl
