|
QUBO++ Library with QUBO Solver APIs
Author: Koji Nakano, License: Non-commercial research and evaluation purposes without any guarantees.
|
QUBO++ is a C++ library designed to create and manipulate polynomials of binary variables, specifically to simplify the formulation of QUBO (Quadratic Unconstrained Binary Optimization) problems, which involve quadratic expressions of binary variables in the form of \(0/1\). The objective of QUBO problems is to find an optimal binary assignment that minimizes these expressions.
Key features include:
This document primarily explains how to use the QUBO++ library to design QUBO expressions. Since all source code files of the QUBO++ library and related programs are documented using Doxygen, users can refer to the documentation for detailed usage information.
For detailed license information, please refer to the Terms and Conditions.
A QUBO (Quadratic Unconstrained Optimization Problem) expression is a quadratic formula consisting of binary variables. It includes a constant term, linear terms, and quadratic terms of variables. For example, we can derive a QUBO model \(f\) of three binary variables \(a\), \(b\), and \(c\) as follows:
\begin{eqnarray*} f(a,b,c) &=&(a+b+c-2)(a+b+c-3)\\ &=& 6 -2a -2b -2c -3a -3b -3c +a^2 +ab +ac +ba +b^2 +bc +ca +cb +c^2 \\ &=& 6 -5a -5b -5c +a +2ab +2ac +b +2bc +c \\ & =& 6 -4a -4b -4c +2ab +2ac +2bc \end{eqnarray*}
By expanding \((a+b+c-2)(a+b+c-3)\), we obtain an equivalent quadratic formula. We can simplify it using the fact that \(x^2=x\) holds for all binary variables \(x\). The resulting quadratic formula has:
In this document, we term \((a+b+c-2)(a+b+c-3)\) as a formula and \(6 -4a -4b -4c +2ab +2ac +2bc\) as a QUBO expression. QUBO++ is a C++ library designed to create QUBO formulas, derive the corresponding QUBO expressions, and includes APIs to call QUBO solvers for finding optimal solutions of QUBO models.
A QUBO++ program for generating a QUBO expression and evaluate all solutions are as follows:
The header file qbpp.hpp is included to enable the use of the QUBO++ library, while qbpp_exhaustive_solver.hpp is included to access the ExhaustiveSolver in the library. In this program, three variables, \(a\), \(b\), and \(c\), are defined, along with the formula \(f\). The formula \(f\) is automatically expanded, and the function qbpp::simplify_as_binary returns the corresponding QUBO expression, which is stored in \(g\). ExhaustiveSolver evaluates the values of \(g\) for all \(2^3\) possible solutions, and the results are then displayed.
The output of this program follows.
The resulting value of a QUBO expression for a given assignment of binary values to variables is referred to as the energy. The goal of the QUBO problem is to find the optimal assignment that minimizes this energy. For instance, in the case of \(g\), the minimum value of 0 is achieved when the sum of the three variables equals 2 or 3. When the sum of the three variables is 2 or less, the energy value is 2 or greater. QUBO solvers are designed to find one of the optimal solutions that minimizes the energy.
Let's begin with a simple example that solves the partitioning problem through a QUBO model using the QUBO++ library. This will allow us to quickly see how a combinatorial optimization problem is handled by the QUBO++ library. Specifically, we will use the QUBO++ EasySolver, included in the QUBO++ library, to find solutions for a QUBO model derived from an instance of the partitioning problem.
Suppose that a list of \(n\) numbers \(w_0, w_1, \ldots, w_{n-1}\) is given. The partitioning problem is to partition these numbers into two lists, \(L\) and \(\overline{L}\), so that their sums are as equal as possible. More specifically, \(L\) and \(\overline{L}\) are determined so that
\begin{eqnarray*} {\rm Partition}(L) &=&\left(\sum_{i\in L}w_i - \sum_{i\in \overline{L}}w_i\right)^2 \end{eqnarray*}
is minimized.
Let \(X=\{x_0, x_1, \ldots, x_{n-1}\}\) be a set of \(n\) binary variables to denote elements in \(L\) such that \(x_i=1\) if and only if \(w_i\) is in \(L\). We have the following objective function:
\begin{eqnarray*} {\rm Partition}(X) &=& \left(\sum_{i=0}^{n-1} w_i x_i - \sum_{i=0}^{n-1} w_i (1 - x_i)\right)^2 = \left(2 \sum_{i=0}^{n-1} w_i x_i - \sum_{i=0}^{n-1} w_i \right)^2 \end{eqnarray*}
It should be clear that \({\rm Partition}(X)={\rm Partition}(L)\) and we can obtain a QUBO expression for the partitioning problem by expanding \({\rm Partition}(X)\).
Below is an example of a QUBO++ program that generates a QUBO expression for a partitioning problem with 8 input elements, stored in qbpp::Vector<int>, an integer vector class in QUBO++ compatible with std::vector<int>.
To use the QUBO++ ExhaustiveSolver, the header file qbpp_exhaustive_solver.hpp is required. This program performs the following steps:
Alternatively, the same QUBO expression can be defined more concisely using the extensive vector operations available in the QUBO++ library:
This program constructs a QUBO expression for the partitioning problem in a single formula using vector operations. By leveraging the vector-based features of the QUBO++ library, the formula is defined more concisely and efficiently, eliminating the need for explicit loops and manual construction of the objective function. The qbpp::sum and qbpp::sqr functions streamline the process by handling summation and square QUBO expressions, thereby simplifying the definition of the partitioning problem.
Users of the QUBO++ library can choose between these two approaches based on their preferences and familiarity with the library. The first method offers more explicit control over the construction of the QUBO expression, making it easier for those new to the library to follow the steps. The second method, on the other hand, takes advantage of the powerful vector operations available in QUBO++, providing a more concise and efficient way to define the problem for advanced users who are comfortable with these features.
The QUBO++ library provides the following core classes for designing polynomial expressions involving variables:
These three classes form the core components of the QUBO++ library.
In addition, the following supplementary classes are provided:
To handle vectors or multi-dimensional arrays of integers, qbpp::Var, qbpp::VarInt, and qbpp::Expr objects, use the qbpp::Vector class:
A qbpp::Expr object is internally converted into a qbpp::Model, and subsequently into a qbpp::QuadModel. QUBO solvers find solutions for the QUBO model stored in qbpp::QuadModel and return the results as qbpp::Sol objects:
Each product term in qbpp::Expr objects is represented by:
Lastly, to store or exchange the best solutions obtained by solvers, the following class is provided:
Below is a summary of these classes and their roles:
| Classes | Role |
|---|---|
| qbpp::Var | Stores a single symbolic variable. |
| qbpp::Expr | Stores a polynomial expression of qbpp::Var objects. |
| qbpp::Sol | Stores a solution for qbpp::Expr objects. |
| qbpp::VarInt | Stores a set of qbpp::Var objects representing an integer. |
| qbpp::Vector | Implements a vector and nested vector of objects. |
| qbpp::Term | Stores a single term included in qbpp::Expr objects. |
| qbpp::Model | Stores a qbpp::Expr object with indexing of qbpp::Var objects. |
| qbpp::QuadModel | Stores a qbpp::Model object with a constant term, linear terms, and quadratic terms. |
| qbpp::SolHolder | Stores the best solution with attributes obtained so far. |
Objects of these classes can be converted to strings using the str() global functions, which return std::string representing objects. In other words, str(x) returns the std::string representation of the object x. Additionally, these objects can be displayed using the standard C++ output style, as in std::cout << x. This functionality is particularly useful when designing QUBO++ programs and for debugging purposes.
The output of this code is:
Note that the outputs are provided for observation and debugging purposes only and should not be used as inputs for other programs, as they may change in future updates. Additionally, the output from the latest version of the QUBO++ library may differ from the example shown above.
qbpp::Var objects can be created using auto type deduction and the qbpp::var() function. A qbpp::Var object represents a single variable. Unlike conventional programming languages, it does not store a variable's value; instead, it symbolically represents a variable within qbpp::Expr objects.
We can use the qbpp::var function to create a qbpp::Var object x that stores a variable with the label string X as follows:
Note that the function qbpp::var() uses all lowercase letters, while the class qbpp::Var begins with a capital letter. The argument "X" specifies the label string for the qbpp::Var object, which is used to represent the object as a string. This example uses qbpp::Var object x with the label string X to distinguish them easily, but it is recommended to use the same letter or string for them. The label strings are used only for displaying expressions during debugging and are not referenced in any internal computations. Additionally, the library does not check for duplicate label strings, so no error will occur even if the same label string is assigned to multiple objects.
A vector of qbpp::Var objects can be defined with a specified size as follows:
This creates a vector x with three qbpp::Var objects labeled X. Each object can be accessed using x[0], x[1], and x[2], and their label strings, X[0], X[1], and X[2], combine the base label with the corresponding indices for display purposes.
Multi-dimensional qbpp::Var objects can be defined similarly. For example, the following code creates a \(3\times 2\) matrix x of qbpp::Var objects.
Each object can be accessed as x[0][0], x[0][1], x[1][0], x[1][1], x[2][0], and x[2][1] and they are displayed as X[0][0], X[0][1], X[1][0], X[1][1], X[2][0], and X[2][1].
Higher-dimensional qbpp::Var objects can be defined similarly, with no limitation on the number of dimensions. Additionally, a variable can be created without specifying a label string:
For such variables, default numbered label string such as "{0}", "{1}", and so on are assigned.
The qbpp::var() functions shown above call the constructor of the qbpp::Var class. However, the constructor should not be called directly, as a set of all qbpp::Var objects is maintained internally.
Unique integer IDs, starting from 0, are internally assigned to all created qbpp::Var objects in the order of their creation. By default, these unique IDs are stored as uint32_t, but they can be configured to use uint64_t through a compiler option.
A qbpp::VarInt object is used to represent an integer value within a specified range. It corresponds to a qbpp::Expr object composed of multiple qbpp::Var objects. qbpp::VarInt objects can be created using the qbpp::var_int() global function.
A single qbpp::VarInt object x, representing an integer value in the range \([1,10]\), can be created and displayed with the following code:
From the output of the code below, we can see that x is a qbpp::Expr object, composed of four qbpp::Var objects: x[0], x[1], x[2], and x[3], representing an integer value in the range \([1,10]\).
The integers specifying the range can be negative.
Similarly to the creation of qbpp::Var objects, a multi-dimensional array of qbpp::VarInt objects with the same specified range can be created as follows:
Each qbpp::VarInt object can be accessed by its indices, and the corresponding qbpp::Expr object can be displayed as follows:
If a string is not provided, default names such as {0}, {1}, and so on are assigned, similarly to qbpp::Var objects.
In most cases, qbpp::VarInt objects are implicitly converted to their corresponding qbpp::Expr objects.
A qbpp::Expr object consists of a constant term and a list of qbpp::Term objects, representing an expanded polynomial expression. A qbpp::Term object consists of a constant coefficient and a vector of qbpp::Var objects, representing a product term. For example, a qbpp::Expr object represented as \(2 + 4a + ab + 3abc\) has:
A qbpp::Term object represented as \(3abc\) has a coefficient \(3\) and the qbpp::Var objects \(a\), \(b\), and \(c\).
The number of qbpp::Var objects in a qbpp::Term object is called the degree of the qbpp::Term object. The maximum degree of all qbpp::Term objects in a qbpp::Expr object is called the degree of the qbpp::Expr object.
QUBO and Ising expressions are defined using qbpp::Expr objects with degree 2.
Note that a qbpp::Expr object simply stores an expanded polynomial expression. It does not have any attributes related to the variables used, and thus, it can represent a QUBO expression, an Ising expression, or neither. Additionally, the QUBO++ library stores expressions as expanded polynomial forms in qbpp::Expr objects, automatically expanding any input formula The original, non-expanded form of the formula is not preserved.
The qbpp::Expr class includes constructors for int, qbpp::Var, and qbpp::VarInt. Collectively, we refer to these types, along with qbpp::Expr, as ExprType. Since these constructors allow implicit conversion of ExprType objects to qbpp::Expr, operators and functions defined for qbpp::Expr will work seamlessly with any of these types.
Additionally, the global function qbpp::toExpr() can be used to explicitly convert ExprType object into qbpp::Expr object. The following code demonstrates how to use qbpp::toExpr() to create qbpp::Expr objects:
In this example, f, g, and h are qbpp::Expr objects. However, if qbpp::toExpr() is omitted, f, g, and h would be deduced as qbpp::Var, qbpp::VarInt, and int, respectively, by the auto type deduction. This would lead to a compilation error if these variables are subsequently updated by qbpp::Expr objects.
Operators and functions for qbpp::Expr are divided into two categories: global functions and member functions as follows:
For example, the sqr() function, which computes the square of a qbpp::Expr object, is available as both a global and a member function. The global version, sqr(f), returns the square of f without updating f. In contrast, the member function f.sqr() returns the square of f and updates f with this value.
The following table summarizes the available operators and functions:
| Operators/Functions | Operator Symbols/Function Names | Function Type | Return Type | Argument Type |
|---|---|---|---|---|
| Type Conversion | toExpr() | Global | qbpp::Expr | ExprType |
| Type Conversion | toInt() | Global | Int | Expr |
| Assignment | = | Member | qbpp::Expr | ExprType |
| Binary Operators | +, -, * | Global | qbpp::Expr | ExprType-ExprType |
| Compound Assignment Operators | +=, -=, *= | Member | qbpp::Expr | ExprType |
| Division | / | Global | qbpp::Expr | ExprType-Int |
| Compound Division | /= | Member | qbpp::Expr | Int |
| Unary Operators | +, - | Global | qbpp::Expr | ExprType |
| Comparison (Equality) | == | Global | qbpp::Expr | ExprType-Int |
| Comparison (Double Inequality) | <= <= | Global | qbpp::Expr | IntInf-ExprType-IntInf |
| Square | sqr() | Global | qbpp::Expr | ExprType |
| Square | sqr() | Member | qbpp::Expr | - |
| GCD | gcd() | Global | Int | ExprType |
| Simplify | simplify(), simplify_as_binary(), simplify_as_spin() | Global | qbpp::Expr | ExprType |
| Simplify | simplify(), simplify_as_binary(), simplify_as_spin() | Member | qbpp::Expr | - |
| Eval | eval() | Global | Int | ExprType-MapList |
| Replace | replace() | Global | qbpp::Expr | ExprType-MapList |
| Replace | replace() | Member | qbpp::Expr | MapList |
| Reduce | reduce() | Global | qbpp::Expr | ExprType |
| Reduce | reduce() | Member | qbpp::Expr | MapList |
| Binary/Spin Conversion | binary_to_spin(), spin_to_binary() | Global | qbpp::Expr | ExprType |
| Binary/Spin Conversion | binary_to_spin(), spin_to_binary() | Member | qbpp::Expr | - |
In this table, Int denotes an integer, while IntInf represents either an integer, -qbpp::inf, or +qbpp::inf, which signify infinite values.
qbpp::Expr object can be created using the auto type deduction and qbpp::expr() global function.
A qbpp::Expr object with an empty expression, which is an expression with a constant term 0 and no variables, can be created as shown below:
Unlike qbpp::Var objects, qbpp::Expr objects cannot be assigned label strings.
Similarly to variable definition, a multi-dimensional array of qbpp::Expr with empty expressions can be created. For example, the following code creates a \(3\times 2\) matrix f of qbpp::Var objects, with each object being represented as f[0][0], f[0][1], f[1][0], f[1][1], f[2][0], and f[2][1]:
Be mindful of the capitalization when using qbpp::expr. For example:
creates a single qbpp::Expr object initialized with the integer 3 by calling the constructor of qbpp::Expr class, while
creates three qbpp::Expr objects f[0], f[1] and f[2] by the global function qbpp::expr.
A qbpp::Expr object with an initial expression can be easily created using auto type deduction, as shown below:
In this example, f is a qbpp::Expr object that stores the expression a + 2. However, if the right-hand side of the expression does not involve operations that return a qbpp::Expr object, a compilation error will occur. For example:
In this case, you must use the toExpr() function to explicitly return a qbpp::Expr object, as shown below:
While not recommended, the following workaround uses a no-op multiplication to force the return of a qbpp::Expr object:
The following C++ operators are overloaded to work with qbpp::Expr objects:
=+, *, -, /+, -+=, -=, *=, /=Additionally, the following basic functions can be used:
Since implicit conversions from qbpp::Var and qbpp::VarInt objects to qbpp::Expr objects are defined, these operators can also be used with them. However, the left-hand side of the assignment and compound assignment operators must be a qbpp::Expr object, while qbpp::Var and qbpp::VarInt objects can only be placed on the right-hand side. The division operator and the compound assignment operator for division only accept numbers as divisors, and all dividends, including constants and coefficients, must be divisible. Additionally, all constants and coefficients of the resulting qbpp::Expr object after division must be integers.
The following example demonstrates the use of qbpp::Expr objects with these operators and functions:
The output of this code is as follows:
Simplification functions reduce expressions by sorting variables within terms, merging redundant terms, and ordering all terms. The following simplification functions are available:
Therefore, after applying either simplify_as_binary() or simplify_as_spin(), no terms will contain duplicated variables.
The following example demonstrates how these functions are used and the differences in their outputs:
The output of this code will display the simplified expressions as follows:
Variables within terms are ordered so that earlier-defined variables appear first. Additionally, lower-degree terms appear before higher-degree terms. For terms of the same degree, lexicographically earlier terms are prioritized.
Comparison operators, equality (==), and double inequalities (<= <=) are supported between qbpp::Expr objects and integers. In addition to integers, infinite values represented as +qbpp::inf and -qbpp::inf can also be specified.
Single inequalities are intentionally not supported to prevent potential misuse caused by misunderstandings. Instead, qbpp::inf can be used to represent single inequalities. Specifically:
Other comparison operators such as !=, <, >=, and > are not supported.
As an example of using equality operators, we present a QUBO++ program that solves the following linear equations:
\begin{eqnarray*} x + y &=& 10 \\ 2x+4y &=& 24 \end{eqnarray*}
The following code demonstrates how to solve these linear equations using the Exhaustive Solver:
The output below confirms that the correct solution to the linear equations is obtained:
The following code computes qbpp::Expr object f that takes minimum value of 0 if \( 2\leq a+2b+3c +4d\leq 4 \) is satisfied and finds all optimal solutions:
The output of this code is as follows:
Here, {0} is an auxiliary variable required to implement the double inequality. We can confirm that the output includes all solutions that satisfy the double inequality.
The following code computes qbpp::Expr object f that takes minimum value of 0 if \( 8\leq a+2b+3c +4d \) is satisfied and finds all optimal solutions:
In this code, qbpp::inf is used to indicate that the double inequality has no upper bound. The output of this code is as follows:
We can confirm that the output includes all solutions that satisfy the double inequality.
Given a mapping of variables to integer values, the evaluation function computes the energy of a qbpp::Expr. This mapping must include all variables present in the qbpp::Expr and should be provided as a qbpp::MapList object, which is a list of pairs consisting of qbpp::Var objects and corresponding integer values. The following code demonstrates how to use the evaluation functions with a qbpp::MapList object:
In this code, the energy value of f is evaluated using a qbpp::MapList object, var_map. The energy is also evaluated for a set of values provided using an initializer list. The expected output of the code is as follows:
The replacement functions substitute qbpp::Var and qbpp::VarInt objects in qbpp::Expr objects with other qbpp::Expr objects. Since a qbpp::Expr object can also store integers, variables can be replaced with integers as well. The mapping of qbpp::Var objects to qbpp::Expr objects is defined using qbpp::MapList objects. Unlike evaluation functions, it is not necessary to define mappings for all variables.
The following code demonstrates how to use replacement functions to replace variables:
In this code, the energy value of f is evaluated using a qbpp::MapList object, var_map. The energy is also evaluated for a set of values provided using an initializer list. The expected output of the code is as follows:
The eval() and replace() functions can be used with qbpp::MapList objects and qbpp::VarInt objects, as demonstrated in the following example:
Based on the following output, we can confirm that the functions are working correctly:
Since the replacement function involves intensive computation, repeated applications should be avoided. When replacing multiple variables, a single MapList object defining all replacements should be created, and the replacement function should be called only once for this MapList object. Alternatively, individual MapList objects can be created for each replacement, and the replacement function can be called repeatedly for each one to achieve the same result. However, this repeated execution of the replacement function is computationally expensive and should be avoided.
The reduction function reduces the degree of all terms in qbpp::Expr objects to two, in order to obtain QUBO expressions. The reduction is performed using auxiliary variables, ensuring that the optimal solutions remain unchanged.
The following code demonstrates the reduction of the degree-3 expression \(+abc\):
This code uses the ExhaustiveSolver to evaluate all possible solutions, producing the following output:
The auxiliary variable, shown as {0} is introduced to ensure the equivalent QUBO expression. From the result of the ExhaustiveSolver, we can confirm that \(g=1\) when \(a=b=c=1\), and that \(g\) can take minimum value of 0 otherwise. Thus, \(g\) and \(f=abc\) are equivalent.
QUBO and Ising models are quadratic expressions involving binary ( \(0/1\)) and spin ( \(-1/+1\)) variables, respectively. The binary variable \(x\) and the spin variable \(s\) are related by the equation \(2x - 1 = s\). Based on this relationship, the following functions allow for equivalent conversions between QUBO and Ising expressions:
The following example demonstrates how to use these conversion functions:
The output of this code is:
The QUBO++ library supports vectors and nested vectors of qbpp::Expr objects, which can be treated as multi-dimensional arrays of qbpp::Expr. There is no limitation on the depth of nested vectors. These structures are implemented using the qbpp::Vector class, which is a wrapper around std::vector. In this context, Vector refers to any instance of qbpp::Vector and its nested forms, containing ExprType objects. A Scalar refers to a single ExprType object.
These operators and functions are defined as either Global and/or Member functions of the qbpp::Vector class:
We categorize operators and functions for the Vectors into three types:
Element-wise functions can be defined as both global and member functions. However, Vector-wise and Object-wise functions cannot be member functions because the resulting values are not of the same type as the original objects.
The following table summarizes the operators and functions defined for Vectors of qbpp::Expr objects:
| Operators/Functions | Operator Symbols/Function Names | Global/Member Function | Operation Type | Arguments |
|---|---|---|---|---|
| Type Conversion | toExpr() | Global | Element-wise | Vector |
| Assignment | = | Member | Element-wise | Vector |
| Binary Operators | +, -, * | Global | Element-wise | Vector-Vector, Scalar-Vector, Vector-Scaler |
| Compound Assignment Operators | +=, -=, *= | Member | Element-wise | Vector, Scalar |
| Division | / | Global | Element-wise | Vector-Int |
| Compound Division | /= | Member | Element-wise | Int |
| Unary Operators | +, - | Global | Element-wise | Vector |
| Comparison (Equality) | == | Global | Element-wise | Vector-Int |
| Comparison (Double Inequality) | <= <= | Global | Element-wise | IntInf-Vector-IntInf |
| Square | sqr() | Global | Element-wise | Vector |
| Square | sqr() | Member | Element-wise | - |
| Simplify | simplify(), simplify_as_binary(), simplify_as_spin() | Global | Element-wise | Vector |
| Simplify | simplify(), simplify_as_binary(), simplify_as_spin() | Member | Element-wise | - |
| Reduce | reduce() | Global | Element-wise | Vector |
| Reduce | reduce() | Member | Element-wise | - |
| Binary/Spin Conversion | binary_to_spin(), spin_to_binary() | Global | Element-wise | Vector |
| Binary/Spin Conversion | binary_to_spin(), spin_to_binary() | Member | Element-wise | - |
| Eval/Replace | eval(),replace() | Global | Element-wise | Vector-MapList |
| Replace | replace() | Member | Element-wise | MapList |
| Sum | sum() | Global | Ojbect-wise | Vector (1-d) |
| Total | total_sum(), total_product() | Global | Object-wise | Vector (2-d or higher) | s | | Vector Sum/Vector Product | vector_sum(), vector_product() | Global | Vector-wise | Vector (2-d or higher) | | GCD | gcd() | Global | Object-wise | Int | | Transpose | transpose() | Global | Element-wise | Vector (2-d) | | Transpose | transpose() | Member | Element-wise | - | | Row/Column Read | get_row(), get_col() | Global | Vector | Vector,Int |
We will provide several example programs to demonstrate how to use these operators and functions with Vectors of qbpp::Expr objects.
Recall that the qbpp::expr() function can create a Vector of qbpp::Expr objects, with each object storing an expression. The following program demonstrates how to create Vectors and assign Scalars, such as the integer 1 and a qbpp::Var object x, to them:
Since qbpp::Expr objects do not have labels, the label strings must be specified in the str() function to display them. If label strings are not needed, conventional stream output, such as std::cout << f, can be used.
The following output shows that all elements of the Vectors hold the same scalar value:
A Vector of qbpp::Expr objects can be created without using the qbpp::toExpr() function. The following program demonstrates how to create Vectors using the qbpp::toExpr() function or operators:
The qbpp::toExpr() function is required to explicitly convert the Vector x of qbpp::Var objects to a Vector of qbpp::Expr objects. If the qbpp::toExpr() function is omitted, f will be defined as a Vector of qbpp::Var objects, and the following compound assignment += will cause a compilation error. However, qbpp::toExpr() is not necessary if the right-hand side involves an operator that returns a Vector of qbpp::Expr objects. The output of this code is:
The qbpp::toExpr() function can create a Vector of qbpp::Expr objects using an initializer list as follows:
The output of this code is:
Although the Vector class has no inherent limitation on depth, for technical reasons, the depth is restricted to four levels when using initializer lists.
To create and initialize large vectors, expressions can be assigned one by one as follows:
The output of this code is:
Basic functions such as sqr(), simplify(), simplify_as_binary(), simplify_as_spin(), reduce(), replace(), eval(), binary_to_spin(), and spin_to_binary() perform element-wise operations on qbpp::Expr objects. Their global versions return a vector of qbpp::Expr objects with the same dimensions, storing the results of the operations. Their member versions update the current object and return the modified object. Note that for the eval() function, only the global version is available.
The following example demonstrates how these functions are used:
From the output of this code, we can confirm that the operations are performed element-wise:
The operators for Vectors in the QUBO++ library support element-wise operations on Vectors of the same dimension. They also allow element-wise operations between a Vector and a scalar, where the operation is applied to all qbpp::Expr objects within the Vector using the scalar. The following code demonstrates how these operators are used:
The output of this code is as follows:
The sum() and product() functions in the QUBO++ library compute the sum and product of elements in a Vector, respectively. Compilation errors are intentionally triggered if a scalar or a nested vector is passed as an argument.
The vector_sum() and vector_product() functions in the QUBO++ library operate on Vector objects at the lowest dimensional level.
The following code demonstrates how vector_sum() and vector_product() work on a \(2\times 2\times 2\) Vector:
This code outputs \(2\times 2\times 2\) Vectors as follows:
The total_sum() and total_product() functions compute the sum and product of all qbpp::Expr objects in the Vector and return the result as a scalar qbpp::Expr object. The following code demonstrates their usage:
The output of this code is as follows:
Matrices can be represented using qbpp::Vector<qbpp::Vector<qbpp::Expr>> objects. The following functions are designed to manipulate matrices:
The following code demonstrates the usage of these functions:
The output of this code is:
The following elegant code generates a QUBO expression for an \(n\times n\) matrix. The expression reaches a minimum value of 0 when the sum of each row and column equals 1.
The output of this code is:
The QUBO++ library contains three classes: qbpp::Expr, qbpp::Model, and qbpp::QuadModel, for storing polynomial expressions.
A qbpp::Model object is created from a qbpp::Expr object. It has a "has-a" relationship with qbpp::Expr, holding a const qbpp::Expr object as a member variable. Additionally, it maintains a vector of variables extracted from the qbpp::Expr object, representing indices from 0. Since all member variables are const, they cannot be modified after creation. The degree of a qbpp::Expr object can be arbitrarily large, while the corresponding qbpp::QuadModel must be quadratic. When operating on QUBO models, there is no need to explicitly create a qbpp::Model object. These qbpp::Model objects are intended to handle High-order Unconstrained Binary Optimization (HUBO) in future extensions of the QUBO++ library.
The qbpp::QuadModel class is derived from qbpp::Model and follows an "is-a" relationship with it. This class can store qbpp::Expr objects with quadratic expressions, whereas a qbpp::Model object can store any qbpp::Expr object. It includes member variables to store a constant term, as well as vectors of linear and quadratic terms, allowing convenient access to these elements for QUBO solvers. Similarly, all member variables are const and cannot be modified after creation.
Implicit conversions from a qbpp::Expr object to both qbpp::Model and qbpp::QuadModel are defined. Additionally, an implicit conversion from qbpp::Model to qbpp::QuadModel is defined. Therefore, since QUBO solvers accept qbpp::QuadModel objects, they can also accept qbpp::Expr and qbpp::Model objects. However, if the same QUBO model is repeatedly passed to QUBO solvers, it is recommended to explicitly create a qbpp::QuadModel object from a qbpp::Expr object to avoid repeated implicit conversions. Both qbpp::Model and qbpp::QuadModel objects are immutable, and since their data is stored via shared pointers (std::shared_ptr), the copy overhead is minimal.
The following solvers are available through the QUBO++ library:
Please refer to Sample Programs for examples of how to call these solvers from the QUBO++ library.
To quickly compare how different QUBO solvers handle a QUBO expression f, the following table outlines how to set the QUBO expression, configure parameters, execute the solver, and obtain the solution.
| QUBO Solvers | Setting QUBO expression f | Setting parameter examples | Running the solver and obtaining the solution |
|---|---|---|---|
| EasySolver | auto solver = qbpp::easy_solver::EasySolver(f); | model.time_limit(5); | auto sol = solver.search(); |
| ExhaustiveSOlver | auto solver = qbpp::exhaustive_solver::ExhaustiveSolver(f); | - | auto sol = solver.search(); |
| Gurobi Optimizer | auto model = qbpp_grb::QuadModel(f); | model.set_time_limit(5); | auto sol = model.optimize(); |
| ABS2 QUBO Solver | auto model = qbpp_abs2::QuadModel(f) | auto param = qbpp_abs2::Param(); param.set_time_limit(5); | auto solver = qbpp_abs2::Solver(); auto sol = solver(model, param); |
All solvers support callback functions, which are triggered by events such as the discovery of a new best solution. Typically, callback functions allow users to interrupt solver execution and perform customized operations. The default callback functions simply display the newly found best solutions.
The following table summarizes how to enable default callback functions and define user-defined custom callback functions.
| QUBO Solvers | Enabling default callback | Customizing callback function |
|---|---|---|
| EasySolver | solver.enable_default_callback(); | Define callback() function in derived class of qbpp::easy_solver::EasySolver |
| ExhaustiveSolver | solver.enable_default_callback(); | Define callback() function in derived class of qbpp::exhaustive_solver::ExhaustiveSolver |
| Gurobi Optimizer | auto cb = qbpp_grb::Callback(model); model.set(cb); | Define callback() function in derived class of qbpp_grb::Callback |
| ABS2 QUBO Solver | auto cb = qbpp_abs2::Callback(); param.set(cb); | Define callback() function in derived class of qbpp_abs2::Callback |
The following code demonstrates the use of the default callback function of the ExhaustiveSolver. The QUBO expression is simply the negative sum of 20 variables, and the default callback is enabled. As expected, the minimum energy of -20 is achieved when all variables are set to 1.
The callback function in this code displays the TTS (Time to Solution) and energy of new best solutions as follows:
Solutions of QUBO expressions, stored as qbpp::Expr, qbpp::Model, or qbpp::QuadModel, represent a mapping from qbpp::Var objects to binary (0/1) values. The APIs for the QUBO solvers supported by the QUBO++ library are designed to output solutions as qbpp::Sol objects. qbpp::Sol objects contain:
Note that a solution stored in a qbpp::Sol object may not necessarily be the optimal solution, even though the goal of QUBO is to find the solution with the minimum energy among all possible solutions.
Once a solution stored in a qbpp::Sol object is obtained, next step is to read binary values for each variable. Reading the solution can be done using get() member function for the qbpp::Sol object. The argument of get() member function can be:
The energy() member function simply returns the energy value of the solution.
The following code demonstrates an example of reading the energy value and the solution of each qbpp::Var object.
The output of this code is:
The following code demonstrates how to read the energy value and the solution for each qbpp::VarInt object:
The output of this code is:
The get() member function of the qbpp::Sol class can retrieve solutions for a Vector or a nested Vector of qbpp::Var objects as the same Vector or nested Vector, respectively. Additionally, binary Vector values are often used to represent integers using one-hot encoding, where the integer \(i\) is represented if the \(i\)-th bit is 1 and all other bits are 0. Furthermore, a Vector of Vectors of binary values is used to represent a sequence of integers.
The QUBO++ library provides the global function onehot_to_int() to obtain the integer values represented by such Vectors.
In the following example code, a QUBO expression f is created with a Vector of x, which takes its minimum value of 0 when the sum of x equals 1. Therefore, the optimal solution is one-hot, and onehot_to_int() returns the corresponding integer value of the solution.
Due to the random nature of EasySolver, the output may vary each time the program is run. Below is an example of the output:
The get() and onehot_to_int() functions also support nested Vectors. The following code demonstrates an example using a Vector of Vectors. It creates a QUBO expression f for a Vector of Vectors of qbpp::Var objects, where each element of x takes binary values. This expression f reaches its minimum value of 0 if each row and column of x contains exactly one 1. By applying the onehot_to_int() function to the resulting value of x, we can obtain a sequence of distinct integers.
An example output of this code is:
The qbpp::SolHolder class is designed to store the best solution obtained during computation. It holds the solution along with the TTS (Time To Solution) and the solver’s name. The EasySolver and ExhaustiveSolver classes in the QUBO++ library use qbpp::SolHolder to store and display the best solution in their callback functions. It is also used in the factorization sample program (factorization.cpp) to exchange the best solution found by concurrently executed QUBO solvers.
int32_t and int64_t, respectively. Other possible data types include int8_t, int16_t, int32_t, int64_t, int128_t, int256_t, int512_t, int1024_t and cpp_int. Data types from int128_t to cpp_int utilize the Boost Multiprecision library, which allows EasySolver and ExhaustiveSolver to handle QUBO models with these types.In QUBO++, two integer data types, qbpp::energy_t and qbpp::coeff_t, are used as follows:
If you are unsure how large the coefficients of terms can be, you can initially specify cpp_int for qbpp::energy_t and qbpp::coeff_t. This enables computations with an unlimited number of digits. To achieve this, define ENERGY_TYPE and COEFF_TYPE as cpp_int, or use compiler options such as -DENERGY_TYPE=cpp_int and -DCOEFF_TYPE=cpp_int.
An example source code is provided below:
The output of this code is:
From this output, you can estimate the required bit count for energy_t and coeff_t.
1.9.1