Decomposed Quadratization: Efficient QUBO Formulation for Learning Bayesian Network
This work addresses the efficiency of solving large QUBO problems, particularly for learning Bayesian networks, but it appears incremental as it builds on conventional quadratization techniques.
The paper tackled the problem of reducing binary variables in QUBO formulations for combinatorial optimization, specifically in Bayesian network structure learning, resulting in a method that requires notably fewer variables and outperforms existing algorithms in score maximization on instances with 37 to 223 variables.
Algorithms and hardware for solving quadratic unconstrained binary optimization (QUBO) problems have made significant recent progress. This advancement has focused attention on formulating combinatorial optimization problems as quadratic polynomials. To improve the performance of solving large QUBO problems, it is essential to minimize the number of binary variables used in the objective function. In this paper, we propose a QUBO formulation that offers a bit capacity advantage over conventional quadratization techniques. As a key application, this formulation significantly reduces the number of binary variables required for score-based Bayesian network structure learning. Experimental results on $16$ instances, ranging from $37$ to $223$ variables, demonstrate that our approach requires notably fewer binary variables than quadratization. Moreover, an annealing machine that implement our formulation have outperformed existing algorithms in score maximization.