Primal-Dual Approaches and Theory for Binary Optimization

Binary optimization, where variables take 0-1 values, is central to network design,scheduling, circuit layout, and machine learning. However, existing solvers face a persistent trade-off. Exact methods provide guarantees yet scale poorly, while heuristics scale but lack certificates. Our recent work shows that many unconstrained binary optimization problems admit a principled primal‑dual minimax reformulation. We then developed a simultaneous gradient descent-ascent (GDA) scheme that converges in linear time to epsilon-binary solutions. This approach is well-suited for GPU deployment, achieving state-of-the-art quality within seconds on benchmarks including Max-Cut, Max-SAT, and Maximum Independent Set with up to 50,000 variables.This project develops the mathematical foundations and scalable algorithms for a gap-certified framework for constrained binary optimization. We will extend the primal-dual formulation and GDA method to handle convex constraints, including budgets, norm bounds, and semidefinite structures. This is achieved via a semi-boxed Lagrangian formulation whose dual variables evolve to enforce both feasibility and integrality. We will derive tight dual lower bounds by combining diagonal shifting (to convexify objectives) with convex envelopes. By analyzing when each approach dominates, we will provide strong certified optimality gaps. We will also convert the resulting primal-dual structure into effective cut families that integrate with branch-and-cut algorithms,yielding exact or epsilon-optimal solutions. Our theoretical agenda includes iteration complexity guarantees for reaching near-feasible, near-binary points by GDA. We will also establish structural dominance conditions determining when each bounding technique provides the tightest bounds. Finally, we will develop cut generation policies that combine concavity cuts with integrality cuts through parallel computation to ensure measurable gap decay in branch-and-cut.The project will deliver significant advances in both theory and practice. We will establish a unified primal-dual scheme for constrained binary optimization, provide rigorous analysis of hybrid bounding techniques with provable dominance regimes, and develop concavification-based cutting planes that accelerate branch-and-cutalgorithms. Our GPU-accelerated solver will return high-quality solutions together with certified optimality gaps on instances far beyond the reach of classical exact methods,while retaining branch-and-cut integration for applications requiring exact solutions.These tools will enable faster, trustworthy optimization for large-scale discrete modeling, with theoretical guarantees appropriate for scientific and industrial deployment.By blending continuous optimization, combinatorial structure, and modern hardware, this project aims to make reliable large-scale binary optimization both mathematically rigorous and practically accessible.