Abstract

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).