Exact Maximum Cut and Binary Quadratic Programming
I am currently acting as a principal investigator in a research project that -- seen as a whole -- is
joint work with Jonas Charfreitag,
Michael Jünger, Petra Mutzel,
and Angelika Wiegele.
In different branches of this project, we are integrating solution techniques from polyhedral combinatorics, integer linear programming, and semidefinite programming as well as effective preprocessing and modeling techniques in order to obtain a fast exact solver for general Maximum Cut and Binary Quadratic Optimization instances.
An early yet visible outcome of this project is the web-based solver service McSparse for sparse problem instances, as well as an accompanying publication.
Previous research constituting one of the many pillars of this project is about facet-only separation algorithms for the odd cycle inequalities associated to the cut polypope, i.e., the convex hull of (edge) incidence vectors corresponding to a bi-partitioning of a graph.