Robust optimisation of unconstrained binary quadratic problems

Mark Lewis, John Metcalfe and Gary Kochenberger

International Journal of Operational Research, 2019, vol. 36, issue 4, 441-454

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. (search for similar items in EconPapers)
Date: 2019
References: Add references at CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://www.inderscience.com/link.php?id=104050 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:ids:ijores:v:36:y:2019:i:4:p:441-454

Access Statistics for this article

More articles in International Journal of Operational Research from Inderscience Enterprises Ltd
Bibliographic data for series maintained by Sarah Parker ().