On the benefits of a new continuous reformulation for QUBO problems

The quadratic unconstrained binary optimization (QUBO) emerges as an alternative to modeling and solving a wide range of challenging practical applications. This paper proposes reformulating QUBO as a continuous quadratic optimization problem considering theoretical results concerning constraint penalization and diagonal regularization on the objective function. Our findings show that it is possible to address convexity by addressing the problem with the proposed continuous reformulation. The problem is explored with a series of computational experiments using reference instances for the QUBO problem, where up-to-date solutions are provided for benchmark instances. Complementary studies on custom instances show the benefits of using the proposed reformulations for cases with defined negative matrices.