Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2407.19676 · IEEE Congress on Evolutionary Computation (CEC)

On the Effects of Smoothing Rugged Landscape by Different Toy Problems: A Case Study on UBQP

Wei Wang, Jialong Shi, Jianyong Sun, Arnaud Liefooghe, Qingfu Zhang, Ye Fan

Published Jun 30, 2024• 0 citations
arXivHTMLPDF

Abstract

The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$‘), a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/-\mathrm{i}$’) and a toy UBQP with matrix$\hat{\boldsymbol{Q}}^{3}$(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP with$\hat{\boldsymbol{Q}}^{1}$(construct by “$+/-1$”) exhibits the flattest landscape among the three, while the toy UBQP with$\hat{Q}^{3}$(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP with$\hat{\boldsymbol{Q}}^{2}$(construct by “$+/\cdot \mathbf{i})$emerges as the most effective, while$\hat{\boldsymbol{Q}}^{3}$(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.

DOI
10.1109/cec60901.2024.10612165

Related papers

Greedy and Local Search Heuristics for Unconstrained Binary Quadratic Programming

Peter Merz, Bernd Freisleben

Journal of Heuristics•Mar 1, 2002•147 citations

Local Minima in Quadratic-Penalty Relaxations of Binary Linear Programs

Cheng-Han Huang, Yongliang Sun, Chaoyan Huang +2 more

Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box $[0,1]^n$ and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relaxed problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, 0--1 knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.

arXiv:2606.28734•Jun 27, 2026•0 citations

On some features of quadratic unconstrained binary optimization with random coefficients

Marco Isopi, Benedetto Scoppola, Alessio Troiani

Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form $$H(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}$$ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, $$\eta \in \{0, 1\}^N$$ η ∈ { 0 , 1 } N and W a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington–Kirkpatrick spin glass model. Finding the optima of H is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the $$J_{i,j}$$ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum per particle of H do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of H. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the $$J_{i,j}$$ J i , j ’s is allowed to be zero with probability going to 1 as $$N \rightarrow \infty $$ N → ∞ in a suitable way.

arXiv:2402.17059•Bollettino Della Unione Matematica Italiana•Aug 22, 2024•7 citations

Computing Local Optima in Quadratic Unconstrained Binary Optimization Problems in Randomized Polynomial Time

Lunshan Gao

•Jan 1, 2024•0 citations

A Parallel Tabu Search for the Unconstrained Binary Quadratic Programming problem

Jialong Shi, Qingfu Zhang, Bilel Derbel +1 more

Although several sequential heuristics have been proposed for dealing with the Unconstrained Binary Quadratic Programming (UBQP), very little effort has been made for designing parallel algorithms for the UBQP. This paper propose a novel decentralized parallel search algorithm, called Parallel Elite Biased Tabu Search (PEBTS). It is based on D2TS, a state-of-the-art sequential UBQP metaheuristic. The key strategies in the PEBTS algorithm include: (i) a lazy distributed cooperation procedure to maintain diversity among different search processes and (ii) finely tuned bit-flip operators which can help the search escape local optima efficiently. Our experiments on the Tianhe-2 supercomputer with up to 24 computing cores show the accuracy of the efficiency of PEBTS compared with a straightforward parallel algorithm running multiple independent and non-cooperating D2TS processes.

IEEE Congress on Evolutionary Computation (CEC)•Jun 1, 2017•5 citations

One-pass heuristics for large-scale unconstrained binary quadratic problems

Fred Glover, Bahram Alidaee, César Rego +1 more

European Journal of Operational Research•Mar 1, 2002•71 citations
The hardness of the Unconstrained Binary Quadratic Program (UBQP) problem is due its rugged landscape. Various algorithms have been proposed for UBQP, including the Landscape Smoothing Iterated Local Search (LSILS). Different from other UBQP algorithms, LSILS tries to smooth the rugged landscape by building a convex combination of the original UBQP and a toy UBQP. In this paper, our study further investigates the impact of smoothing rugged landscapes using different toy UBQP problems, including a toy UBQP with matrixQ^1\hat{\boldsymbol{Q}}^{1}Q^​1(construct by “+/−1+/-1+/−1‘), a toy UBQP with matrixQ^2\hat{\boldsymbol{Q}}^{2}Q^​2(construct by “+/−i+/-\mathrm{i}+/−i’) and a toy UBQP with matrixQ^3\hat{\boldsymbol{Q}}^{3}Q^​3(construct randomly). We first assess the landscape flatness of the three toy UBQPs. Subsequently, we test the efficiency of LSILS with different toy UBQPs. Results reveal that the toy UBQP withQ^1\hat{\boldsymbol{Q}}^{1}Q^​1(construct by “+/−1+/-1+/−1”) exhibits the flattest landscape among the three, while the toy UBQP withQ^3\hat{Q}^{3}Q^​3(construct randomly) presents the most non-flat landscape. Notably, LSILS using the toy UBQP withQ^2\hat{\boldsymbol{Q}}^{2}Q^​2(construct by “+/⋅i)+/\cdot \mathbf{i})+/⋅i)emerges as the most effective, whileQ^3\hat{\boldsymbol{Q}}^{3}Q^​3(construct randomly) has the poorest result. These findings contribute to a detailed understanding of landscape smoothing techniques in optimizing UBQP.
Many combinatorial optimization problems admit quadratic unconstrained binary formulations (QUBO) which can often be relaxed to the box [0,1]n[0,1]^n[0,1]n and optimized using scalable gradient-based methods. However, the resulting non-convex landscape can often contain local optima that are spurious or infeasible. In this paper, we establish sufficient structural conditions on quadratic penalties that rule out these failures, guaranteeing that every local minimizer of the relaxed problem is both binary and feasible. For each problem we study, we examine existing QUBO formulations when available, identify why they fail when they do, and propose alternative relaxed QUBOs that satisfy our conditions. We show for several common combinatorial problems, including open-pit mining, 0--1 knapsack, and traveling salesman formulations, that these constructions allow gradient-based methods such as projected gradient descent and Adam to be safely applied to obtain valid binary solutions. Our results clarify when differentiable optimization is a reliable local solver for quadratic combinatorial objectives.
Abstract Quadratic Unconstrained Binary Optimization (QUBO or UBQP) is concerned with maximizing/minimizing the quadratic form H(J,η)=W∑i,jJi,jηiηjH(J, \eta ) = W \sum _{i,j} J_{i,j} \eta _{i} \eta _{j}H(J,η)=W∑i,j​Ji,j​ηi​ηj​ H ( J , η ) = W ∑ i , j J i , j η i η j with J a matrix of coefficients, η∈{0,1}N\eta \in \{0, 1\}^Nη∈{0,1}N η ∈ { 0 , 1 } N and W a normalizing constant. In the statistical mechanics literature, QUBO is a lattice gas counterpart to the (generalized) Sherrington–Kirkpatrick spin glass model. Finding the optima of H is an NP-hard problem. Several problems in combinatorial optimization and data analysis can be mapped to QUBO in a straightforward manner. In the combinatorial optimization literature, random instances of QUBO are often used to test the effectiveness of heuristic algorithms. Here we consider QUBO with random independent coefficients and show that if the Ji,jJ_{i,j}Ji,j​ J i , j ’s have zero mean and finite variance then, after proper normalization, the minimum and maximum per particle of H do not depend on the details of the distribution of the couplings and are concentrated around their expected values. Further, with the help of numerical simulations, we study the minimum and maximum of the objective function and provide some insight into the structure of the minimizer and the maximizer of H. We argue that also this structure is rather robust. Our findings hold also in the diluted case where each of the Ji,jJ_{i,j}Ji,j​ J i , j ’s is allowed to be zero with probability going to 1 as N→∞N \rightarrow \infty N→∞ N → ∞ in a suitable way.
Although several sequential heuristics have been proposed for dealing with the Unconstrained Binary Quadratic Programming (UBQP), very little effort has been made for designing parallel algorithms for the UBQP. This paper propose a novel decentralized parallel search algorithm, called Parallel Elite Biased Tabu Search (PEBTS). It is based on D2TS, a state-of-the-art sequential UBQP metaheuristic. The key strategies in the PEBTS algorithm include: (i) a lazy distributed cooperation procedure to maintain diversity among different search processes and (ii) finely tuned bit-flip operators which can help the search escape local optima efficiently. Our experiments on the Tianhe-2 supercomputer with up to 24 computing cores show the accuracy of the efficiency of PEBTS compared with a straightforward parallel algorithm running multiple independent and non-cooperating D2TS processes.