Robust Optimization of Unconstrained Binary Quadratic Problems
This addresses robustness in optimization for applications like business decision-making and quantum computing, but appears incremental as it builds on existing binary quadratic models.
The paper tackles the problem of finding robust solutions for unconstrained binary quadratic optimization under perturbations in the Q matrix, motivated by uncertainty in big data and quantum annealing computers. It uses experimental design to identify robust solutions and provides a theoretical framework for variable robustness, with an illustrative business application.
In this paper we focus on the unconstrained binary quadratic optimization model, maximize 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.