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

Algorithms

An Efficient Closed-Form Formula for Evaluating r-Flip Moves in Quadratic Unconstrained Binary Optimization

Bahram Alidaee, Haibo Wang, Lutfu Sagbansua

Published Dec 5, 2023• 4 citations
Publisher

Abstract

Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.

DOI
10.3390/a16120557

Related papers

Fast two-flip move evaluations for binary unconstrained quadratic optimisation problems

Fred Glover, Jin‐Kao Hao

We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.

International Journal of Metaheuristics•Jan 1, 2010•14 citations

Efficient Solutions for Large-Scale Max-Cut Problems: A Hybrid Local Search Heuristic Approach and Comparative Analysis with Quantum Annealing

Haibo Wang, Bahram Alidaee, Lutfu Sagbansua

In this study, we address the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on very-large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.

•Feb 29, 2024•1 citation

Hybrid Heuristic Algorithms for Adiabatic Quantum Machine Learning Models

Bahram Alidaee, Haibo Wang, Lutfu Sua +1 more

Numerous established machine learning models and various neural network architectures can be restructured as Quadratic Unconstrained Binary Optimization (QUBO) problems. A significant challenge in Adiabatic Quantum Machine Learning (AQML) is the computational demand of the training phase. To mitigate this, approximation techniques inspired by quantum annealing, like Simulated Annealing and Multiple Start Tabu Search (MSTS), have been employed to expedite QUBO-based AQML training. This paper introduces a novel hybrid algorithm that incorporates an "r-flip" strategy. This strategy is aimed at solving large-scale QUBO problems more effectively, offering better solution quality and lower computational costs compared to existing MSTS methods. The r-flip approach has practical applications in diverse fields, including cross-docking, supply chain management, machine scheduling, and fraud detection. The paper details extensive computational experiments comparing this r-flip enhanced hybrid heuristic against a standard MSTS approach. These tests utilize both standard benchmark problems and three particularly large QUBO instances. The results indicate that the r-flip enhanced method consistently produces high-quality solutions efficiently, operating within practical time constraints.

arXiv:2407.21062•Jul 26, 2024•0 citations

Efficient Solutions for Large-Scale Max-Cut Problems: A Hybrid Local Search Heuristic Approach and Comparative Analysis with Quantum Annealing

Haibo Wang, Bahram Alidaee, Lutfu Sagbansua

This study addresses the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.

•Jun 25, 2024•1 citation

Efficient evaluations for solving large 0-1 unconstrained quadratic optimisation problems

Fred Glover, Jin‐Kao Hao

Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.

International Journal of Metaheuristics•Jan 1, 2010•44 citations

Constraint Programming to Discover One-Flip Local Optima of Quadratic Unconstrained Binary Optimization Problems

Amit Verma, Mark W. Lewis

The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.

arXiv:2104.01709•Apr 4, 2021•2 citations
Quadratic unconstrained binary optimization (QUBO) is a classic NP-hard problem with an enormous number of applications. Local search strategy (LSS) is one of the most fundamental algorithmic concepts and has been successfully applied to a wide range of hard combinatorial optimization problems. One LSS that has gained the attention of researchers is the r-flip (also known as r-Opt) strategy. Given a binary solution with n variables, the r-flip strategy “flips” r binary variables to obtain a new solution if the changes improve the objective function. The main purpose of this paper is to develop several results for the implementation of r-flip moves in QUBO, including a necessary and sufficient condition that when a 1-flip search reaches local optimality, the number of candidates for implementation of the r-flip moves can be reduced significantly. The results of the substantial computational experiments are reported to compare an r-flip strategy-embedded algorithm and a multiple start tabu search algorithm on a set of benchmark instances and three very-large-scale QUBO instances. The r-flip strategy implemented within the algorithm makes the algorithm very efficient, leading to very high-quality solutions within a short CPU time.
We provide a method for efficiently evaluating two-flip moves that simultaneously change the values of two 0-1 variables in search methods for binary unconstrained quadratic optimisation problems (UQP). We extend a framework recently proposed by the authors for creating efficient evaluations of one-flip moves to yield a method requiring significantly less computation time than a direct sequential application of one-flips. A tabu search algorithm that combines one-flip and two-flip moves, in a study currently in process, has made use of this extension to produce very competitive results on some UQP benchmark instances.
In this study, we address the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on very-large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
Numerous established machine learning models and various neural network architectures can be restructured as Quadratic Unconstrained Binary Optimization (QUBO) problems. A significant challenge in Adiabatic Quantum Machine Learning (AQML) is the computational demand of the training phase. To mitigate this, approximation techniques inspired by quantum annealing, like Simulated Annealing and Multiple Start Tabu Search (MSTS), have been employed to expedite QUBO-based AQML training. This paper introduces a novel hybrid algorithm that incorporates an "r-flip" strategy. This strategy is aimed at solving large-scale QUBO problems more effectively, offering better solution quality and lower computational costs compared to existing MSTS methods. The r-flip approach has practical applications in diverse fields, including cross-docking, supply chain management, machine scheduling, and fraud detection. The paper details extensive computational experiments comparing this r-flip enhanced hybrid heuristic against a standard MSTS approach. These tests utilize both standard benchmark problems and three particularly large QUBO instances. The results indicate that the r-flip enhanced method consistently produces high-quality solutions efficiently, operating within practical time constraints.
This study addresses the formidable challenge of solving large-scale Max-Cut problems (MCP). We introduce a rapid computational procedure utilizing a hybrid 1-flip/r-flip local search heuristic. This innovative strategy significantly reduces the computational time required for MCP problems while consistently generating solutions of exceptional quality. The paper presents substantial computational insights, showcasing the effectiveness of our approach on large-scale Max-Cut instances with varying densities. Our proposed heuristic is rigorously evaluated by comparing its performance against a quantum annealing solver, leveraging a multi-start Tabu Search framework. The results underscore the potency of this unique combination as an efficient and effective solution for large-scale QUBO problems. Notably, our hybrid heuristic consistently delivers high-quality solutions within the stringent CPU time limits of 600 seconds, demonstrating its efficacy across Max-Cut instances ranging from 10,000 to 40,000 variables. This research contributes to advancing the state-of-the-art in large-scale QUBO problem-solving, offering a powerful and time-efficient approach with broad applicability.
Abstract: We provide a method for efficiently evaluating moves that complement values of 0–1 variables in search methods for binary unconstrained quadratic optimisation problems. Our method exploits a compact matrix representation and offers further improvements in speed by exploiting sparse matrices that arise in large-scale applications. The resulting approach, which works with integer or real data, can be applied to improve the efficiency of a variety of different search processes, especially in the case of commonly encountered applications that involve large and sparse matrices. It also enables larger problems to be solved than could previously be handled within a given amount of available memory. Our evaluation method has been embedded in a tabu search algorithm in a sequel to this paper, yielding a method that efficiently matches or improves currently best-known results for instances from widely used benchmark sets having up to 7,000 variables.
The broad applicability of Quadratic Unconstrained Binary Optimization (QUBO) constitutes a general-purpose modeling framework for combinatorial optimization problems and are a required format for gate array and quantum annealing computers. QUBO annealers as well as other solution approaches benefit from starting with a diverse set of solutions with local optimality an additional benefit. This paper presents a new method for generating a set of one-flip local optima leveraging constraint programming. Further, as demonstrated in experimental testing, analysis of the solution set allows the generation of soft constraints to help guide the optimization process.