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


Exact separation of \(k\)-projection polytope constraints


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