Black Box Optimization Using QUBO and the Cross Entropy Method
Black box optimization (BBO) can be used to optimize functions whose analytic
form is unknown. A common approach to realize BBO is to learn a surrogate model
which approximates the target black box function which can then be solved via
white box optimization methods. In this paper we present our approach BOX-QUBO,
where the surrogate model is a QUBO matrix. However, unlike in previous
state-of-the-art approaches, this matrix is not trained entirely by regression,
but mostly by classification between 'good' and 'bad' solutions. This better
accounts for the low capacity of the QUBO matrix, resulting in significantly
better solutions overall. We tested our approach against the state-of-the-art
on four domains and in all of them BOX-QUBO showed significantly better
results. A second contribution of this paper is the idea to also solve white
box problems, i.e. problems which could be directly formulated as QUBO, by
means of black box optimization in order to reduce the size of the QUBOs to
their information-theoretic minimum. The experiments show that this
significantly improves the results for MAX-$k$-SAT.