TITLE: Preprocessing of Unconstrained Quadratic Binary Optimization

AUTHORS: Endre Boros, Peter L. Hammer, Gabriel Tavares

ABSTRACT: We propose several efficient preprocessing techniques for Unconstrained Quadratic Binary Optimization (QUBO), including the direct use of enhanced versions of known basic techniques (e.g., implications derived from first and second order derivatives and from roof--duality), and the integrated use (e.g., by probing and by consensus) of the basic techniques.
The application of these techniques is implemented using a natural network flow model of QUBO.
The use of the proposed preprocessing techniques provides: (i) a lower bound of the minimum of the objective function, (ii) the values of some of the variables in some or every optimum, (iii) binary relations (equations, inequalities, or non-equalities) between the values of certain pairs of variables in some or every optimum, and (iv) the decomposition (if possible) of the original problem into several smaller pairwise independent QUBO problems.
Extensive computational experience showing the efficiency of the proposed techniques is presented.
Substantial problem simplifications, improving considerably the existing techniques, are demonstrated on benchmark problems as well as on randomly generated ones.
In particular, it is shown that 100% data reduction is achieved using the proposed preprocessing techniques for MAX-CUT graphs derived from VLSI design, MAX-Clique in c-fat graphs derived from fault diagnosis, and minimum vertex cover problems in random planar graphs of up to 500,000 vertices.