David Bernal: Quantum Computing for Discr. Nonlin. Optimization Graver Augmented Multiseed Algorithm скачать в хорошем качестве

David Bernal: Quantum Computing for Discr. Nonlin. Optimization Graver Augmented Multiseed Algorithm

David E. Bernal1,3, Sridhar Tayur2,3, Ignacio E. Grossmann1 Department of Chemical Engineering Tepper School of Business Quantum Computing Group Carnegie Mellon University This presentation introduces the usage of unconventional computing, among them Quantum Computing, for Mixed-Integer Nonlinear Programming (MINLP). Using the Adiabatic Quantum Computing (AQC) framework, we show how different algorithms have been proposed to solve Quadratic Unconstrained Binary Optimization (QUBO) problems using unconventional computers, e.g., Quantum Annealing (QA) and the Quantum Approximation Optimization Algorithm (QAOA). Motivated by the successful usage of decomposition algorithms to tackle MINLP in the classical setting, where we have developed open-source tools for that end [1], we present preliminary results on a new algorithm that we call Graver Augmentation Multistart Algorithm (GAMA). This algorithm uses concepts from algebraic geometry, i.e., the test-set computation through Graver basis of a lattice, and relies on the solution of QUBO subproblems to become a hybrid classical-quantum algorithm for linear equality constrained MINLP problems [2]. Moreover, when the problems are well structured, the computation of the Graver basis can be performed analytically, leading to interesting new algorithms for problems such as Cardinality Constrained Quadratic Programming (CBQP) and Quadratic Assignment Problems (QAP) [3], where we have obtained promising preliminary results. The contents of this presentation are a summary of an open-access course we recently developed on Quantum Integer Programming (QuIP), which has been taught at several universities across the globe, e.g., Carnegie Mellon University and the Indian Institute of Technology in Madras, which we encourage you to visit [4,5]. [1] Mixed-Integer Nonlinear Decomposition Toolbox in Pyomo – MindtPy. https://pyomo.readthedocs.io/en/stabl... [2] Alghassi, Hedayat, Raouf Dridi, and Sridhar Tayur. "Graver bases via quantum annealing with application to non-linear integer programs." arXiv preprint arXiv:1902.04215 (2019). [3] Alghassi, Hedayat, Raouf Dridi, and Sridhar Tayur. "GAMA: A Novel Algorithm for Non-Convex Integer Programs." arXiv preprint arXiv:1907.10930 (2019). [4] Bernal, David E., Sridhar Tayur, and Davide Venturelli. "Quantum Integer Programming (QuIP) 47-779: Lecture Notes." arXiv preprint arXiv:2012.11382 (2020). [5] Quantum Integer Programming. https://bernalde.github.io/QuIP/ Additional blogposts on the content: [1] Quantum Integer Programming http://www.myamplelife.com/wp/2019/12... [2] GAMA http://www.myamplelife.com/wp/2019/06... [3] Quantum Algorithms, Hardware, Applications http://www.myamplelife.com/wp/2021/04... ~ This talk was submitted to MINLP Virtual Workshop 2021 (https://optimisation.doc.ic.ac.uk/min...) Connect with the Computational Optimisation Group at Imperial College London online... Subscribe to the CogImperial YouTube channel for more research related content:    / @cogimperial   Follow us on Twitter for news about our research group:   / cogimperial   Visit our official site for more information: https://optimisation.doc.ic.ac.uk/