GAMA: QUANTUM AND QUANTUM-INSPIRED ALGORITHMS

Add to your list(s) Download to your calendar using vCal

• Sridhar Tayur, Professor of Operations Management, Tepper School of Business, Carnegie Mellon University
• Thursday 09 January 2020, 12:30-14:00
• LT4, Simon Sainsburys Building, Cambridge Judge Business School.

If you have a question about this talk, please contact Emily Brown.

I will discuss two original approaches to solve nonlinear integer optimisation problems that arise in applications in finance, cancer genomics and supply chain optimisation. Our Graver Augmented Multiseed Algorithm (GAMA) utilises augmentation along Graver basis elements (the improvement direction is obtained by comparing objective function values) from these multiple initial feasible solutions.

• A hybrid quantum classical approach (GAMMA-Q) that have the potential to solve a variety of hard linear and nonlinear integer programs, as the form a test set (optimality cerficate). We test two hybrid quantum classical algorithms (on D-Wave) one for computing Graver basis and a second for optimising nonlinear integer programs that utilise GRacer bases to understand the stengths and limitations of the practical quantum annealers available today. Our experiments suggest that with a modest increase in coupler precision along with near term improvements in the number of qubits and connectivity that are expected the ability to outperform classical best in class algorithms is within reach.

• A (fully classical) approach (GAMA-C) to solving certain non convex integer programs. This method is well suited for Cardinality Boolean Quadratic Problems (CBQP), Quadratic Semi Assignment Problems (QSAP) and Quadratic Assignment Problems (QAP). Sensitivity analysis indicates that the rate at which GAMA slows down as the problem size increases is much lower than that of Gurobi. We find that for several instances of practical relevance, GAMA vastly outperforms in terms of time to find the optimal solution (by two or three orders of magnitude).

• Results of applying GAMA on data from The Cancer Genome Project (TCGA) to fi nd mutated driver pathways are encouraging. I will discuss some results on Acute Myleoid Luekemia (AML) and Glioblastoma Multiforme (GBM).

This talk is part of the OTM Seminars, CJBS series.

This talk is included in these lists:

• LT4, Simon Sainsburys Building, Cambridge Judge Business School
• OTM Seminars, CJBS

Note that ex-directory lists are not shown.