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

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

Gregory P. Rodgers

Published Jan 3, 1990• 4 citations
OpenAlex

Abstract

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.

Related papers

Lagrangean decompositions for the unconstrained binary quadratic programming problem

Geraldo Regis Mauri, Luiz Antônio Nogueira Lorena

The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.

International Transactions in Operational Research•Dec 4, 2009•11 citations

Enhancing convexification techniques for solving nonconvex quadratic programming problems

Xiaofei Qi

At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .

•Jan 1, 2017•0 citations

Intelligent medical expert system: addressing philosophical and logistical deficiencies of the rule-based medical expert system

Christopher A. Hughes

Quadratic programming is a fundamental problem in constrained optimization. One of the simplest quadratic programs has only simple bounds. In this thesis, we present several algorithms for the numerical solution of quadratic programs with simple bounds along with numerical results. All of our algorithms are designed for or applicable to the case where the Hessian matrix is large and sparse. Direct active set methods traditionally have not been used for large sparse problems because their storage requirements and data structure manipulations were thought to be prohibitive and because typical dense active set methods require a large number of iterations if the initial active set is very different from that at the solution. We show how a standard direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. We show that all of the necessary factorizations can be carried out in a static data structure that can be set up before the numeric computations begin and requires only as much space as one Cholesky factorization of the Hessian of the quadratic. To allow us to add and delete several constraints from the active set at each iteration, we use projection techniques and a new search direction for the indefinite case. We also propose a heuristic method for finding a starting point that reduces the number of iterations required in practice. Iterative methods are attractive for large sparse quadratic programs because they require less data structure manipulation and hence are considerably easier to implement. The numerical results available for existing iterative methods indicate that they have linear rates of convergence. To avoid difficulties we experienced because of the feasibility requirement of interior point methods, we show how to reformulate a convex quadratic program with simple bounds as an unconstrained piecewise quadratic function with the same optimality conditions. We present an iterative method for solving this new problem that is superlinearly convergent and is suitable for sparse problems.

•Jan 1, 1990•1 citation

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

Preprocessing of unconstrained quadratic binary optimization

Endre Boros, Peter L. Hammer, Gabriel Tavares

We propose several efficient preprocessing techniques for Unconstrained Quadratic Binary Optimization (QUBO), including the direct use of enhanced versions of known basic techniques (e.g., implications derived from first and second order derivatives and from roof–duality), and the integrated use (e.g., by probing and by consensus) of the basic techniques. The application of these techniques is implemented using a natural network flow model of QUBO. The use of the proposed preprocessing techniques provides: (i) a lower bound of the minimum of the objective function, (ii) the values of some of the variables in some or every optimum, (iii) binary relations (equations, inequalities, or non-equalities) between the values of certain pairs of variables in some or every optimum, and (iv) the decomposition (if possible) of the original problem into several smaller pairwise independent QUBO problems. Extensive computational experience showing the efficiency of the proposed techniques is presented. Substantial problem simplifications, improving considerably the existing techniques, are demonstrated on benchmark problems as well as on randomly generated ones. In particular, it is shown that 100% data reduction is achieved using the proposed preprocessing techniques for MAX-CUT graphs derived from VLSI design, MAX-Clique in c-fat graphs derived from fault diagnosis, and minimum vertex cover problems in random planar graphs of up to 500 000 vertices. Acknowledgements: The third author was partially financially supported by the Portuguese FCT and by the FSE in the context of the III Quadro Comunitario de Apoio.

•Jan 1, 2006•66 citations

Enhancing Quantum Algorithms for Quadratic Unconstrained Binary Optimization via Integer Programming

Friedrich Wagner, Jonas Nüßlein, Frauke Liers

To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.

