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

International Journal of Metaheuristics

Polynomial unconstrained binary optimisation â part 2

Fred Glover, Jin‐Kao Hao, Gary A. Kochenberger

Published Jan 1, 2011• 11 citations
Publisher

Abstract

The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimisation problem. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover et al., 2011) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms.

DOI
10.1504/ijmheur.2011.044356

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 Metaheuristics•Jan 1, 2010•44 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, 1998•151 citations

A Polynomial-Time Algorithm for Unconstrained Binary Quadratic Optimization

Juan Ignacio Mulero-Martínez

In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class $P$. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.

arXiv:2005.07030•May 13, 2020•0 citations

Algorithms for unconstrained quadratic 0-1 programming and related problems on contemporary computer architectures

Gregory P. Rodgers

Unconstrained quadratic zero-one programming belongs to the class of NP-complete problems. It is therefore considered computationally intractable. Much research has been done in trying to find subsets of unconstrained quadratic 0-1 programs that can be solved in polynomial time. However, for the general problem, nonpolynomial methods must be used, resulting in limitations on the size of problems that can be solved. Branch and bound is a computational method that implicitly enumerates all possible solutions. Research on branch and bound algorithms is vast. Due to the computational complexity of the algorithm, efficient implementations are necessary in order to solve even moderate size problems. It is natural to expect that any implementation of a branch and bound algorithm may consume large amounts of computer resources due to the nature of the algorithm. Therefore, it is desirable to exploit contemporary high performance computers. In this thesis, efficiencies in the implementation of new 0-1 branch and bound algorithms on contemporary computer architectures are studied. Though not primarily designed for combinatorial problems, it is shown that many contemporary architectures, including distributed and shared memory multiprocessors, are capable of increasing the scope of solvable discrete programming problems. An application of unconstrained quadratic 0-1 programming is the maximum clique problem. It is shown that the variable selection rule in the proposed algorithm is equivalent to a nongreedy vertex selection rule for the maximum clique problem. This rule enhances the use of preprocessing rules that are applied to all branch and bound subproblems. By using this rule and by exploiting efficient data structures, maximum clique problems are solved for graphs of up to 1,000 vertices and 150,000 edges.

•Jan 3, 1990•4 citations

New algorithms for Quadratic Unconstrained Binary Optimization (QUBO) with applications in engineering and social sciences

Tavares, Gabriel

This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.

•Jan 1, 2008•7 citations

Logical and Inequality Implications for Reducing the Size and Complexity of Quadratic Unconstrained Binary Optimization Problems

Fred Glover, Mark W. Lewis, Gary A. Kochenberger

The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.

