Smoothing Binary Optimization: A Primal-Dual Perspective
Wenbo Liu, Akang Wang, Dun Ma, Hongyi Jiang, Jianghua Wu, Wenguo Yang · 2025
Read Smoothing Binary Optimization: A Primal-Dual Perspective by Wenbo Liu, Akang Wang, Dun Ma, Hongyi Jiang, Jianghua Wu, Wenguo Yang (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-21064.txt.
Introduction
Many practical choices are yes-or-no, yet the resulting binary optimization problems are hard to solve at scale. Wenbo Liu and five co-authors attack them from a primal-dual angle in a 2025 paper. Their framework recasts an unconstrained binary problem as a continuous minimax problem.
The reformulation has a strong max-min property, meaning the two sides of the game meet cleanly. Smoothing the discrete problem this way lets gradient methods take over. The authors design a simultaneous gradient descent-ascent algorithm that parallelizes well on GPUs. They prove it reaches a near-optimal solution in linear time. Experiments on large instances back the claims, offering an alternative to heuristic solvers with weak guarantees.
Catalog record
| CREATOR | Wenbo Liu, Akang Wang, Dun Ma, Hongyi Jiang, Jianghua Wu, Wenguo Yang |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 59 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-21064
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Smoothing Binary Optimization: A Primal-Dual Perspective Wenbo Liu, Akang Wang, Dun Ma, Hongyi Jiang, Jianghua Wu, Wenguo Yang 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. 1 Introduction In this work, we consider the following binary optimization problem: \displaystyle\underset{{\bm{x}}\in\{0,1\}^{n}}{\min}\;F({\bm{x}}), (1) where {\bm{x}} denotes a binary variable of dimension n and F:\{0,1\}^{n}\rightarrow\mathbb{R} represents an arbitrary real-valued function defined on the binary domain. Problem ( 1 ) serves as a general model for a wide range of combinatorial optimization problems. A prominent special case is the quadratic unconstrained binary optimization (QUBO), which is inherently equivalent to the Max-Cut problem and capable of characterizing all of the Karp’s 21 \mathcal{NP} -complete problems ( Lucas 2014 ) . Moreover, integer linear programs can be approximately transformed into QUBO by appropriately penalizing the constraints via quadratic terms ( Alessandroni et al. 2025 ) . Other classic problems such as maximum satisfiability (MaxSAT) ( Bacchus et al. 2021 ) are also encompassed within this framework. Exact methods for binary optimization typically rely on branch-and-bound frameworks, integrated with various relaxation techniques such as the linear programming-based relaxations ( Barahona et al. 1989 ) and the semi-definite relaxations ( Poljak & Rendl 1995 ) . Recent advances have further enhanced these methods through sophisticated problem reduction techniques and accelerated cutting plane separation ( Rehfeldt et al. 2023 ) . However, the inherent \mathcal{NP} -hardness fundamentally limits the scalability of exact approaches, which generally remain practical only for instances involving up to a few hundred variables. Given the limitations of exact methods, research has shifted toward heuristics for large-scale binary optimization. Traditional CPU-based methods involving customized tabu search ( Palubeckis 2006 ; Wang et al. 2013 ) , simulated annealing ( Bertsimas & Tsitsiklis 1993 ) and genetic algorithms ( Merz & Freisleben 1999 ) , rely on well-crafted search mechanisms to iteratively explore the solution space. However, their performance is often constrained by sequential execution. Recent hardware progress has enabled significant improvements through GPU-acceleration, and conventional heuristics have benefited. For instance, ABS2 ( Nakano et al. 2023 ) integrates multiple search strategies and genetic operations executed in parallel on GPUs, while FEM ( Shen et al. 2025 ) introduces the simulated annealing method from a continuous view and optimized via GPU implementations. Beyond classical computing approaches, quantum annealing on specialized hardware ( Berwald 2019 ) has emerged as a promising alternative for QUBO. However, the limited number of qubits and noise sensitivity ( Zaborniak & de Sousa 2021 ) still impede its widespread practical application. Meanwhile, learning-based methods are gaining substantial traction as a powerful approach to binary optimization. For example, QUBO problems can be naturally represented using graph structures, enabling the application of graph neural networks (GNNs) to effectively model variable interactions and achieve strong empirical performance ( Schuetz et al. 2022 ; Ichikawa 2024 ) . In addition, Tönshoff et al. 2023 introduces a general graph representation for constraint satisfaction problems and proposes a GNN-based reinforcement learning approach enhanced with global search actions. Despite their promise, such methods often operate without theoretical guarantees and encounter practical difficulties related to data acquisition and model generalization. A prominent line of work within this domain smooths Problem ( 1 ) using a probabilistic framework ( Karalias & Loukas 2020 ; Qiu et al. 2025 ) : GNNs are leveraged to parameterize an independent distribution over the binary space \{0,1\}^{n} , and the loss function is subsequently constructed in terms of the expectation of F . We note that this approach is essentially to relax Problem ( 1 ) to: \min_{{\bm{x}}\in[0,1]^{n}}f({\bm{x}}), (2) where f:\mathbb{R}^{n}\rightarrow\mathbb{R} is the multilinear extension of F (see Section 2 for definition). Although this relaxation preserves theoretical guarantees relative to the original problem ( Wang et al. 2022 ) , the non-convex nature of f in Problem ( 2 ) still presents significant optimization challenges. To tackle this challenge, we revisit the binary optimization problem ( 1 ), and reformulate it into a continuous model by characterizing binarity via continuous variables and convex constraint functions. Based on Lagrangian duality, an equivalent minimax problem is derived, to which we develop a gradient descent-ascent (GDA)-based algorithm for efficient solutions. We remark that by initializing dual variables as positive values, we induce convexity in the primal space, promoting the identification of high-quality solutions. As optimization proceeds, the dual variables gradually decrease, shifting emphasis from convexity promotion to the enforcement of integrality. We refer to this approach as “a P rimal- D ual approach for B inary O ptimization” (denoted as PDBO), with the overall framework illustrated in Figure 1 . Figure 1: An illustration of PDBO. The distinct contributions of our work are summarized as follows. • Primal-Dual Reformulation. We introduce a novel framework that reformulates unconstrained binary optimization as a continuous minimax problem, satisfying a strong max-min property. This reformulation smooths the discrete problem, enabling efficient gradient-based optimization. • GDA with Guarantees. We develop a simultaneous GDA-based algorithm that is highly parallelizable on GPUs and provably converges to near-optimal solutions in linear time. • Empirical Superiority. Through extensive experiments on large-scale problems including Max-Cut, MaxSAT, and Maximum Independent Set with up to 50,000 variables, we demonstrate that our method achieves state-of-the-art performance, obtaining high-quality solutions within seconds. 2 Preliminaries Definition 1 (Extension) . Let F:\{0,1\}^{n}\rightarrow\mathbb{R} be a function defined on the binary domain. A function f:[0,1]^{n}\rightarrow\mathbb{R} is called an extension of F if f({\bm{x}})=F({\bm{x}}) for every {\bm{x}}\in\{0,1\}^{n} . Definition 2 (Multilinear Function) . A function f:\mathbb{R}^{n}\rightarrow\mathbb{R} is called multilinear if it is affine in each variable when all other variables are held fixed. Remark 1 . Any function F:\{0,1\}^{n}\rightarrow\mathbb{R} admits a unique multilinear extension f defined by: f({\bm{x}})\coloneqq\mathbb{E}_{\bm{\xi}\sim P_{{\bm{x}}}}[F(\bm{\xi})]=\sum_{\bm{\xi}\in\{0,1\}^{n}}P_{{\bm{x}}}(\bm{\xi})\cdot F(\bm{\xi}), where for {\bm{x}}\in[0,1]^{n} , P_{{\bm{x}}}(\bm{\xi})\coloneqq\prod_{i=1}^{n}x_{i}^{\xi_{i}}(1-x_{i})^{1-\xi_{i}} denotes the n -dimensional independent Bernoulli distribution with mean vector {\bm{x}} . A key property of the multilinear extension is that it preserves the minimum value of the original function: Lemma 1 . Let f:[0,1]^{n}\rightarrow\mathbb{R} be the multilinear extension of F:\{0,1\}^{n}\rightarrow\mathbb{R} . Then \min_{{\bm{x}}\in[0,1]^{n}}f({\bm{x}})=\min_{{\bm{x}}\in\{0,1\}^{n}}F({\bm{x}}). Lemma 1 establishes the equivalence between Problem ( 1 ) and its continuous relaxation ( 2 ). However, we note that f is generally non-convex, making the relaxed problem still challenging to solve. Proposition 1 . If F:\{0,1\}^{n}\rightarrow\mathbb{R} is a polynomial function of the form F({\bm{x}})=\sum\limits_{{\bm{d}}}a_{{\bm{d}}}{\bm{x}}^{{\bm{d}}} , where {\bm{x}}^{{\bm{d}}}\coloneqq x_{1}^{d_{1}}x_{2}^{d_{2}}\cdots x_{n}^{d_{n}} , then its multilinear extension is given by: f({\bm{x}})=\sum_{{\bm{d}}}a_{{\bm{d}}}\prod_{i:d_{i}\neq 0}x_{i}. Proposition 1 shows that for polynomial objectives (such as QUBO and MaxSAT), the multilinear extension has a compact closed form, avoiding exponential summation. This makes computation tractable for many practical optimization problems. Definition