Groupe d’études et de recherche en analyse des décisions

# Exact separation of $$k$$-projection polytope constraints

## Elspeth Adams et Miguel F. Anjos

A critical step of any cutting plane algorithm is to find valid inequalities, or cuts, that improve the current relaxation of the integer-constrained problem. The maximally violated valid inequality problem aims to find the most violated inequality from a given family of cuts. $$k$$-projection polytope constraints are a family of cuts that are based on an inner description of the cut polytope of size $$k$$ and are applied to $$k\times k$$ principal minors of a semidefinite optimization relaxation. We propose a bilevel second order cone optimization approach to solve the maximally violated $$k$$ projection polytope constraint problem. We reformulate the bilevel problem as a single-level mixed binary second order cone optimization problem that can be solved using off-the-shelf conic optimization software. Additionally we present two methods for improving the computational performance of our approach, namely lexicographical ordering and a reformulation with fewer binary variables. All of the proposed formulations are exact. Preliminary results show the computational time and number of branch-and-bound nodes required to solve small instances in the context of the max-cut problem.

, 17 pages