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.
Quadratic pseudo-Boolean functions (i.e., quadratic functions with real-valued coefficients and two-valued variables) are the native input to quantum annealers and also a common problem format to optimize with the QAOA algorithm on circuitmodel quantum computers. In both cases, large, complex optimization problems can be expressed in terms of combinations of simpler problems. A key challenge in problem set-up lies in finding the coefficients for the constituent sub-problems. These need to be chosen such that the function is minimized on valid inputs and is higher elsewhere. One difficulty is that it is not possible in general to solve for a sub-problem’s coefficients without introducing ancillary variables, the number of which and their corresponding per-row values being unknown a priori. These unknowns lead to solving for a sub-problem’s coefficients being an NP-complete problem.In this paper we present a simple heuristic that considers a prioritized subset of the exponential number of possibilities for each per-row ancillary variable. Using this heuristic, coefficients can be found substantially faster than would be possible using a brute-force search and with less software complexity than is required by prior approaches.
A quadratization represents a Boolean cost by minimizing a quadratic cost over auxiliary variables. For a four-variable family with one positive quartic coefficient and six sufficiently negative quadratic coefficients, this work determines the exact uniform error with at most six genuine pair interactions, allowing any finite auxiliary set. The optimum is the minimum of an explicit quadratic fallback and thirty-nine scalar capacities, explained by three response mechanisms. Interval endpoints and rational max flow construct attaining nonnegative rational networks with at most two auxiliary variables, without optimization linear programs. A structural lower bound covers all finite auxiliary sets. The paper also gives the separate one-auxiliary seven-, eight- and nine-interaction formulas, the one-auxiliary six-interaction procedure with 57 rational linear programs, and an exact interaction frontier. Absolute costs are retained. The results are proof-supported candidate theorems for this structured family; no claim about arbitrary quartic targets or hardware performance is made.
We prove that any function with real-valued coefficients, whose input is 4 binary variables and whose output is a real number, is perfectly equivalent to a quadratic function whose input is 5 binary variables and is minimized over the new variable. Our proof is constructive: we provide quadratizations for all possible 4-variable functions. There exists 4 different classes of 4-variable functions that each have their own 5-variable quadratization formula. Since we provide 'perfect' quadratizations, we can apply these formulas to any 4-variable subset of an n-variable function even if n >> 4. We provide 5 examples of functions that can be quadratized using the result of this work. For each of the 5 examples we compare the best possible quadratization we could construct using previously known methods, to a quadratization that we construct using our new result. In the most extreme example, the quadratization using our new result needs only N auxiliary variables for a 4N-variable degree-4 function, whereas the previous state-of-the-art quadratization requires 2N (double as many) auxiliary variables and therefore we can reduce by the cost of optimizing such a function by a factor of 2^1000 if it were to have 4000 variables before quadratization. In all 5 of our examples, the range of coefficient sizes in our quadratic function is smaller than in the previous state-of-the-art one, and our coefficient range is a factor of 7 times smaller in our 15-term, 5-variable example of a degree-4 function.
Let
(QP) be an integer quadratic program that consists in minimizing a quadratic function subject to linear constraints. A such problem belongs to the class of
NP-Hard problems. Standard solvers that use a Branch and Bound algorithm can efficiently solve
(QP) in the specific case where its objective function is convex. Thus, to solve
(QP), we choose to reformulate it into an equivalent problem with a convex objective function. Two reformulations are possible: either we reformulate
(QP) into a linear program, or we reformulate it into a convex quadratic program. \par In the first part of this dissertation, we present several linearizations of
(QP), i.e. reformulations into an equivalent program with a linear objective function. Many linearization methods for the quadratic binary programs are known. A natural approach when considering
(QP) is therefore to reformulate it into a quadratic binary program. This can be done by the binary decomposition of each integer variable and then the linearization of each new product of two binary variables. However, this method, that we denote by \texttt{BBL (Binary Binary Linearization)}, leads to a linear program with a large number of variables and constraints. We then present a new approach, \texttt{BIL (Binary Integer Linearization)}, that consists in reformulating
(QP) into a particular quadratic integer program where each quadratic term is the product of an integer variable by a binary variable. As in the \texttt{BBL} approach, the binary variables come from the binary decomposition of the initial integer variables. Then, we linearize the obtained program by replacing each quadratic term by a new real variable and a set of inequalities. As the number of quadratic terms is lower than in the \texttt{BBL} approach, the number of additional variables is reduced. Hence, the obtained integer linear program is significantly smaller in the \texttt{BIL} approach. Moreover, contrary to what one might think, the \texttt{BIL} approach provides a better bound obtained by continuous relaxation than the \texttt{BBL} approach. Each reformulation leads to an integer linear program that is equivalent to
(QP) and that we improve by adding valid inequalities. \par In a second part, we present several quadratic convex reformulations of
(QP), i.e. we reformulate
(QP) into an equivalent program, with a quadratic convex objective function. We first introduce a simple approach to convexify
(QP) that consists in expressing linearly the squares of integer variables using their unary decompositions, and then to convexify with the smallest eigenvalue of the Hessian matrix of
(QP). We call this approach \texttt{NC (Naive Convexification)}. Then, we introduce a new convex reformulation scheme that perturbs the objective function of
(QP) with the linear expression of the products of integer variables, and the equality constraints of
(QP). Then, we show that we can compute, within this scheme, an optimal reformulation of
(QP) in terms of bound obtained by continuous relaxation : the \texttt{IQCR (Integer Quadratic Convex Reformulation)} approach. This reformulation is based on the optimal dual solution of a semi-definite relaxation of
(QP). Moreover, we show that the method \texttt{IQCR} is easily adaptable to mixed-integer programming. This adaptation, that we call \texttt{IQCRs}, also allows us to integrate the inequality constraints of
(QP) into the perturbation of the objective function of our convex reformulation scheme. Then, we present an interesting restriction of the method \texttt{IQCR}, called \texttt{CQCR (Compact Quadratic Convex Reformulation)}. The difference between this last approach and \texttt{IQCR} is that \texttt{CQCR} only uses the linear expression of the integer variable squares to perturb the objective function, while \texttt{IQCR} uses all the products. The interest is that \texttt{CQCR} produces a reformulated problem with a reduced size in comparison with the \texttt{IQCR} approach, what could be profitable experimentally. Finally, we apply these
3 methods \texttt{NC}, \texttt{CQCR} and \texttt{IQCR} to binary quadratic programming. We show that \texttt{NC} and \texttt{CQCR} are equivalent to existing binary convex reformulations. An interesting result is that \texttt{IQCR} is an improvement of existing convexifications for binary quadratic programming.\par In a third part, we design a specific Branch and Bound algorithm based on a projection property of the \texttt{IQCR} approach.\par Finally, we compare the four obtained linearizations and the three obtained quadratic convex reformulations from the computational point of view. For integer programming, computational experiences are carried out with two classes of instances of
(QP), the first having one equality constraint, and the other having one inequality constraint. The results show that most of the considered instances with up to
40 variables can be solved in one hour of CPU time by the \texttt{IQCR} and \texttt{CQCR} approaches. We then test \texttt{IQCR} on binary quadratic programming. The results corroborate that our approach \texttt{IQCR} improves existing convexifications.