Synergies for Exact Solutions to the Maximum Cut Problem

• Applicant: Dr. Sven Mallach
• Subject Area: Theoretical Computer Science
• Term: since 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 537033028

We propose a synergetic approach to exactly solve the Maximum Cut Problem and the Unconstrained Binary Quadratic Optimization Problem that integrates and commonly enhances so far separately developed state-of-the-art techniques based on Integer Linear Programming (ILP) and Semidefinite Programming (SDP) in a novel way. Thereby, the synergetic interplay between our methods will be (at least) two-fold. On the one hand, we will combine for the first time ILP- and SDP-based algorithms within a common divide-and-conquer framework that allows the solution of problem instances out of reach for each of the standalone solvers. Moreover, we will also meaningfully combine each of the techniques with the respective other one in terms of the preprocessing of difficult instances. On the other hand, we will commonly enhance our ILP- and SDP-based algorithms methodologically. A brief collection of our planned developments in this respect includes algorithmic innovations for sophisticated core solver components such as separation algorithms and branching heuristics, a thorough analysis and extension of preprocessing techniques, and further algorithmic improvements derived from a structural instance and solver performance analyses that is embedded into an algorithm engineering cycle. While we focus on enhancing current state-of-the-art methods, we will also contribute an exact solver that employs only subroutines of free and academic rather than commercial software libraries, especially to foster further research developments. Apart from that, we will also enhance the current state-of-the-art services to solve Spin Glass instances by tailored derivatives of our extended methods. Furthermore, to serve the scientific community, but also to support our work program, we compose a rich library of carefully selected problem instances that will also offer meta data useful for research purposes and provide the instances in different file formats. Last but not least, we will obtain the first (ultimately fair) setting where an experimental comparison of ILP and SDP approaches based on the same preprocessing workflow is possible.

• DFG Programme: Research Grants
• International Connection: Austria
• Partner Organisation: Fonds zur Förderung der wissenschaftlichen Forschung (FWF)
• Cooperation Partner: Professorin Dr. Angelika Wiegele