A continuous reformulation of the quadratic unconstrained binary optimization problem

Abstract

In this paper we consider the Quadratic Unconstrained Binary Optimization (QUBO) Problem. Using a suitable function and penalty parameter we can reformulate the original QUBO problem as a continuous program. It is shown that the problem of large size can be reduced to two constraints. A new convex formulation is then proposed.