{"ID":2865968,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2509.21064","arxiv_id":"2509.21064","title":"Smoothing Binary Optimization: A Primal-Dual Perspective","abstract":"Binary optimization is a powerful tool for modeling combinatorial problems, yet scalable and theoretically sound solution methods remain elusive. Conventional solvers often rely on heuristic strategies with weak guarantees or struggle with large-scale instances. In this work, we introduce a novel primal-dual framework that reformulates unconstrained binary optimization as a continuous minimax problem, satisfying a strong max-min property. This reformulation effectively smooths the discrete problem, enabling the application of efficient gradient-based methods. We propose a simultaneous gradient descent-ascent algorithm that is highly parallelizable on GPUs and provably converges to a near-optimal solution in linear time. Extensive experiments on large-scale problems--including Max-Cut, MaxSAT, and Maximum Independent Set with up to 50,000 variables--demonstrate that our method identifies high-quality solutions within seconds, significantly outperforming state-of-the-art alternatives.","short_abstract":"Binary optimization is a powerful tool for modeling combinatorial problems, yet scalable and theoretically sound solution methods remain elusive. Conventional solvers often rely on heuristic strategies with weak guarantees or struggle with large-scale instances. In this work, we introduce a novel primal-dual framework...","url_abs":"https://arxiv.org/abs/2509.21064","url_pdf":"https://arxiv.org/pdf/2509.21064v2","authors":"[\"Wenbo Liu\",\"Akang Wang\",\"Dun Ma\",\"Hongyi Jiang\",\"Jianghua Wu\",\"Wenguo Yang\"]","published":"2025-09-25T12:14:14Z","proceeding":"math.OC","tasks":"[\"math.OC\"]","methods":"[]","has_code":false}