Systems | Information | Learning | Optimization

Chvátal rank in binary polynomial optimization

We consider the unconstrained 0-1 polynomial optimization problem where its hypergraph representation contains a beta-cycle. First, we show that almost all known cutting planes for this problem have Chvátal rank 1. We then exploit these inequalities to derive new cutting planes that generally have Chvátal rank 2. This novel class of valid inequalities subsume odd-cycle inequalities for binary quadratic optimization. Lastly, we give an indication of their theoretical power by showing that they provide the integer hull when the problem is represented by a cycle hypergraph.
June 20 @ 16:00
4:00 pm (1h)

Memorial Union, State Room

Silvia Di Gregorio