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

Genetic and Evolutionary Computation Conference (GECCO)

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

Kengo Katayama, Masafumi Tani, Hiroyuki Narihisa

Published Jul 10, 2000• 42 citations
OpenAlex

Abstract

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

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

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

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

An Iterated Greedy Algorithm for the Binary Quadratic Programming Problem

Takenori Murakami, Fubito Toyama, Kenji Shoji +1 more

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.

IEEJ Transactions on Electronics Information and Systems•Jan 1, 2010•0 citations

Local Search for Integer Quadratic Programming

Xiang He, Peng Lin, Tao Jiang +1 more

Integer quadratic programming (IQP) is an important problem in operations research. Local search is a powerful primal heuristic method for solving hard problems, but the research on local search algorithms for solving IQP is still in its early stages. This paper introduces an efficient local search algorithm called LS-IQCQP, which stands for “local search for integer quadratically constrained quadratic programming.” The algorithm is designed for solving general IQP, and it is capable of handling cases where quadratic terms appear in the objective function, constraints, or both. We propose four newly designed operators: the root operator for feasibility and three operators—inequality exploration, equality balance, and unconstrained free operator—for optimizing the objective function. To evaluate the quality of these operations, a weighted scoring function is introduced. Based on the scoring function, LS-IQCQP iteratively applies effective operations and employs a WalkSAT-like approach (a classic local search algorithm for satisfiability problems) by randomly selecting an operation to escape local optima. Experiments are conducted on standard IQP benchmarks from the Quadratic Programming Library (QPLIB) and Mixed-Integer Nonlinear Programming Library (MINLPLIB), comparing LS-IQCQP with several state-of-the-art IQP solvers. Experimental results demonstrate that LS-IQCQP is competitive with the most powerful commercial solver Gurobi and other state-of-the-art solvers in terms of finding a good feasible solution quickly. Moreover, LS-IQCQP has established six new records for QPLIB and MINLPLIB open instances by finding the new best-known solutions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This research was supported by the National Key Research and Development Program of China [Grant 2023YFA1009500]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1178 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1178 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .

arXiv:2409.19668•INFORMS journal on computing•May 12, 2026•0 citations
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
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.
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.
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.
Integer quadratic programming (IQP) is an important problem in operations research. Local search is a powerful primal heuristic method for solving hard problems, but the research on local search algorithms for solving IQP is still in its early stages. This paper introduces an efficient local search algorithm called LS-IQCQP, which stands for “local search for integer quadratically constrained quadratic programming.” The algorithm is designed for solving general IQP, and it is capable of handling cases where quadratic terms appear in the objective function, constraints, or both. We propose four newly designed operators: the root operator for feasibility and three operators—inequality exploration, equality balance, and unconstrained free operator—for optimizing the objective function. To evaluate the quality of these operations, a weighted scoring function is introduced. Based on the scoring function, LS-IQCQP iteratively applies effective operations and employs a WalkSAT-like approach (a classic local search algorithm for satisfiability problems) by randomly selecting an operation to escape local optima. Experiments are conducted on standard IQP benchmarks from the Quadratic Programming Library (QPLIB) and Mixed-Integer Nonlinear Programming Library (MINLPLIB), comparing LS-IQCQP with several state-of-the-art IQP solvers. Experimental results demonstrate that LS-IQCQP is competitive with the most powerful commercial solver Gurobi and other state-of-the-art solvers in terms of finding a good feasible solution quickly. Moreover, LS-IQCQP has established six new records for QPLIB and MINLPLIB open instances by finding the new best-known solutions. History: Accepted by Erwin Pesch, Area Editor for Heuristic Search & Approximation Algorithms. Funding: This research was supported by the National Key Research and Development Program of China [Grant 2023YFA1009500]. Supplemental Material: The software that supports the findings of this study is available within the paper and its Supplemental Information ( https://pubsonline.informs.org/doi/suppl/10.1287/ijoc.2025.1178 ) as well as from the IJOC GitHub software repository ( https://github.com/INFORMSJoC/2025.1178 ). The complete IJOC Software and Data Repository is available at https://informsjoc.github.io/ .