Title: Robust optimisation of unconstrained binary quadratic problems

Authors: Mark Lewis; John Metcalfe; Gary Kochenberger

Addresses: Craig School of Business, Missouri Western State University, Saint Joseph, MO 64507, USA ' Department of Computer Science and Engineering, University of Kansas, Lawrence, KS 66045, USA ' School of Business, University of Colorado, 1250 14th St., Denver, CO 80202, USA

Abstract: In this paper we focus on the unconstrained binary quadratic optimisation model, maximise x^tQx, 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.

Keywords: robust optimisation; unconstrained binary quadratic problems; upper bounds; business decision making; scenario generation; experimental design; surface response equation; sensitivity analysis.

DOI: 10.1504/IJOR.2019.104050

International Journal of Operational Research, 2019 Vol.36 No.4, pp.441 - 454

Received: 08 Dec 2015
Accepted: 26 Nov 2016
Published online: 10 Dec 2019 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article