Grab Senior Data Scientist Liuqin Yang Wins Beale-Orchard-Hays Prize

Summary

Grab Senior Data Scientist Dr. Liuqin Yang, Professor Defeng Sun, and Professor Kim-Chuan Toh received the 2018 Beale-Orchard-Hays Prize for their research paper introducing SDPNAL+. The software employs a majorised semismooth Newton-CG augmented Lagrangian method to solve large-scale semidefinite programming problems with nonnegative constraints. While traditional methods struggled beyond matrix dimensions of 2,000 and 5,000 constraints, SDPNAL+ successfully scales to matrix dimensions of 9,261 and over 12 million constraints. In benchmark testing, the software solved a problem on a desktop PC in 1.5 hours that required 122 hours on a 56-core CPU and 128-GPU cluster using a traditional solver. Grab implements these optimisation techniques to accelerate its passenger-driver allocation algorithms by hundreds of times.

Takeaways

1. 1

   SDPNAL+ expanded solvable semidefinite programming limits to matrix dimensions of 9,261 and over 12 million constraints.

2. 2

   In a benchmark test, SDPNAL+ completed a problem in 1.5 hours on a standard desktop PC, compared to 122 hours required by a traditional solver on a 56-core CPU and 128-GPU cluster.

3. 3

   Grab implements these mathematical optimisation algorithms within its driver-passenger allocation system to run computation tasks hundreds of times faster.