Robust optimisation of unconstrained binary quadratic problems

摘要

In this paper we focus on the unconstrained binary quadratic optimisation model, maximise x~(t)Qx , x binary, and consider the problem of identifying optimal solutions that are robust with respect to perturbations in the Q matrix. We are motivated to find robust, or stable, solutions because of the uncertainty inherent in the big data origins of Q and limitations in computer numerical precision, particularly in a new class of quantum annealing computers. Experimental design techniques are used to generate a diverse subset of possible scenarios, from which robust solutions are identified. An illustrative example with practical application to business decision making is examined. The approach presented also generates a surface response equation which is used to estimate upper bounds in constant time for Q instantiations within the scenario extremes. In addition, a theoretical framework for the robustness of individual x_(i) variables is considered by examining the range of Q values over which the x_(i) are predetermined.