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

arXiv:2105.07032

Variable Reduction For Quadratic Unconstrained Binary Optimization

Amit Verma, Mark W. Lewis

Published May 14, 2021• 3 citations
arXivHTMLPDF

Abstract

Quadratic Unconstrained Binary Optimization models are useful for solving a diverse range of optimization problems. Constraints can be added by incorporating quadratic penalty terms into the objective, often with the introduction of slack variables needed for conversion of inequalities. This transformation can lead to a significant increase in the size and density of the problem. Herein, we propose an efficient approach for recasting inequality constraints that reduces the number of linear and quadratic variables. Experimental results illustrate the efficacy.

DOI
10.48550/arxiv.2105.07032

Related papers

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

A Simplification Method for Inequality Constraints in Integer Binary Encoding HOBO Formulations

Yuichiro Minato

This study proposes a novel method for simplifying inequality constraints in Higher-Order Binary Optimization (HOBO) formulations. The proposed method addresses challenges associated with Quadratic Unconstrained Binary Optimization (QUBO) formulations, specifically the increased computational complexity and reduced solution accuracy caused by the introduction of slack variables and the resulting growth in auxiliary qubits. By efficiently integrating constraints, the method enhances the computational efficiency and accuracy of both quantum and classical solvers. The effectiveness of the proposed approach is demonstrated through numerical experiments applied to combinatorial optimization problems. The results indicate that this method expands the applicability of quantum algorithms to high-dimensional problems and improves the practicality of classical optimization solvers for optimization problems involving inequality constraints.

arXiv:2501.09670•Jan 16, 2025•0 citations

Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions

Amit Verma, Mark W. Lewis, Gary A. Kochenberger

Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.

arXiv:2107.11695•Jul 24, 2021•5 citations

REDUCING DISCRETE OPTIMIZATION PROBLEMS TO THE QUBO FORM

A.M. Semenov, S.R. Usmanov, Aleksey K. Fedorov

Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.

Problems of Information Transmission•Jan 1, 2025•2 citations

New methods for handling binary constraints

Abhay Yadav, Rajeev Ranjan, Upal Mahbub +1 more

We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2016•12 citations

Generating hard quadratic unconstrained binary optimization instances via the method of combining bit reduction and duplication technique

X. H. Li, Koji Nakano, Shunsuke Tsukiyama +3 more

Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables. We propose the method of combing bit reduction and duplication technique that can generate hard instances of QUBO problems from any original QUBO problem without changing the size. The idea is to reduce the original QUBO problem for a specified number of bits and duplicate the same number of bits while ensuring all duplicated pair of bits take the same binary values. Experimental results show that generated QUBO instances are much hard for solving.

International Journal of Parallel Emergent and Distributed Systems•Jul 9, 2024•2 citations
Quadratic Unconstrained Binary Optimization models are useful for solving a diverse range of optimization problems. Constraints can be added by incorporating quadratic penalty terms into the objective, often with the introduction of slack variables needed for conversion of inequalities. This transformation can lead to a significant increase in the size and density of the problem. Herein, we propose an efficient approach for recasting inequality constraints that reduces the number of linear and quadratic variables. Experimental results illustrate the efficacy.
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.
This study proposes a novel method for simplifying inequality constraints in Higher-Order Binary Optimization (HOBO) formulations. The proposed method addresses challenges associated with Quadratic Unconstrained Binary Optimization (QUBO) formulations, specifically the increased computational complexity and reduced solution accuracy caused by the introduction of slack variables and the resulting growth in auxiliary qubits. By efficiently integrating constraints, the method enhances the computational efficiency and accuracy of both quantum and classical solvers. The effectiveness of the proposed approach is demonstrated through numerical experiments applied to combinatorial optimization problems. The results indicate that this method expands the applicability of quantum algorithms to high-dimensional problems and improves the practicality of classical optimization solvers for optimization problems involving inequality constraints.
Quadratic Unconstrained Binary Optimization (QUBO) is recognized as a unifying framework for modeling a wide range of problems. Problems can be solved with commercial solvers customized for solving QUBO and since QUBO have degree two, it is useful to have a method for transforming higher degree pseudo-Boolean problems to QUBO format. The standard transformation approach requires additional auxiliary variables supported by penalty terms for each higher degree term. This paper improves on the existing cubic-to-quadratic transformation approach by minimizing the number of additional variables as well as penalty coefficient. Extensive experimental testing on Max 3-SAT modeled as QUBO shows a near 100% reduction in the subproblem size used for minimization of the number of auxiliary variables.
Practical discrete optimization problems often contain multidimensional arrays of variables with linear constraints, which complicates their conversion to QUBO (quadratic unconstrained binary optimization) form. The article proposes a systematic approach to transforming such problems, which includes three key steps: the transition from a multidimensional representation of variables to a one-dimensional one using the Kronecker product of matrices, the reduction of mixed variables to binary ones, and the introduction of linear constraints into the objective function through quadratic penalties. Explicit computational formulas are obtained for each stage, simplifying their software implementation. The developed method is illustrated with examples from graph theory and combinatorial optimization, including classical formulations, confirming its universality. The results of the article allow standardizing the process of adapting problems for solving on quantum annealing algorithms (e.g., D-Wave) and classical QUBO solvers.
We consider the problem of handling binary constraints in optimization problems. We review methods for solving binary quadratic programs (BQPs), such as the spectral method and semidefinite programming relaxations. We then discuss two new methods for handling these constraints. The first involves the introduction of an extra unconstrained variable along with the alternating direction method of multipliers (ADMM), which has now also appeared in other recent literature. This allows the effect of the binary variables to be decoupled when they are minimized over. The second involves rewarding the one-norm while restricting the infinity-norm, based on a reformulation of the original problem. The piecewise linearity of the negative penalty results in the problem being convex until it hits a critical point, at which point the parameters of this linear term can be changed. These two methods can be applied to any problems which are convex except for binary constraints. In addition to testing them on BQPs, we show the efficacy of these approaches on point segmentation and image segmentation problems.
Quadratic Unconstrained Binary Optimization (QUBO) is a combinatorial optimization problem defined by an energy function that consists of a quadratic formula involving multiple binary variables. We propose the method of combing bit reduction and duplication technique that can generate hard instances of QUBO problems from any original QUBO problem without changing the size. The idea is to reduce the original QUBO problem for a specified number of bits and duplicate the same number of bits while ensuring all duplicated pair of bits take the same binary values. Experimental results show that generated QUBO instances are much hard for solving.