arXiv:2302.05493•ACM Transactions on Quantum Computing•Jan 13, 2025•2 citations
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.
The unconstrained binary quadratic programming problem (QP) is a classical non-linear problem of optimizing a quadratic objective by a suitable choice of binary decision variables. This paper proposes new Lagrangean decompositions to find bounds for QP. The methods presented treat a mixed binary linear version (LQP) of QP with constraints represented by a graph. This graph is partitioned into clusters of vertices forming a dual problem that is solved by a subgradient algorithm. The subproblems formed by the generated subgraphs are solved by CPLEX. Computational experiments consider a data set formed by several difficult instances with different features. The results show the efficiency of the proposed methods over traditional Lagrangean relaxations and other methods found in the literature.
At the intersection of combinatorial and nonlinear optimization, quadratic programming (QP) plays an important role in practice and optimization theory.With wide-spread real-world applications including, but not limited to, engineering design, game theory, and economics, quadratic programming has many valuable contributions and has attracted considerable interest over the past few decades.As a more general formulation, quadratically constrained quadratic programming (QCQP) problems arise naturally from a lot of applications such as facility location, production planning, economic equilibria and Euclidean distance geometry, etc.Most global optimization approaches for nonconvex QCQPs are based on constructing a convex or linear relaxation of the problem, and embedding it within an exhaustive search mechanism, where a lower bound is calculated as the value of the objective function of this relaxation (for a minimization problem) at each iteration of the search tree.The two principle elements affecting the overall effectiveness of such exhaustive search methods are the tightness of the underlying relaxation and the efficiency of calculating the lower bound.Besides, the performance of a branch-and-bound algorithm also relies on the procedure used to select a branching node and branching variable, which leads to good quality feasible solutions or equivalently an upper bound.vii LIST OF TABLES 5.5 Computational results of 0-1 QPs with n = 40 . . . . . . . . . . . .110 5.6 Computational results of 0-1 QPs with n = 50 . . . . . . . . . . . .
Quadratic programming is a fundamental problem in constrained optimization. One of the simplest quadratic programs has only simple bounds. In this thesis, we present several algorithms for the numerical solution of quadratic programs with simple bounds along with numerical results. All of our algorithms are designed for or applicable to the case where the Hessian matrix is large and sparse. Direct active set methods traditionally have not been used for large sparse problems because their storage requirements and data structure manipulations were thought to be prohibitive and because typical dense active set methods require a large number of iterations if the initial active set is very different from that at the solution. We show how a standard direct active set method for solving definite and indefinite quadratic programs with simple bounds can be efficiently implemented for large sparse problems. We show that all of the necessary factorizations can be carried out in a static data structure that can be set up before the numeric computations begin and requires only as much space as one Cholesky factorization of the Hessian of the quadratic. To allow us to add and delete several constraints from the active set at each iteration, we use projection techniques and a new search direction for the indefinite case. We also propose a heuristic method for finding a starting point that reduces the number of iterations required in practice. Iterative methods are attractive for large sparse quadratic programs because they require less data structure manipulation and hence are considerably easier to implement. The numerical results available for existing iterative methods indicate that they have linear rates of convergence. To avoid difficulties we experienced because of the feasibility requirement of interior point methods, we show how to reformulate a convex quadratic program with simple bounds as an unconstrained piecewise quadratic function with the same optimality conditions. We present an iterative method for solving this new problem that is superlinearly convergent and is suitable for sparse problems.
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.
We propose several efficient preprocessing techniques for Unconstrained Quadratic Binary Optimization (QUBO), including the direct use of enhanced versions of known basic techniques (e.g., implications derived from first and second order derivatives and from roof–duality), and the integrated use (e.g., by probing and by consensus) of the basic techniques. The application of these techniques is implemented using a natural network flow model of QUBO. The use of the proposed preprocessing techniques provides: (i) a lower bound of the minimum of the objective function, (ii) the values of some of the variables in some or every optimum, (iii) binary relations (equations, inequalities, or non-equalities) between the values of certain pairs of variables in some or every optimum, and (iv) the decomposition (if possible) of the original problem into several smaller pairwise independent QUBO problems. Extensive computational experience showing the efficiency of the proposed techniques is presented. Substantial problem simplifications, improving considerably the existing techniques, are demonstrated on benchmark problems as well as on randomly generated ones. In particular, it is shown that 100% data reduction is achieved using the proposed preprocessing techniques for MAX-CUT graphs derived from VLSI design, MAX-Clique in c-fat graphs derived from fault diagnosis, and minimum vertex cover problems in random planar graphs of up to 500 000 vertices. Acknowledgements: The third author was partially financially supported by the Portuguese FCT and by the FSE in the context of the III Quadro Comunitario de Apoio.
To date, research in quantum computation promises potential for outperforming classical heuristics in combinatorial optimization. However, when aiming at provable optimality, one has to rely on classical exact methods like integer programming. State-of-the-art integer programming algorithms can compute strong relaxation bounds even for hard instances, but may have to enumerate a large number of subproblems for determining an optimum solution. If the potential of quantum computing is realized, it can be expected that in particular finding high-quality solutions for hard problems can be done fast. Still, near-future quantum hardware considerably limits the size of treatable problems. In this work, we go one step into integrating the potentials of quantum and classical techniques for combinatorial optimization. We propose a hybrid heuristic for the weighted maximum-cut problem and for quadratic unconstrained binary optimization. The heuristic employs a linear programming relaxation, rendering it well-suited for integration into exact branch-and-cut algorithms. For large instances, we reduce the problem size according to a linear relaxation such that the reduced problem can be handled by quantum machines of limited size. Moreover, we improve the applicability of depth-1 QAOA, a parameterized quantum algorithm, by deriving a parameter estimate for arbitrary instances. We present numerous computational results from real quantum hardware.