Jisuanji gongcheng

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

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

Published Jan 1, 2012• 0 citations

Abstract

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.

Related papers

Heuristic algorithms for the unconstrained binary quadratic programming problem

J. E. Beasley

In this paper we consider the unconstrained binary quadratic programming problem. This is the problem of maximising a quadratic objective by suitable choice of binary (zero-one) variables. We present two heuristic algorithms based upon tabu search and simulated annealing for this problem. Computational results are presented for a number of publically available data sets involving up to 2500 variables. An interesting feature of our results is that whilst for most problems tabu search dominates simulated annealing for the very largest problems we consider the converse is true. This paper typifies a "multiple solution technique, single paper" approach, i.e. an approach that within the same paper presents results for a number of different heuristics applied to the same problem. Issues relating to algorithmic design for such papers are discussed. Keywords: unconstrained binary (zero-one) quadratic programming

Jan 1, 1998151 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.

InformaticaJan 1, 200664 citations

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, 20124 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

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.19668INFORMS journal on computingMay 12, 20260 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, 20081 citation