Integer Semidefinite Programming - a New Perspective
Presenter
March 2, 2023
Abstract
Integer semidefinite programming can be viewed as a generalization of integer programming where the vector variables are replaced by positive semidefinite integer matrix variables. The combination of positive semidefiniteness and integrality allows to formulate various optimization problems as integer semidefinite programs (ISDPs). Nevertheless, ISDPs have received attention only very recently.
In this talk we show how to extend the Chv\'atal-Gomory (CG) cutting-plane procedure to ISDPs. We also show how to exploit CG cuts in a branch-and-cut framework for ISDPs.
Finally, we demonstrate the practical strength of the CG cuts in our branch-and-cut algorithm. Our results provide a new perspective on ISDPs.