×

Quantum bridge analytics II: QUBO-plus, network optimization and combinatorial chaining for asset exchange. (English) Zbl 1468.90079

Summary: Quantum Bridge Analytics relates to methods and systems for hybrid classical-quantum computing, and is devoted to developing tools for bridging classical and quantum computing to gain the benefits of their alliance in the present and enable enhanced practical application of quantum computing in the future.This is the second of a two-part tutorial that surveys key elements of Quantum Bridge Analytics and its applications. Part I focused on the Quadratic Unconstrained Binary Optimization (QUBO) model which is presently the most widely applied optimization model in the quantum computing area, and which unifies a rich variety of combinatorial optimization problems. Part II (the present paper) introduces the domain of QUBO-Plus models that enables a larger range of problems to be handled effectively. After illustrating the scope of these QUBO-Plus models with examples, we give special attention to an important instance of these models called the Asset Exchange Problem (AEP). Solutions to the AEP enable market players to identify exchanges of assets that benefit all participants. Such exchanges are generated by a combination of two optimization technologies for this class of QUBO-Plus models, one grounded in network optimization and one based on a new metaheuristic optimization approach called combinatorial chaining. This combination opens the door to expanding the links to quantum computing applications established by QUBO models through the Quantum Bridge Analytics perspective. We show how the modeling and solution capability for the AEP instance of QUBO-Plus models provides a framework for solving a broad range of problems arising in financial, industrial, scientific, and social settings.

MSC:

90C20 Quadratic programming
90C35 Programming involving graphs or networks

Software:

