Synergies for Exact Solutions to the Maximum Cut Problem

A wide range of real-world challenges in fields like physics, data science, logistics, telecommunications, and finance can be modeled as binary quadratic optimization or equivalent max-cut problems. The term "binary" refers to variables restricted to values of zero or one, forming the foundation of these mathematical models. While highly relevant, large-scale instances of such problems are beyond the capabilities of existing off-the-shelf tools, creating a strong demand for advanced solvers. State-of-the-art techniques for tackling these problems rely on either Linear Programming (LP) or Semidefinite Programming (SDP). This project proposes a synergetic approach that integrates and enhances these independently developed methods, offering a novel solution for exactly solving complex binary quadratic problems. Our contributions include developing an exact solver that utilizes free and academic software libraries wherever feasible, combined with advanced algorithmic enhancements of existing methods. This solver will address general problem settings and include specialized adaptations for domain-specific challenges, such as Spin Glass instances from physics. Additionally, the project will combine solvers with common analyses, preprocessing, and decomposition modules within a unified framework to be offered as a web-based service for the scientific community. For the first time, LP- and SDP-based solution techniques will be integrated, unlocking new synergies and mutual enhancements. The framework will also feature a large-scale, diverse instance library to support analytical experiments and provide a robust benchmark set. This collaboration brings together leading experts from complementary fields. Researchers from the University of Bonn contribute expertise in linear programming approaches for complex optimization problems, while experts from Alpen-Adria-Universität Klagenfurt are recognized for their pioneering work in SDP algorithms and academic software. Together, they aim to deliver transformative tools for solving large-scale optimization problems, advancing both research and practical applications.