Efficient QUBO transformation for Higher Degree Pseudo Boolean Functions
This incremental improvement addresses efficiency in optimization modeling for researchers and practitioners using QUBO solvers.
The paper tackles the problem of transforming higher degree pseudo-Boolean functions into QUBO format by improving the cubic-to-quadratic transformation to minimize auxiliary variables and penalty coefficients, resulting in a near 100% reduction in subproblem size for Max 3-SAT modeled as QUBO.
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.