[DMO] Yinyu Ye: Recent Computational Progress on Linear Programming Solvers

13 June 2024 16:00 till 17:00 - Location: Lecture Hall D@ta, 36.HB.01.630 | Add to my calendar

"We describe some recent algorithmic advances in the development of general-purpose linear and semidefinite programming (LP/SDP) solvers. They include:
LP pre-solver based on a fast online LP algorithm
Smart crossover from approximate LP solution to optimal basic solution
ADMM-based method
First-order method PDHG using GPU architecture

Most of these techniques have been implemented in the emerging optimization numerical solver COPT, and they increased the average solution speed by over 3x in the past three years on a set of benchmark LP/SDP problems. For certain problem types, the speedup is more than 50x, and problems that have taken days to solve or never been solved before are now solved in minutes to high accuracy."