Joint International Conference on Soft Computing and Intelligent Systems and International Symposium on Advanced Intelligent Systems (SCIS&ISIS)

An iterated greedy algorithm for the binary quadratic programming problem

Fubito Toyama, Kenji Shoji, Hiroshi Mori, Juichi Miyamichi

Published Nov 1, 2012• 4 citations

Publisher

Abstract

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.

DOI: 10.1109/scis-isis.2012.6505143

Related papers

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 SystemsJan 1, 20100 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.05052Jan 9, 20250 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, 200042 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 gongchengJan 1, 20120 citations

A Fast Binary Quadratic Programming Solver Based on Stochastic Neighborhood Search

Benson S. Y. Lam, Alan Wee‐Chung Liew

Many image processing and pattern recognition problems can be formulated as binary quadratic programming (BQP) problems. However, solving a large BQP problem with a good quality solution and low computational time is still a challenging unsolved problem. Current methodologies either adopt an independent random search in a semi-definite space or perform search in a relaxed biconvex space. However, the independent search has great computation cost as many different trials are needed to get a good solution. The biconvex search only searches the solution in a local convex ball, which can be a local optimal solution. In this paper, we propose a BQP solver that alternatingly applies a deterministic search and a stochastic neighborhood search. The deterministic search iteratively improves the solution quality until it satisfies the KKT optimality conditions. The stochastic search performs bootstrapping sampling to the objective function constructed from the potential solution to find a stochastic neighborhood vector. These two steps are repeated until the obtained solution is better than many of its stochastic neighborhood vectors. We compare the proposed solver with several state-of-the-art methods for a range of image processing and pattern recognition problems. Experimental results showed that the proposed solver not only outperformed them in solution quality but also with the lowest computational complexity.

IEEE Transactions on Pattern Analysis and Machine IntelligenceJul 21, 20205 citations

New approximation methods for solving binary quadratic programming problem

Rui Yang

In this thesis, we consider a special class of binary quadratic programming problem (BQP) where the number of nonzero elements is fixed. Such problems arise frequently from various applications and have been proved to be NP-hard. After a brief review of the quadratic programming problem, several optimization algorithms are presented. In Chapter 3, we propose a new simple second order conic relaxation of the BQP problem. We derive some additional constraints based on the information from the data matrix. The algorithm will be compared with the existing SDP relaxation algorithm in terms of their numerical performances. In Chapter 4, we use the convex quadratic relaxation as a geometric embedding tool to reformulate the underlying BQP as a clustering problem, where the target is to find a single cluster of fixed size. This connection allows us to employ many effective clustering algorithm developed in the data mining field. A 2-approximation algorithm for the clustering problem is presented. Numerical results based on the new relaxation model and the proposed algorithm are reported. The last Chapter mainly discusses some theoretical results we put forward on the derived clustering problem. Core-set technique is used to derive a new algorithm, which can provide a (1+\epsilon) approximation ratio to the reformulated clustering problem.

Jun 22, 20102 citations