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

Discrete Optimization

A max-flow approach to improved lower bounds for quadratic unconstrained binary optimization (QUBO)

Endre Boros, Peter L. Hammer, Richard L. Sun, Gabriel Tavares

Published Dec 1, 2007• 50 citations
Publisher
DOI
10.1016/j.disopt.2007.02.001

Related papers

Quadratic Unconstrained Binary Optimization (QUBO) Modeling

WORLD SCIENTIFIC eBooks•Mar 20, 2023•2 citations

QUBO: Quadratic Unconstrained Binary Optimization Problem

Gary A. Kochenberger, Fred Glover, Haibo Wang

Springer eBooks•Dec 17, 2024•1 citation

Local search heuristics for Quadratic Unconstrained Binary Optimization (QUBO)

Endre Boros, Peter L. Hammer, Gabriel Tavares

Journal of Heuristics•Feb 20, 2007•142 citations

Bounds for Binary Integer Programming via Unconstrained Quadratic Pseudo-Boolean Optimization

Sirilak Phonin, Chulin Likasiri

This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.

Mathematics•Aug 17, 2026•1 citation

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

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
This research proposes a method for finding bounds in binary integer programming (BIP) and quadratic binary integer programming (QBIP). Our approach utilizes a max-flow technique within the framework of quadratic pseudo-Boolean optimization. We apply Lagrange multipliers to transform these problems into a quadratic pseudo-Boolean format, enabling us to create a corresponding network. We develop sufficient conditions under which a flow can or cannot be established in this network. The upper bound of the original problem is obtained through a feasible flow within the network. Additionally, we provide the optimality conditions for the solutions discussed in this paper. We have derived the closed forms for the various functions and values commonly used in our proposed method, as well as a lower bound for both BIP and QBIP, which can assist in solving these problems. This paper includes examples that illustrate both networks containing flows and those that do not, as well as examples that demonstrate lower and upper bound solutions as identified by our method. Furthermore, since our approach can also be applied to Quadratic Unconstrained Binary Optimization (QUBO), we provide the closed forms for the frequently used functions and values in that context, along with an example showcasing its application to a quadratic unconstrained optimization problem.
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.
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.