Simple odd β-cycle inequalities for binary polynomial optimisation

EI-ERIM-OR seminar
Speaker
Matthias Walter
Date
Friday 2 Dec 2022, 12:00 - 13:00
Type
Seminar
Spoken Language
English
Room
C2-3
Building
Theil Building
Add to calendar

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.

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.

    Matthias Walter

    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

    See also

    Benders Decomposition for Robust Tactical Crew Scheduling

    Bart van Rossum (Erasmus School of Economics)
    Train on tracks

    FinEML Conference 2024 at USI Lugano

    Financial Econometrics meets Machine Learning
    University USI Lugano

    Compare @count study programme

    • @title

      • Duration: @duration
    Compare study programmes