The Quadratic Unconstrained Binary Optimization (QUBO) model is widely used to solve combinatorial optimization problems by determining the optimal assignment of binary variables in a quadratic formulation. Given its versatility, extensive research has been conducted on developing QUBO solvers and converting combinatorial optimization problems into equivalent QUBO formulations. This paper introduces QUBO++, a novel C++ symbolic mathematical computation library specifically designed for QUBO modeling. It provides a comprehensive set of operators and functions for symbolic computation, enabling seamless transformation of optimization problems into QUBO models. While several Python-based libraries exist for similar purposes, QUBO++ is the only dedicated C++ library that supports multithreaded acceleration via Intel Threading Building Blocks (oneTBB). In addition to its modeling capabilities, QUBO++ includes two fundamental QUBO solvers: the Exhaustive Solver, which is useful for verifying small-scale problems, and the Easy Solver, designed for efficient testing and debugging. Compared to existing Python-based QUBO modeling tools such as PyQUBO, Fixstars Amplify, and Tytan, QUBO++ demonstrates significantly higher performance, achieving speedups of over 1,700 times in certain scenarios. By leveraging QUBO-based problem-solving techniques, QUBO++ serves as a powerful and versatile tool for addressing complex optimization challenges in both industrial and societal applications.
The Quadratic Unconstrained Binary Optimization (QUBO) model is widely used to solve combinatorial optimization problems by determining the optimal assignment of binary variables in a quadratic formulation. Given its versatility, extensive research has been conducted on developing QUBO solvers and converting combinatorial optimization problems into equivalent QUBO formulations. This paper introduces QUBO++, a novel C++ symbolic mathematical computation library specifically designed for QUBO modeling. It provides a comprehensive set of operators and functions for symbolic computation, enabling seamless transformation of optimization problems into QUBO models. While several Python-based libraries exist for similar purposes, QUBO++ is the only dedicated C++ library that supports multithreaded acceleration via Intel Threading Building Blocks (oneTBB). In addition to its modeling capabilities, QUBO++ includes two fundamental QUBO solvers: the Exhaustive Solver, which is useful for verifying small-scale problems, and the Easy Solver, designed for efficient testing and debugging. Compared to existing Python-based QUBO modeling tools such as PyQUBO, Fixstars Amplify, and Tytan, QUBO++ demonstrates significantly higher performance, achieving speedups of over 1,700 times in certain scenarios. By leveraging QUBO-based problem-solving techniques, QUBO++ serves as a powerful and versatile tool for addressing complex optimization challenges in both industrial and societal applications.
We present PyQUBO, an open-source Python library for constructing quadratic unconstrained binary optimizations (QUBOs) from the objective functions and the constraints of optimization problems. PyQUBO enables users to prepare QUBOs or Ising models for various combinatorial optimization problems with ease thanks to the abstraction of expressions and the extensibility of the program. QUBOs and Ising models formulated using PyQUBO are solvable by Ising machines, including quantum annealing machines. We introduce the features of PyQUBO with applications in the number partitioning problem, knapsack problem, graph coloring problem, and integer factorization using a binary multiplier. Moreover, we demonstrate how PyQUBO can be applied to production-scale problems through integration with quantum annealing machines. Through its flexibility and ease of use, PyQUBO has the potential to make quantum annealing a more practical tool among researchers.
The field of Combinatorial Optimization (CO) is one of the most important
areas in the general field of optimization, with important applications found
in every industry, including both the private and public sectors. It is also
one of the most active research areas pursued by the research communities of
Operations Research, Computer Science, and Analytics as they work to design and
test new methods for solving real world CO problems. In recent years, we have
discovered that a mathematical formulation known as QUBO, an acronym for a
Quadratic Unconstrained Binary Optimization problem, can embrace a large
variety of important CO problems found in industry and government. Through
special reformulation techniques that are easy to apply, the power of QUBO
solvers can be used to efficiently solve many important problems once they are
put into the QUBO framework. This two-step process of first re-casting an
original model into the form of a QUBO model and then solving it with
appropriate software enables the QUBO model to become a unifying framework for
combinatorial optimization. The alternative path that results for effectively
modeling and solving many important problems is a new development in the field
of combinatorial optimization. The materials provided in subsequent sections
illustrate the process of reformulating important optimization problems as QUBO
models through a series of explicit examples. Collectively these examples
highlight the application breadth of the QUBO model. We do not focus here on
modeling a given problem in the form classically adopted in the optimization
community. Rather, our examples disclose the methods that can be used to recast
a given problem, perhaps existing in a classical mathematical form, into an
equivalent QUBO model.
Optimization is a crucial challenge across various domains, including finance, resource allocation, and mobility. Quantum computing has the potential to redefine the way we handle complex problems by reducing computational complexity and enhancing solution quality. Optimization, particularly of objective functions, stands to benefit significantly from quantum solvers, which leverage principles of quantum mechanics like superposition, entanglement, and tunneling. The Ising and Quadratic Unconstrained Binary Optimization (QUBO) models are the most suitable formulations for these solvers, involving binary variables and constraints treated as penalties within the overall objective function. To harness quantum approaches for optimization, two primary strategies are employed: exploiting quantum annealers—special-purpose optimization devices—and designing algorithms based on quantum circuits. This review provides a comprehensive overview of quantum optimization methods, examining their advantages, challenges, and limitations. It demonstrates their application to real-world scenarios and outlines the steps to convert generic optimization problems into quantum-compliant models. Lastly, it discusses available tools and frameworks that facilitate the exploration of quantum solutions for optimization tasks.
Quadratic Unconstrained Binary Optimization (QUBO) is a versatile framework for modeling combinatorial optimization problems. This study benchmarks five software-based QUBO solvers: Neal, PyTorch (CPU), PyTorch (GPU), JAX, and SciPy, on randomly generated QUBO matrices ranging from 1000x1000 to 45000x45000, under six convergence thresholds from 10^-1 to 10^-6. We evaluate their performance in terms of solution quality (energy) and computational time. Among the solvers tested, Neal achieved the lowest energy values but was limited to problems with up to 6000 variables due to high memory consumption. PyTorch produced slightly higher energy results than Neal but demonstrated superior scalability, solving instances with up to 45000 variables. Its support for GPU acceleration and CPU multi-threading also resulted in significantly shorter runtimes. JAX yielded energy values slightly above those of PyTorch and was limited to 25000 variables, with runtimes comparable to PyTorch on GPU. SciPy was the most constrained solver, handling only up to 6000 variables and consistently producing the highest energy values with the longest computation times. These findings highlight trade-offs between solution quality, scalability, and runtime efficiency, and suggest that PyTorch is the most balanced choice for large-scale QUBO problems when computational resources permit.
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.The goal of the QUBO problem is to find an optimal assignment of values to the variables that minimizes the energy function.With the increasing applicability of QUBO problems, QUBO solvers on different computing platforms have been developed.It is necessary to generate hard QUBO instances for improving and evaluating the performance of QUBO solvers.In this dissertation, we research in generating hard QUBO instances.First, we propose an effective method called bit duplication technique for generating hard QUBO instances with adjustable sizes.The idea is to duplicate specified number of bits and then to give constraints so that the corresponding two bits take the same binary values.By this technique, any QUBO problem with n bits is converted to a hard QUBO problem with (n + m) bits (0 < m ≤ n).Second, in order to avoid the increase in the original size after performing bit duplication technique, we propose a novel technique which we call bit reduction to reduce the size of the original QUBO problem before preforming bit duplication technique.Through this method, hard QUBO instances can be generated without increasing the size of the original QUBO problem.By combining the bit duplication and bit reduction technique, we propose the method for generating hard instance of QUBO problems from any original QUBO problem without changing the size. 1 We use random QUBO problems, N-Queens problems, Traveling Salesman Problem (TSP), maximum weight matching (MWM) problems and Satisfiability problems (SAT) as original QUBO problems to generate hard QUBO instances.The performance of QUBO solvers including Gurobi optimizer, Fixstars Amplify AE, OpenJij with SA, D-Wave Hybrid and ABS2 QUBO solvers are evaluated for solving the generated hard QUBO instances.The experimental results show that generated QUBO instances are much hard for solving.
With the advances in customized hardware for quantum annealing and digital/CMOS Annealing, Quadratic Unconstrained Binary Optimization (QUBO) models have received growing attention in the optimization literature. Motivated by an existing general-purpose approach that derives QUBO models from binary linear programs (BLP), we propose a novel Multilevel Constraint Transformation Scheme (MLCTS) that derives QUBO models with fewer ancillary binary variables. We formulate sufficient conditions for the existence of a compact QUBO formulation (i.e., in the original BLP decision space) in terms of constraint levelness and demonstrate the flexibility and applicability of MLCTS on synthetic examples and several well-known combinatorial optimization problems, i.e., the Maximum 2-Satisfiability Problem, the Linear Ordering Problem, the Community Detection Problem, and the Maximum Independence Set Problem. For a proof-of-concept, we compare the performance of two QUBO models for the latter problem on both a general-purpose software-based solver and a hardware-based QUBO solver. The MLCTS-derived models demonstrate significantly better performance for both solvers, in particular, solving up to seven times more instances with the hardware-based approach.