International Journal of Metaheuristics

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

Fred Glover, Jin‐Kao Hao

Published Jan 1, 2010• 14 citations

Abstract

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.

DOI: 10.1504/ijmheur.2010.034201

Related papers

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 MetaheuristicsJan 1, 201044 citations

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

Bahram Alidaee, Haibo Wang, Lutfu Sagbansua

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.

AlgorithmsDec 5, 20234 citations

Global equilibrium search applied to the unconstrained binary quadratic optimization problem

Pãnos M. Pardalos, Oleg A. Prokopyev, Oleg V. Shylo +1 more

We describe a heuristic method for solving the unconstrained binary quadratic optimization problem based on a global equilibrium search framework. We investigate performance of the proposed approach and compare it with the best available solver [G. Palubeckis, Multistart tabu search strategies for the unconstrained binary quadratic optimization problem, Ann. Oper. Res., 131 (2004), pp. 259–282; G. Palubeckis, Unconstrained binary quadratic optimization. Available at http://www.soften.ktu.lt/∼gintaras/binqopt.html (Last accessed December 2006).] on well-known benchmarks instances. The reported computational results indicate a high efficiency of the heuristic.

Optimization methods & softwareDec 22, 200732 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

Several versions of the Devour Digest Tidy-up Heuristic for Unconstrained Binary Quadratic Problems

Saïd Hanafi, Ahmed Rebaï, Michel Vasquez

The unconstrained binary quadratic minimization problem is known to be NP hard and due to its computational challenge and application capability, it becomes more and more considered and involved by the recent research studies, including both exact and heuristic solution approaches. Our work is in line with what was suggested by Glover, Alidaee, Rego and Kochenberger (2002) who proposed one pass heuristics as alternatives to the well-known Devour Digest Tidy-up procedure (DDT) of Boros, Hammer and Sun (1989). The "devour" step sets a term of the current representation to 0 or 1, and the "tidy-up" step substitutes the logical consequences derived from the "digest" step into the current quadratic function. We propose several versions of the DDT constructive heuristic based on the alternative representation of the quadratic function. We also present an efficient implementation of local search using one-flip and two-flip moves that simultaneously change the values of one or two binary variables. Computational experiments performed on instances up to 7000 variables show the efficiency of our implementation in terms of quality improvement and CPU use enhancement.

Jul 25, 20110 citations

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