LKH
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Assad, AA, Multicommodity network flows—a survey, Networks, 8, 1, 37-91 (1978) · Zbl 0381.90040 · doi:10.1002/net.3230080107
[2] Barr, R.; Elam, J.; Glover, F.; Klingman, D.; Fiacco, A.; Kortanek, K., A network augmenting path basis algorithm for transshipment problems, Extremal methods and systems analysis, 250-274 (1978), Berlin: Springer, Berlin · Zbl 0428.90070
[3] Du Y, Kochenberger G, Glover F, Lu ZP, Liu DH, Hulandageri A (2020) Optimal solutions to the minimum sum coloring problem: a comparison of alternative models. Working paper, University of Colorado Denver
[4] Fitzpatrick L (2019) A complete beginner’s guide to atomic swaps. Forbes, Sept 2, 2019 https://www.forbes.com> sites> lukefitzpatrick
[5] Fulkerson, DR; Ford, LR Jr, Flows in networks (1962), Santa Monica: Rand Corporation, Santa Monica · Zbl 0106.34802
[6] Glover, F., Ejection chains, reference structures and alternating path methods for traveling salesman problems, Discrete Appl Math, 65, 223-253 (1996) · Zbl 0846.90117 · doi:10.1016/0166-218X(94)00037-E
[7] Glover, F.; Glover, R.; Klingman, D.; Gallo, G.; Sandi, C., The threshold assignment algorithm, Netflow at Pisa, 12-37 (1986), Berlin: Springer, Berlin · Zbl 0605.90099 · doi:10.1007/BFb0121086
[8] Glover, F.; Phillips, N.; Klingman, D., Netform modeling and applications. Special issue on the practice of mathematical programming, Interfaces, 20, 1, 7-27 (1990) · doi:10.1287/inte.20.4.7
[9] Glover, F.; Klingman, D.; Phillips, N., Network models in optimization and their applications in practice. Reviewed in interfaces, 284 (1992), Hoboken: Wiley, Hoboken
[10] Glover, F.; Kochenberger, G.; Du, Y., Quantum bridge analytics I: a tutorial on formulating and using QUBO models, 4OR Q J Oper Res Invited Surv, 17, 335-371 (2019) · Zbl 1428.90143 · doi:10.1007/s10288-019-00424-y
[11] Glover F, Kochenberger G, Du Y, Hennig R, Wang H, Mniszewski S, Hulandageri A (2020) New advances for solving important classes of combinatorial optimization problems. In: 12th INFORMS conference on information systems and technology (CIST), virtual 2020 INFORMS annual meeting, November 7-13
[12] Glover, F.; Kochenberger, G.; Du, Y.; Punnen, AP, Applications of the QUBO Model, The quadratic unconstrained binary optimization problem (2021), Berlin: Springer, Berlin
[13] Guemri, O.; Nduwayoa, P.; Todosijevic, R.; Hanafi, S.; Glover, F., Probabilistic tabu search for the cross-docking assignment problem, Eur J Oper Res, 277, 3, 875-885 (2019) · Zbl 1430.90377 · doi:10.1016/j.ejor.2019.03.030
[14] Helsgaun, K., An effective implementation of the Lin-Kernighan traveling salesman heuristic, Eur J Oper Res, 126, 1, 106-130 (2000) · Zbl 0969.90073 · doi:10.1016/S0377-2217(99)00284-2
[15] Helsgaun, K., General k-opt submoves for the Lin-Kernighan TSP heuristic, Math Program Comput, 1, 2-3, 119-163 (2009) · Zbl 1180.90269 · doi:10.1007/s12532-009-0004-6
[16] Hoos, H., Programming by optimization, Commun ACM, 55, 2, 70-80 (2012) · doi:10.1145/2076450.2076469
[17] Hu, TC, Multi-commodity network flows, Oper Res (1963) · Zbl 0123.23704 · doi:10.1287/opre.11.3.344
[18] Kochenberger G, Ma M (2019) Quantum computing applications of QUBO models to portfolio optimization. White paper. University of Colorado, Denver, September 2019
[19] Kubicka E, Schwenk AJ (1989) An introduction to chromatic sums. In: CSC’89: proceedings of the 17th conference on ACM annual computer science conference, New York, NY, USA, ACM, pp 39-45
[20] Müller, JC; Pokutta, S.; Martin, A.; Pape, S.; Peter, A.; Winter, T., Pricing and clearing combinatorial markets with singleton and swap orders, Math Methods Oper Res, 85, 155-177 (2017) · Zbl 1371.90133 · doi:10.1007/s00186-016-0555-z
[21] National Academies (2019) The national academies of sciences, engineering and medicine, 2019, quantum computing: progress and prospects. The National Academies Press, NY doi:10.17226/25196
[22] Nolan T (2013) Alt chains and atomic transfers. Bitcointalk https://bitcointalk.org/index.php?topic=193281.0
[23] Rego, C.; Glover, F., Ejection chain and filter-and-fan methods in combinatorial optimization, 4OR Q J Oper Res, 4, 4, 263-296 (2006) · Zbl 1149.90185 · doi:10.1007/s10288-006-0029-x
[24] Rego, C.; Gamboa, D.; Glover, F., Doubly-rooted stem-and-cycle ejection chain algorithm for the asymmetric traveling salesman problem. Special issue on metaheuristics in network optimization, Networks, 68, 1, 23-33 (2016) · doi:10.1002/net.21676
[25] Samorani M, Wang Y, Lu Z, Glover F (2019) Clustering-driven evolutionary algorithms: an application of path relinking to the QUBO problem. In: Glover F, Samorani M (eds) Special issue on intensification, diversification and learning of the Journal of Heuristics, 25(4-5), 629-642
[26] Wang, Y.; Lu, Z.; Glover, F.; Hao, J-K, Path relinking for unconstrained binary quadratic programming, Eur J Oper Res, 223, 3, 595-604 (2012) · Zbl 1292.90225 · doi:10.1016/j.ejor.2012.07.012
[27] Winter T, Rudel M, Lalla H, Brendgen S, Geißler B, Martin A, Morsi A (2011) System and method for performing an opening auction of a derivative. https://www.google.de/patents/US20110119170. Pub. No.: US 2011/0119170 A1. US Patent App. 12/618,410
[28] Xu, J.; Chiu, S.; Glover, F., Tabu search for dynamic routing communications network design, Telecommun Syst, 8, 1-23 (1997) · doi:10.1023/A:1019149101850
[29] Yagiura, M.; Ibaraki, T.; Glover, F., A path relinking approach with ejection chains for the generalized assignment problem, Eur J Oper Res, 169, 548-569 (2006) · Zbl 1079.90119 · doi:10.1016/j.ejor.2004.08.015
[30] Yagiura, M.; Komiya, A.; Kojima, K.; Nonobe, K.; Nagamochi, H.; Ibaraki, T.; Glover, F., A path relinking approach for the multi-resource generalized quadratic assignment problem, 121-135 (2007), Berlin: Springer, Berlin · Zbl 1134.68500
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.