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

IEEJ Transactions on Electronics Information and Systems

An Iterated Greedy Algorithm for the Binary Quadratic Programming Problem

Takenori Murakami, Fubito Toyama, Kenji Shoji, Jyuichi Miyamichi

Published Jan 1, 2010• 0 citations
Publisher

Abstract

In this paper, Iterated Greedy algorithm with K-opt Local Search (IGKLS) is proposed for the binary quadratic programming problem (BQP). The proposed iterated greedy algorithm consists of two central phases, construction and destruction phases. As a local search algorithm, k-opt local search is applied after the construction phase. The computational results showed that the proposed iterated greedy algorithm outperformed state-of-the-art methods for huge size BQP instances.

DOI
10.1541/ieejeiss.130.1089

Related papers

An iterated greedy algorithm for the binary quadratic programming problem

Fubito Toyama, Kenji Shoji, Hiroshi Mori +1 more

The binary quadratic programming problem (BQP) is an NP-hard problem and has a large number of applications. In this paper, an iterated greedy algorithm with k-opt local search (IGKLS) is proposed for the BQP. Iterated greedy (IG) algorithm has already been applied to a variety of optimization problems, and shown to be simple but with excellent search performance. The proposed iterated greedy algorithm consists of two central phases, destruction and construction phases. As a local search algorithm, k-opt local search is applied after the construction phase. The computational results showed that the proposed iterated greedy algorithm outperformed state-of-the-art methods for huge size BQP instances.

Joint International Conference on Soft Computing and Intelligent Systems and International Symposium on Advanced Intelligent Systems (SCIS&ISIS)•Nov 1, 2012•4 citations

Solving large binary quadratic programming problems by effective genetic local search algorithm

Kengo Katayama, Masafumi Tani, Hiroyuki Narihisa

A genetic local search (GLS) algorithm, which is a combination technique of ge-netic algorithm and local search, for the un-constrained binary quadratic programming problem (BQP) is presented. An effective lo-cal search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale prob-lem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our aver-age solution values obtained are better than previous powerful heuristic approaches espe-cially for the large problem instances of 2,500 variables. 1

Genetic and Evolutionary Computation Conference (GECCO)•Jul 10, 2000•42 citations

Iterated Tabu Search Algorithm for Solving 0-1 Binary Quadratic Programming Problem

Zhang Ai-jun, Qin Xin-qiang, Gong Chun-qiong

This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem.The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum.Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS.Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.

Jisuanji gongcheng•Jan 1, 2012•0 citations

Cover-Relax-Search: A Primal Heuristic for Binary Quadratic Programs

Weimin Huang, Natalie M. Isenberg, Ján Drgoňa +2 more

Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.

arXiv:2501.05052•Jan 9, 2025•0 citations

Iterated Tabu Search for the Unconstrained Binary Quadratic Optimization Problem

Gintaras Palubeckis

Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.

Informatica•Jan 1, 2006•64 citations

Perturbation Based Search Method For Solving Unconstrained Binary Quadratic Programming Problem

Muthu Solayappan, Kien Ming Ng, Kim Leng Poh

This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.

•Jan 23, 2008•1 citation
In this paper, Iterated Greedy algorithm with K-opt Local Search (IGKLS) is proposed for the binary quadratic programming problem (BQP). The proposed iterated greedy algorithm consists of two central phases, construction and destruction phases. As a local search algorithm, k-opt local search is applied after the construction phase. The computational results showed that the proposed iterated greedy algorithm outperformed state-of-the-art methods for huge size BQP instances.
The binary quadratic programming problem (BQP) is an NP-hard problem and has a large number of applications. In this paper, an iterated greedy algorithm with k-opt local search (IGKLS) is proposed for the BQP. Iterated greedy (IG) algorithm has already been applied to a variety of optimization problems, and shown to be simple but with excellent search performance. The proposed iterated greedy algorithm consists of two central phases, destruction and construction phases. As a local search algorithm, k-opt local search is applied after the construction phase. The computational results showed that the proposed iterated greedy algorithm outperformed state-of-the-art methods for huge size BQP instances.
A genetic local search (GLS) algorithm, which is a combination technique of ge-netic algorithm and local search, for the un-constrained binary quadratic programming problem (BQP) is presented. An effective lo-cal search algorithm, which is a variant of the k-opt local search for the BQP by Merz et al., is described, and the performance of the GLS with the variant local search heuristic is demonstrated on several large-scale prob-lem instances. Our computational results indicate that the GLS is able to frequently find the best-known solution with a relatively short running time and obviously our aver-age solution values obtained are better than previous powerful heuristic approaches espe-cially for the large problem instances of 2,500 variables. 1
This paper presents an iterated Tabu Search(TS) algorithm for the Binary Quadratic Programming(BQP) problem.The TS as the Local Search(LS) and a new perturbation strategy makes the search jump into a more promising area when TS falling into the local optimum.Experimental results show that the proposed algorithm can reach the best known solution on all the 30 large OR-library instances and comparisons with TS.Simulated Annealing(SA) and Memetic Algorithm(MA) demonstrate the competitiveness of the proposed algorithm.
Binary Quadratic Programs (BQPs) are a class of NP-hard problems that arise in a wide range of applications, including finance, machine learning, and logistics. These problems are challenging to solve due to the combinatorial search space and nonlinearity. In fact, this class of optimization problems is so challenging that, in many instances, standard algorithms struggle to identify feasible solutions within a reasonable time. Primal heuristic algorithms have been developed to quickly identify feasible solutions to BQPs. In this paper, we propose Cover-Relax-Search, an efficient primal heuristic for BQPs. This approach is inspired by multiple local search algorithms, including Undercover. We evaluate the \emph{Cover-Relax-Search} algorithm on multiple BQP benchmarks and show that our proposed heuristic identifies high-quality solutions at a faster speed and significantly reduces the primal integral compared to state-of-the-art solvers and other local search baselines.
Given a set of objects with profits (any, even negative, numbers) assigned not only to separate objects but also to pairs of them, the unconstrained binary quadratic optimization problem consists in finding a subset of objects for which the overall profit is maximized. In this paper, an iterated tabu search algorithm for solving this problem is proposed. Computational results for problem instances of size up to 7000 variables (objects) are reported and comparisons with other up-to-date heuristic methods are provided.
This paper presents a perturbation based search method to solve the unconstrained binary quadratic programming problem. The proposed algorithm was tested with some of the standard test problems and the results are reported for 10 instances of 50, 100, 250, & 500 variable problems. A comparison of the performance of the proposed algorithm with other heuristics and optimization software is made. Based on the results, it was found that the proposed algorithm is computationally inexpensive and the solutions obtained match the best known solutions for smaller sized problems. For larger instances, the algorithm is capable of finding a solution within 0.11% of the best known solution. Apart from being used as a stand-alone method, this algorithm could also be incorporated with other heuristics to find better solutions.