arXiv:1705.09545•May 26, 2017•0 citations
The class of problems known as quadratic zero-one (binary) unconstrained optimisation has provided access to a vast array of combinatorial optimisation problems, allowing them to be expressed within the setting of a single unifying model. A gap exists, however, in addressing polynomial problems of degree greater than 2. To bridge this gap, we provide methods for efficiently executing core search processes for the general polynomial unconstrained binary (PUB) optimisation problem. A variety of search algorithms for quadratic optimisation can take advantage of our methods to be transformed directly into algorithms for problems where the objective functions involve arbitrary polynomials. Part 1 of this paper (Glover et al., 2011) provided fundamental results for carrying out the transformations and described coding and decoding procedures relevant for efficiently handling sparse problems, where many coefficients are 0, as typically arise in practical applications. In the present part 2 paper, we provide special algorithms and data structures for taking advantage of the basic results of part 1. We also disclose how our designs can be used to enhance existing quadratic optimisation algorithms.
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.
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
In this paper, an exact algorithm in polynomial time is developed to solve unrestricted binary quadratic programs. The computational complexity is $O\left( n^{\frac{15}{2}}\right) $, although very conservative, it is sufficient to prove that this minimization problem is in the complexity class PPP. The implementation aspects are also described in detail with a special emphasis on the transformation of the quadratic program into a linear program that can be solved in polynomial time. The algorithm was implemented in MATLAB and checked by generating five million matrices of arbitrary dimensions up to 30 with random entries in the range $\left[ -50,50\right] $. All the experiments carried out have revealed that the method works correctly.
Unconstrained quadratic zero-one programming belongs to the class of NP-complete problems. It is therefore considered computationally intractable. Much research has been done in trying to find subsets of unconstrained quadratic 0-1 programs that can be solved in polynomial time. However, for the general problem, nonpolynomial methods must be used, resulting in limitations on the size of problems that can be solved. Branch and bound is a computational method that implicitly enumerates all possible solutions. Research on branch and bound algorithms is vast. Due to the computational complexity of the algorithm, efficient implementations are necessary in order to solve even moderate size problems. It is natural to expect that any implementation of a branch and bound algorithm may consume large amounts of computer resources due to the nature of the algorithm. Therefore, it is desirable to exploit contemporary high performance computers. In this thesis, efficiencies in the implementation of new 0-1 branch and bound algorithms on contemporary computer architectures are studied. Though not primarily designed for combinatorial problems, it is shown that many contemporary architectures, including distributed and shared memory multiprocessors, are capable of increasing the scope of solvable discrete programming problems. An application of unconstrained quadratic 0-1 programming is the maximum clique problem. It is shown that the variable selection rule in the proposed algorithm is equivalent to a nongreedy vertex selection rule for the maximum clique problem. This rule enhances the use of preprocessing rules that are applied to all branch and bound subproblems. By using this rule and by exploiting efficient data structures, maximum clique problems are solved for graphs of up to 1,000 vertices and 150,000 edges.
This dissertation investigates the Quadratic Unconstrained Binary Optimization (QUBO) problem, i.e. the problem of minimizing a quadratic function in binary variables. QUBO is studied at two complementary levels. First, there is an algorithmic aspect that tells how to preprocess the problem, how to find heuristics, how to get improved bounds and how to solve the problem with all the above ingredients.Second, there is a practical aspect that uses QUBO to solve various applications from the engineering and social sciences fields including: via minimization, 2D/3D Ising models, 1D Ising chain models, image binarization, hierarchical clustering, greedy graph coloring/partitioning, MAX-2-SAT, MIN-VC, MAX-CLIQUE, MAX-CUT, graph stability and minimum k-partition.Several families of fast heuristics for QUBO are analyzed, which include a novel probabilistic based class of methods.It is shown that there is a unique maximal set of persistencies for the linearization model for QUBO.This set is determined in polynomial time by a maximum flow followed by the computation of the strong components of a network that has 2n+2 nodes, where n is the number of variables. The identification of the above persistencies leads to a unique decomposition of the function, such that each component can be optimized separately. To find further persistencies, two additional techniques are proposed: one is based on the second order derivatives of Hammer et al. [HH81]; the other technique is a probing procedure on the two possible values of the variables.These preprocessing tools work remarkably well for certain classes of problems.We improved the Iterated Roof-Dual bound (IRD) of [BH89] by proposing two combinatorial methods: one was named the squeezed IRD; and the second was called the project-and-lift IRD method.The cubic-dual bound can be found by means of linear programming by adding a set of triangle inequalities to the standard linearization, whose number is cubic in the number of variables. We show that this set can be reduced depending on the coefficients of the terms of the function. This leads to the possibility of computing the cubic-duals of larger QUBOs.
The quadratic unconstrained binary optimization (QUBO) problem arises in diverse optimization applications ranging from Ising spin problems to classical problems in graph theory and binary discrete optimization. The use of preprocessing to transform the graph representing the QUBO problem into a smaller equivalent graph is important for improving solution quality and time for both exact and metaheuristic algorithms and is a step towards mapping large scale QUBO to hardware graphs used in quantum annealing computers. In an earlier paper (Lewis and Glover, 2016) a set of rules was introduced that achieved significant QUBO reductions as verified through computational testing. Here this work is extended with additional rules that provide further reductions that succeed in exactly solving 10% of the benchmark QUBO problems. An algorithm and associated data structures to efficiently implement the entire set of rules is detailed and computational experiments are reported that demonstrate their efficacy.